Combinatorics
Combinatorics are methods for counting and arranging sets.
Contents
Multiplication Principle of Counting
If event A has a possible outcomes and event B has b possible outcomes, then events A and B together have ab possible outcomes.
The number of subsets of a set is equal to the product of the number of outcomes for the binary inclusion events (in subset or not in subset) for each member. These binary events clearly have 2 possible outcomes each. For a set of k members, there are 2k possible subsets.
More generally, when selecting with replacement from a set (i.e., a member can be re-selected) of n members, there are n possible outcomes for each selection. If there are k selections, then there are total nk possible outcomes.
When selecting without replacement, the number of possible outcomes decrements with each selection. If there are n members, then the first selection has n possible outcomes, the second has n-1 possible outcomes, and so on. There are n! (factorial) possible outcomes.
If some number of the possible outcomes are indistinguishable from another, the number of distinguishable outcomes is equal to the number of possible outcomes divided by the number of indistinguishable outcomes. In other words, while counting is multiplicative, discounting is divisive.
Permutations
As stated above, if there are n members and they are selected without replacement exhaustively, then there are n! (factorial) possible outcomes. If only the first k selections are distinguishable however, then the number of unexhausted selections must be divided as they are indistinguishable. Clearly there are n-k unexhausted selections.
This is variably notated as P(n,k), Pnk, or nPk.
Note that if n = k, then (n-k)! = 0! = 1. So the above formulation for an exhaustive selection without replacement holds.
Combinations
As described by the permutation, if k selections are made without replacement from n members, then the number of distinguishable outcomes is equal to the number of possible outcomes divided by the number of indistinguishable outcomes (i.e., those resulting from unexhausted selections). If there is no ordering however, then there are further indistinguishable outcomes that must be divided out.
For one (or zero) selections, there is only one possible ordering and every possible outcome is distinguishable. For two selections, there are clearly two possible orderings that are indistinguishable by ordering. For three selections, there are six. The number of indistinguishable outcomes is dependent on the number of selections (k) not the number of members. Specifically, there are k! indistinguishable outcomes.
The C(n,k) notation is shown for consistency, and there are parallel notations like Cnk and nCk, but there are all much less conventional than the (kn) notation.
Intuitively, there are 3 ways to choose 2 from a set of 3 (e.g., {A,B,C}). These choices are A and B; B and C; A and C. Plugging n=3 and k=2 into the equation also yields the expected result.
Properties
Combinations have a symmetric property:
Pascal's rule states that:
This is proven by expanding out the RHS as:
Simplify while factoring out the (n-1)! term from both numerators.
Now multiply the fractions to achieve equal denominators.
Add, simplify, reincorporate the (n-1)! term, and observe that the RHS now is equal to the LHS.
Multinomials
Selecting k from n elements is equivalent to splitting n elements between two groups, with the first group having k assignments and the second having n-k assignments.
More generally, let n elements be split into k groups. The respective numbers of assignments are notated as n1, n2, and so on up to nk. The number of possible assignments is given as:
Note that if k = 2, then n2 = n - n1 and the above formula simplifies to:
...which clearly is equivalent to the combination of choose k = n1 from n.