In Section 2.1 we investigated the most basic concept in combinatorics, namely, the rule of products. Even though in this section we investigate other counting formulas, it is of paramount importance to keep this fundamental process in mind. In Section 2.2 we saw that a subclass of rule-of-products problems appears so frequently that we gave them a special designation, namely, permutations, and we derived a formula as a computational aid to assist us. In this section we will investigate another counting formula that are used to count combinations, which are subsets of a certain size..

In many rule-of-products applications the permutation or order is important, as in the situation of the order of putting on one's socks and shoes; in some cases it is not important, as in placing coins in a vending machine or in the listing of the elements of a set. Order is important in permutations. Order is not important in combinations.

#####
Example2.4.1Counting Permutations

How many different ways are there to permute three letters from the set \(A = \{a, b, c, d\}\)? From the Permutation Counting Formula there are \(P(4,3)=\frac{4!}{(4-3)!} = 24\) different orderings of three letters from \(A\)

#####
Example2.4.2Counting with No Order

How many ways can we select a set of three letters from \(A = \{a, b, c, d\}\)? Note here that we are not concerned with the order of the three letters. By trial and error, abc, abd, acd, and bcd are the only listings possible. To repeat, we were looking for all three-element subsets of the set A. Order is not important in sets. The notation for choosing 3 elements from 4 is most commonly \(\binom{4}{3}\) or occasionally \(C(4,3)\), either of which is read “4 choose 3” or the number of combinations for four objects taken three at a time.

#####
Definition2.4.3Binomial Coefficient

Let \(n\) and \(k\) be nonnegative integers. The binomial coefficient \(\binom{n}{k}\) represents the number of combinations of \(n\) objects taken \(k\) at a time, and is read “\(n\) choose \(k\).”

We would now like to investigate the relationship between permutation and combination problems in order to derive a formula for \(\binom{n}{k}\)

Let us reconsider the Counting with No Order. There are \(3 ! = 6\) different orderings for each of the three-element subsets. The table below lists each subset of \(A\) and all permutations of each subset on the same line.
\begin{equation*}
\begin{array}{cc}
\textrm{subset} & \textrm{permutations} \\
\{a, b, c\} & abc,acb,bca,bac,cab,cba \\
\{a, b, d\} & abd,adb,bda,bad,dab,dba \\
\{a, c, d\} & acd,adc,cda,cad,dac,dca \\
\{b, c, d\} & bcd,bdc,cdb,cbd,dbc,dcb \\
\end{array}
\end{equation*}

Hence, \(\binom{4}{3} = \frac{P(4,3)}{3!} = \frac{4!}{(4-3)! \cdot 3!} = 4\)

We generalize this result in the following theorem:

#####
Theorem2.4.4Binomial Coefficient Formula

If \(n\) and \(k\) are nonnegative integers with \(0 \leq k \leq n\), then the number \(k\)-element subsets of an \(n\) element set is equal to \begin{equation*}\binom{n}{k} = \frac{n!}{(n-k)! \cdot k!} \end{equation*}

##### Proof

Proof 1: There are \(k!\) ways of ordering the elements of any \(k\) element set.Therefore,
\begin{equation*}\binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{(n-k)! k!}.\end{equation*}

Proof 2: To “construct” a permutation of \(k\) objects from a set of \(n\) elements, we can first choose one of the subsets of objects and second, choose one of the \(k!\) permutations of those objects. By the rule of products,\begin{equation*}P(n,k) = \binom{n}{k} \cdot k!\end{equation*} and solving for \(\binom{n}{k}\) we get the desired formula.

#####
Example2.4.5Flipping Coins

Assume an evenly balanced coin is tossed five times. In how many ways can three heads be obtained? This is a combination problem, because the order in which the heads appear does not matter. We can think of this as a situation involving sets by considering the set of flips of the coin, 1 through 5, in which heads comes up. The number of ways to get three heads is \(\binom{5}{3}= \frac{5 \cdot 4}{2 \cdot 1} = 10\).

#####
Example2.4.6Listing Five Flips, taking order into account

Determine the total number of ways a fair coin can land if tossed five consecutive times. The five tosses can produce any one of the following mutually exclusive, disjoint events: 5 heads, 4 heads, 3 heads, 2 heads, 1 head, or 0 heads. Hence by the law of addition we have:
\begin{equation*}\binom{5}{5}+\binom{5}{4}+\binom{5}{3}+\binom{5}{2}+\binom{5}{1}+\binom{5}{0}= 1 + 5 +10+10+5+1 = 32\end{equation*} ways to observe the five flips

Of course, we could also have applied the extended rule of products, and since there are two possible outcomes for each of the five tosses, we have \(2^5 = 32\) ways.

