Loading...

​​Discussion 6B

​​Counting

​​Sum Rule

​​If a choice is made in one of two ways, with ​​$a$​ options for the first and ​​$b$​ options for the second, then the number of ways to make the choice is ​​$a+b$​.

​​Product Rule

​​The number of ways to make a sequence of two separate choices, with ​​$a$​ options for the first and ​​$b$​ options for the second, is ​​$a \cdot b$​.

​​Combinatorics

​​Permutations

​​The number of ways to order ​​$n$​ objects is ​​$n!$​.

​​The number of ways to order ​​$k$​ objects from a set of ​​$n$​ objects is ​​$\frac{n!}{(n-k)!}$​.

​​Combinations

​​The number of subsets of size ​​$k$​ for a set of size ​​$n$​ is ​​$\frac{n!}{k! (n-k)!} = \binom{n}{k}$​.

​​How many bitstrings of length ​​$n$​ have exactly ​​$k$​ ones?

​​Stars and Bars

​​You have room for ​​$n$​ fruits in your basket, and there are ​​$k$​ different types of fruit. How many ways can you fill up your basket with ​​$n$​ fruits?

​​

​​You can partition your basket into ​​$k$​ groups so that placing a fruit in a group indicates that you take a fruit of that type. This partitioning can be accomplished using ​​$k-1$​ bars as the boundaries. Then the number of configurations is the number of ways to place the ​​$n$​ fruits and ​​$k-1$​ bars in a sequence, or ​​$\binom{n+k-1}{n}$​.

​​

​​Example: a basket with capacity ​​$n=5$​ fruits and ​​$k=3$​ types of fruits: apples, oranges, and bananas.

​​   apples          oranges          bananas

​​    ●  ●      |             |      ●  ●  ●

​​

​​This is the same as the number of nonnegative integer solutions to ​​$n_{\text{apple}} + n_{\text{orange}} + n_{\text{banana}} = 5$​.

​​Summary

​​Selecting ​​$k$​ from ​​$n$​:

​​

​​	​​With replacement	​​Without replacement
​​Ordered	​​​​$n^k$​	​​​​$\frac{n!}{(n-k)!}$​ permutations
​​Unordered	​​​​$\binom{n+k-1}{n}$​	​​​​$\binom{n}{k}$​ combinations

​​Inclusion-exclusion

​​​​$| A \cup B | = |A| + |B| - |A \cap B|$​

​​Draw a Venn diagram.

​​