Click to show/hide code
choose(n = 4, k = 2)[1] 6Combinatorics 2 - Combinations
1 Combinations
- A combination is a selection of objects from a larger set of objects where the order of selection does not matter (i.e., unordered selection).
1.1 Combinations without replacement
In the previous section, we discussed the motivational example of a set of \(4\) colored balls in a box: \(2\) red balls \((R_1, R_2)\), \(1\) blue ball \((B)\), and \(1\) green ball \((G)\).
We were interested in drawing two balls from the box without replacement.
If order matters, there are \(_4P_2 = \displaystyle \frac{4!}{(4-2)!} =12\) unique permutations of two balls.
If order does not matter, we counted \(6\) unique combinations of two balls (the remaining \(6\) combinations are duplicates because the order of selection does not matter). This number is obtained by dividing the number of ordered permutations \((12)\) by the number of ways the two balls can be arranged \((2)\) to give the number of unordered combinations.
1.1.1 Formula
To generalize the above rule, the number of ordered permutation of \(n\) objects taken \(r\) at a time is given by \(_nP_r = \displaystyle \frac{n!}{(n-r)!}\).
There are \(r!\) ways to arrange \(r\) objects, so the number of unordered \(r\) objects to be selected (without replacement) from the \(n\) objects is given as:
\[ _nC_r = \dbinom{n}{r} = \displaystyle \frac{_nP_r}{r!} = \displaystyle \frac{n!}{r!(n-r)!} \]
\(_nC_r\) is read as “\(n\) choose \(r\)”.
The expression \(\dbinom{n}{r}\) is referred to as the binomial coefficient, where \(n \geq r \ge 0\) (it is discussed in detail below).
1.1.2 Calculation in R
The number of combinations of unordered \(r\) objects to be selected (without replacement) from \(n\) objects can be calculated in
Rusing thechoose()function with argumentsnandk, wherenis the total number of objects andkis the number of objects to be selected.\(_4C_2\).
- How many different subsets of \(8\) books that can be selected from a total of \(15\) books?
Answer
The selection of the \(8\) books is an example of a combination without replacement (the order of the selected books does not matter and once a book is selected, it cannot be selected again).
The number of combinations is given as:
\[ _{15}C_8 = \dbinom{15}{8} = \displaystyle \frac{15!}{8!(15-8)!} = 6,435 \]
This can be calculated in
Ras follows:Click to show/hide code
choose(n = 15, k = 8)[1] 6435
A school is holding an election to form a student council. The council will consist of \(6\) members, and there are \(15\) students applying for the positions. The student can hold only one position on the, how many different combinations for the student council exist?
The answer is combinations.
Permutation of indistinguishable objects within distinct groups
In the previous section, we discussed the permutation of indistinguishable objects within distinct groups and explained the intuition behind the formula: \[ \frac{n!}{n_1! \times n_2! \times \ldots \times n_k!} \]
Another way to think about the formula is to make use of the concept of combinations.
Assume we are interested to find how many unique permutations that can be formed from the letters in the word BANANA.
There is a total of \(6\) letters, where the letter A appears \(3\) times, letter N appears \(2\) times, and letter B appears \(1\) time.
Step 1: - Assume we start with the \(3\) A’s to fill the available letter slots, where the order of them does not matter. The number of ways to choose \(3\) slots from \(6\) slots is \(_6C_3 = \dbinom{6}{3}\) and another \(3\) slots are still available.
Step 2: - Next, we use the \(2\) N’s to fill the \(3\) remaining slots, then the number of ways to choose \(2\) slots from \(3\) slots is \(_3C_2 = \dbinom{3}{2}\).
Step 3: - The remaining slot is filled with the letter B, then the number of ways to choose \(1\) slot from \(1\) slot is \(_1C_1 = \dbinom{1}{1}\).
Step 4: Using the multiplication principle to find the total number of unique permutations: \[ \dbinom{6}{3} \times \dbinom{3}{2} \times \dbinom{1}{1} = \frac{6!}{3! \cdot\ \cancel{3!}} \times \frac{\cancel{3!}}{2! \cdot\ \cancel{1!}} \times \frac{\cancel{1!}}{1! \cdot\ 0!} \]
\[ \frac{6!}{3! \cdot 2! \cdot 1!} \]
The above formula is identical to that derived earlier.
1.2 Combinations with replacement
Suppose we are interested in counting the number of combinations with replacement of \(5\) letters that can be formed from the letters \(\{A, B, C\}\).
The letters can be selected once, more than once, or not at all to form the \(5\)-letter combinations but the order of letters does not matter.
Let’s list all the possible combinations allowing for replacement:
\(1.\ AAAAA\)
\(2.\ AAAAB\)
\(3.\ AAAAC\)
\(4.\ AAABB\)
\(5.\ AAABC\)
\(6.\ AAACC\)
\(7.\ AABBB\)
\(8.\ AABBC\)
\(9.\ AABCC\)
\(10.\ AACCC\)
\(11.\ ABBBB\)
\(12.\ ABBBC\)
\(13.\ ABBCC\)
\(14.\ ABCCC\)
\(15.\ ACCCC\)
\(16.\ BBBBB\)
\(17.\ BBBBC\)
\(18.\ BBBCC\)
\(19.\ BBCCC\)
\(20.\ BCCCC\)
\(21.\ CCCCC\)
There are \(21\) possible combinations of \(5\) letters that can be formed from the letters \(\{A, B, C\}\) with replacement and without regard to the order.
1.2.1 Formula
To derive a general rule, we will make use of a concept referred to as stars and bars.
We will consider each letter as a star (\(\bigstar\)) that can be selected once, more than once, or not at all to form the \(5\)-letter combinations. Therefore, we have \(5\) stars.
We will use bars \((|)\) to separate the stars into three groups corresponding to the three letters \(\{A, B, C\}\). Therefore, we have \(2\) bars.
For example, the following table shows some of the possible \(5\)-letter combinations and their corresponding stars and bars representation:
| Combination | Representation |
|---|---|
| \(AAABC\) | \(\bigstar\bigstar\bigstar \big|\bigstar \big|\bigstar\) |
| \(ABBCC\) | \(\bigstar \big|\bigstar\bigstar \big|\bigstar\bigstar\) |
| \(ACCCC\) | \(\bigstar \big| \quad \big| \bigstar\bigstar\bigstar\bigstar\) |
| \(BBCCC\) | \(\quad \big| \bigstar\bigstar \big| \bigstar\bigstar\bigstar\) |
| \(CCCCC\) | \(\quad \big| \quad \big| \bigstar\bigstar\bigstar\bigstar\bigstar\) |
For example:
The combination \(AAABC\) is represented by \(3\) stars in the first group, \(1\) star in the second group, and \(1\) star in the third group.
When a letter is skipped such as in the combination \(ACCCC\), no star is placed in the corresponding group, so this combination is represented by \(1\) star in the first group, no stars in the second group, and \(4\) stars in the third group.
The common factor between the representations is that the total number of stars is \(5\) and the total number of bars is \(2\) resulting in a total of \(7\) objects.
The problem is now reduced to counting the number of ways to choose \(5\) objects (stars) from a total of \(7\) objects.
If we denote the number of objects to be selected (i.e., stars) as \(m\) and the number of categories (i.e., letters) as \(n\), you notice that the total number of objects (i.e., stars and bars) is \((n+m-1)\).
The number of combinations with replacement is given as:
\[ _{n+m-1}C_m = \dbinom{n+m-1}{m} = \displaystyle \frac{(n+m-1)!}{m!(n-1)!} \]
Alternatively, we can count the number of ways to choose \(2\) bars from a total of \(7\) objects, so the number of combinations with replacement can also be calculated as:
\[ _{n+m-1}C_{n-1} = \dbinom{n+m-1}{n-1} = \displaystyle \frac{(n+m-1)!}{m!(n-1)!} \]
Note
\(\dbinom{n+m-1}{m} = \dbinom{n+m-1}{n-1} = \displaystyle \frac{(n+m-1)!}{m!(n-1)!}\)
This equivalence is due to the symmetry of the binomial coefficient.
Other properties of the binomial coefficient are discussed below.
In the example above, \(m = 5\) and \(n = 3\), so the number of combinations with replacement is given as:
\[ \dbinom{3+5-1}{5} = \dbinom{3+5-1}{3-1} = \displaystyle \frac{(3+5-1)!}{5!(3-1)!} = \displaystyle \frac{7!}{5! \cdot 2!} = 21. \]
2 Binomial Coefficient
The expression \(\dbinom{n}{r}\) is referred to as the binomial coefficient because it arises in the expansion of binomial expressions.
Let’s try to expand the expression \((x+y)^3\):
\[ (x+y)^3 = \stackrel{1}{\boxed{(x+y)}} \cdot \stackrel{2}{\boxed{(x+y)}} \cdot \stackrel{3}{\boxed{(x+y)}}\ = \]
\[ x^3 + 3x^2y + 3xy^2 + y^3 \]
To expand the expression, we multiply one term from each of the three boxes, for instance, \((x) \cdot (x) \cdot (y)\) to get \(x^2y\), \((x) \cdot (y) \cdot (y)\) to get \(xy^2\), and so forth.
As you notice, there are \(3\) slots to fill with \(x\) or \(y\) during each multiplication.
When we choose \(3\ x's\) to multiply, there are no slots left for \(y's\) and we get \(x^3\). There is only \(1\) way to choose the \(3\ x's\) or \(0\ y's\) from the boxes \([(x) \cdot (x) \cdot (x)]\).
When we choose \(2\ x's\), there is only \(1\) slot left for \(y's\). We get \(x^2y\) but there are \(3\) ways to choose the \(2\ x's\) or \(1\ y\) from the boxes \(\Big[ \Big( (x) \cdot (x) \cdot (y) \Big), \Big( (x) \cdot (y) \cdot (x) \Big), \Big( (y) \cdot (x) \cdot (x) \Big) \Big]\)resulting in \(3x^2y\).
When we choose \(1\ x\), there are \(2\) slots left for \(y's\). We get \(xy^2\) but there are \(3\) ways to choose the \(1\ x\) or \(2\ y's\) from the boxes \(\Big[ \Big( (x) \cdot (y) \cdot (y) \Big), \Big( (y) \cdot (x) \cdot (y) \Big), \Big( (y) \cdot (y) \cdot (x) \Big) \Big]\) resulting in \(3xy^2\).
When we do not choose any \(x\), there are \(3\) slots left for \(y's\) and we get \(y^3\). There is only \(1\) way to choose the \(0\ x's\) or \(3\ y's\) from the boxes \([(y) \cdot (y) \cdot (y)]\).
To generalize, consider the expansion of the binomial expression \((x+y)^n\):
\[ (x+y)^n = \stackrel{1}{\boxed{(x+y)}} \cdot \stackrel{2}{\boxed{(x+y)}} \ldots \stackrel{n}{\boxed{(x+y)}}\ \]
There are \(n\) slots to fill with \(x\) or \(y\).
Let \(r\) be the slots be filled with \(y's\), where \(r\) can take values from \(0\) to \(n\).
Then, the slots filled with \(x's\) will be \(n-r\).
The number of ways to choose \(r\) slots of \(y's\) or \((n-r)\) slots of \(x's\) from the boxes is given as \(\dbinom{n}{r}\).
So, for each \(r\) from \(0\) to \(n\), the resulting term in the expansion is \(\dbinom{n}{r}x^{(n-r)} y^r\):
\[ (x+y)^n = \dbinom{n}{0}x^{(n-0)} y^0 + \dbinom{n}{1}x^{(n-1)} y^1 + \ldots + \dbinom{n}{n}x^{(n-n)} y^n = \]
\[ \boxed{\displaystyle \sum_{r=0}^n \dbinom{n}{r}x^{(n-r)} y^r} \]
- Expand the expression \((x+y)^4\).
Answer
\[ (x+y)^4 = \displaystyle \sum_{r=0}^4 \dbinom{4}{r}x^{(4-r)} y^r = \] \[ \dbinom{4}{0}x^{(4-0)} y^0 + \dbinom{4}{1}x^{(4-1)} y^1 + \dbinom{4}{2}x^{(4-2)} y^2 + \]
\[ \dbinom{4}{3}x^{(4-3)} y^3 + \dbinom{4}{4}x^{(4-4)} y^4 = \]
\[ x^4+ 4x^3 y + 6x^2 y^2 + 4x y^3 + y^4 \]
2.1 Properties of the binomial coefficient
The binomial coefficient has the following properties:
\(\dbinom{n}{r} = \dbinom{n}{n-r}\)
\(\dbinom{n}{0} = \dbinom{n}{n} = 1\)
\(\dbinom{n}{1} = \dbinom{n}{n-1} = n\)
\(\dbinom{n}{r} = \dbinom{n-1}{r-1} + \dbinom{n-1}{r}\)
\(\dbinom{n}{r} = \displaystyle \prod_{i=1}^r \frac{n+1-i}{i}\)
3 References
Heumann, C., Schomaker, M., and Shalabh (2022). Introduction to Statistics and Data Analysis: With Exercises, Solutions and Applications in R. Springer
Daniel, W. W. and Cross, C. L. (2013). Biostatistics: A Foundation for Analysis in the Health Sciences, Tenth edition. Wiley
Penn State University. STAT 414: Introduction to Probability Theory. Online Statistics Education. Retrieved December 02, 2024, from https://online.stat.psu.edu/stat414