You might think that counting something two ways is a waste of time but solving a problem two different ways often is instructive and leads to valuable insights. In this case, it suggests a general formula for the sum
\(\sum_{k=0}^n \binom{n}{k}\). In the case of \(n = 5\), we get \(2^5\) so it is reasonable to expect that the general sum is \(2^n\), and it is.

#####
Example2.4.7A Committee of Five

A committee usually starts as an unstructured set of people selected from a larger membership. Therefore, a committee can be thought of as a combination. If a club of 25 members has a five-member social committee, there are \(\binom{25}{5}=\frac{25 24 23 22 21}{5!} = 53130\) different possible social committees. If any structure or restriction is placed on the way the social committee is to be selected, the number of possible committees will probably change. For example, if the club has a rule that the treasurer must be on the social committee, then the number of possibilities is reduced to \(\binom{24}{4}=\frac{24 23 22 21}{4!} = 10626\).

If we further require that a chairperson other than the treasurer be selected for the social committee, we have \(\binom{24}{4} \cdot 4 = 42504\) different possible social committees. The choice of the four non-treasurers accounts for the factor \(\binom{24}{4}\) while the need to choose a chairperson accounts for the 4.

#####
Example2.4.8Binomial Coefficients - Extreme Cases

By simply applying the definition of a Binomial Coefficient as a number of subsets we see that there is \(\binom{n}{0} = 1\) way of choosing a combination of zero elements from a set of \(n\). In addition, we see that there is \(\binom{n}{n} = 1\) way of choosing a combination of \(n\) elements from a set of \(n\).

We could compute these values using the formula we have developed, but no arithmetic is really needed here. Other properties of binomial coefficients that can be derived using the subset definition will be seen in the exercises

The binomial theorem gives us a formula for expanding \(( x + y )^{n}\), where \(n\) is a nonnegative integer. The coefficients of this expansion are precisely the binomial coefficients that we have used to count combinations. Using high school algebra we can expand the expression for integers from 0 to 5:

\begin{equation*} \begin{array}{cc}
n & (x + y)^n \\
0 & 1 \\
1 & x+y \\
2 & x^2+2 x y+y^2 \\
3 & x^3+3 x^2 y+3 x y^2+y^3 \\
4 & x^4+4 x^3 y+6 x^2 y^2+4 x y^3+y^4
\\
5 & x^5+5 x^4 y+10 x^3 y^2+10 x^2
y^3+5 x y^4+y^5 \\
\end{array}
\end{equation*}

In the expansion of \((x + y)^{5} \) we note that the coefficient of the third term is \(\binom{5}{3} = 10\), and that of the sixth term is \(\binom{5}{5}=1\). We can rewrite the expansion as
\begin{equation*}\binom{5}{0} x^5+\binom{5}{1} x^4 y+\binom{5}{2} x^3 y^2+\binom{5}{3} x^2 y^3+\binom{5}{4} x y^4+ \binom{5}{5} y^5
\end{equation*}

In summary, in the expansion of \(( x + y )^{n}\) we note:

The first term is \(x^n\) and the last term is \(y^n\).

With each successive term, exponents of \(x\) decrease by 1 as those of \(y\) increase by 1. For any term the sum of the exponents is \(n\).

The coefficient of \(x^{n-k} y^k\) is \(\binom{n}{k}\).

The triangular array of binomial coefficients is called Pascal's triangle after the seventeenth-century French mathematician Blaise Pascal. Note that each number in the triangle other than the 1's at the ends of each row is the sum of the two numbers to the right and left of it in the row above.

#####
Theorem2.4.9The Binomial Theorem

If \(n \geq 0\), and \(x\) and \(y\) are numbers, then
\begin{equation*}(x+y)^{n} = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k\end{equation*}

##### Proof

This theorem will be proven using a logical procedure called mathematical induction, which will be introduced in Chapter 3.

#####
Example2.4.10Identifying a term in an expansion

Find the third term in the expansion of \(( x-y )^{4}\). The third term, when \(k=2\), is \(\binom{4}{2} x^{4-2} y^2 = 6 x^2 y^2\).

#####
Example2.4.11A Binomial Expansion

Expand \((3 x - 2 )^{3}\). If we replace \(x\) and \(y\) in the Binomial Theorem with \(3x\) and \(-2\), respectively, we get
\begin{equation*}\begin{split}
\sum_{k=0}^3 \binom{3}{k} (3x)^{n-k} (-2)^k & = \binom{3}{0} (3x)^{3} (-2)^0 + \binom{3}{1} (3x)^{2} (-2)^1 + \binom{3}{2} (3x)^{1} (-2)^2 + \binom{3}{3} (3x)^{0} (-2)^3 \\
& = 27 x^3 - 54 x^2 + 36 x - 8
\end{split}
\end{equation*}

##### 1

The judiciary committee at a college is made up of three faculty members and four students. If ten faculty members and 25 students have been nominated for the committee, how many judiciary committees could be formed at this point ?

Answer \(C(10,3)\cdot C(25,4)=1,518,000\)

##### 2

Suppose that a single character is stored in a computer using eight bits.

a. How many bit patterns have exactly three 1's?

b. How many bit patterns have at least two 1's?

HintThink of the set of positions that contain a 1 to turn this is into a question about sets.

Solution(a) \(\binom{8}{3}\) (b) \(2^8-(\binom{8}{0}+\binom{8}{1})\)

##### 3

How many subsets of \(\{1, 2, 3, \dots , 10\}\) contain at least seven elements?

Answer \(C(10,7)+C(10,8)+C(10,9)+C(10,10)\)

##### 4

The congressional committees on mathematics and computer science are made up of five congressmen each, and a congressional rule is that the two committees must be disjoint. If there are 385 members of congress, how many ways could the committees be selected?

##### 5

Expand \( ( 2x - 3y )^4\).

Answer \(16x^4-96x ^3y+216x^2y^2-216x y^3+81y^4\)

##### 6

Find the fourth term of the expansion of \((x -2y)^6\).

##### 7

A poker game is played with 52 cards. At the start of a game, each player get five of the cards. The order in which cards are dealt doesn't matter.

How many “hands” of five cards are possible?

(b) If there are four people playing, how many initial five-card “hands” are possible, taking into account all players?

Answer
\(C(52,5)=2,598,960\)

\(C(52,5)\cdot C(47,5)\cdot C(42,5)\cdot C(37,5)\)

##### 8

A flush in a five-card poker hand is five cards of the same suit. How many spade flushes are possible in a 52-card deck? How many flushes are possible in any suit?

##### 9

How many five-card poker hands using 52 cards contain exactly two aces?

Answer\(C(4,2)C(48,3)\)

##### 10

In poker, a full house is three-of-a-kind and a pair in one hand; for example, three fives and two queens. How many full houses are possible from a 52-card deck? You can use the sage cell in the Sage Note to do this calculation, but also write your answer in terms of binomial coefficients.

##### 11

A class of twelve computer science students are to be divided into three groups of 3, 4, and 5 students to work on a project. How many ways can this be done if every student is to be in exactly one group?

Answer\(C(12,3)\cdot C(9,4)\cdot C(5,5)\)

##### 12

Explain in words why the following equalities are true based on number of subsets, and then verify the equalities using the formula for binomial coefficients.

\(\binom{n}{1} = n\)

\(\binom{n}{k} = \binom{n}{n-k}\), \( 0 \leq k \leq n\)

##### 13

There are ten points, \(P_1, P_2, \dots , P_{10}\) on a plane, no three on the same line.

How many lines are determined by the points?

How many triangles are determined by the points?

Answer
- \(C(10,2)=45\)
- \(C(10,3)=120\)

##### 14

How many ways can \(n\) persons be grouped into pairs when \(n\) is even? Assume the order of the pairs matters, but not the order within the pairs. For example, if \(n=4\), the six different groupings would be
\begin{equation*}\begin{array}{cc}
\{1,2\} & \{3,4\} \\
\{1,3\} & \{2,4\} \\
\{1,4\} & \{2,3\} \\
\{2,3\} & \{1,4\} \\
\{2,4\} & \{1,3\} \\
\{3,4\} & \{1,2\} \\
\end{array}
\end{equation*}

##### 15

Use the binomial theorem to prove that if \(A\) is a finite set, then
\(\lvert P(A)\rvert =2^{\lvert A \rvert}\)

Answer Assume \(\lvert A \rvert =n\). If we let \(x=y=1\) in the Binomial Theorem, we obtain \(2^n=C(n;0)+C(n;1)+\cdots +C(n;n)\), with the right side of the equality counting all subsets of \(A\) containing \(0, 1, 2, \dots , n\) elements. Hence \(\lvert P(A)\rvert =2^{\lvert A \rvert}\)

##### 16

A state's lottery involves choosing six different numbers out of a possible 36. How many ways can a person choose six numbers?

What is the probability of a person winning with one bet?

##### 17

Use the binomial theorem to calculate \(9998^3\).

Hint\(9998 = 10000-2\)

Answer \(1000^3 - 3 \cdot 2 \cdot 1000^2 +3 \cdot 2^2 \cdot 1000 - 2^3 = 999,400,119,992.\)

##### 18

In the card game Blackjack, there are one or more players and a dealer. Initially, each player is dealt two cards and the dealer is dealt one card down and one facing up. As in bridge, the order of the hands, but not the order of the cards in the hands, matters. Starting with a single 52 card deck, and three players, how many ways can the first two cards be dealt out? You can use the sage cell in the Sage Note to do this calculation.