counting

Counting

Overview

There are variety of ways to explore counting problems with your imagination. The following questions are helpful in searching for a solution.

does order matter?
can items be repeated?
is it easier to think in terms of items?
is it easier to think in terms of object state?
is it easier to think in terms of groups of items?
is it easier to think in terms of containers/partitions?
is it easier to count different groups and add them together?
is it easier to find the opposite of the thing you are trying to count i.e. subtract from the total?

The Product Rule

The product rule is used for counting objects whose subparts combine freely with one another.

if there are $n_1$ ways to do the first task, and $n_2$ ways to do the second task, then there $n_1 \cdot n_2$ ways to do the procedure
AKA Cardinality of the Cartesian product of two sets. For example, $|A \times B| = |A| \cdot |B|$, because all the “subparts of $A$ and $B$ combine freely” to form the ordered pairs. In general $|A_1 \times A_2 \times \dots \times A_n| = |A_1| \cdot |A_2| \cdot \dots \cdot |A_n|$.

The Sum Rule

The sum rule is used for counting objects whose subparts do not overlap.

if a task can be done either in one of $n_1$ ways or in one of $n_2$ ways, where none of the set of $n_1$ ways is the same as any of the set of $n_2$ ways, then there are $n_1 + n_2$ ways to do the task.
Cardinality of the union of two sets when their “subparts do not overlap.” i.e. $|A \cup B| = |A| + |B|$ where $A \cap B = \emptyset$.
If $A_1, A_2, \dots, A_m$ are pairwise disjoint finite sets, then the number of elements in the union of these sets is the sum of the numbers of elements in the sets. There are $|A_i|$ ways to choose an element from one of the sets $A_i$ for $i = 1, 2, \dots, m$. Because the sets are pairwise disjoint, when we select an element from a different set $A_j$. Since we cannot select an element from two sets at the same time: $|A_1 \cup A_2 \cup \dots \cup A_m| = |A_1| + |A_2| + \dots + |A_m| \text{ when } A_i \cap A_j = \text{ for all } i, j$.

The Subtraction Rule

for counting objects whose subparts do overlap
AKA principle of inclusion-exclusion
If a task can be done in either $n_1$ ways or $n_2$ ways, then the number of ways to do the task is $n_1 + n_2$ minus the number of ways to do the task that are common to the two different ways.
$|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|$
Consider $|A \cup B|$ when $|A|$ and $|B|$ are not necessarily disjoint.

\[ \begin{gather} A = \{a,b,c,d,e,f,g\}\\ B = \{e,f,g,h,i,j\}\\ A \cup B = \{a,b,c,d,e,f,g,h,i,j\}\\ A \cap B = \{e,f,g\}\\ |A \cup B| = |A| + |B| - |A \cap B| = 7 + 6 - 3 = 10 \end{gather} \]

Extension to three sets:

\[ |A \cup B \cup C| = |A| + |B| + |C|\\ - |A \cap B| - |A \cap C| - |B \cap C|\\ + |A \cap B \cap C| \]

The reason that you add the intersection of all three back is because you subtracted elements that are common to all three sets twice. Element $a_1$ that is in $A \cap B \cap C$ is also in $A \cap B$ and $A \cap C$ and so is subtracted twice.

Generalization of Inclusion-exclusion

the pattern exhibited by the two and three set cases is followed i.e. subtracting the pairwise intersections, adding the three-wise intersection, etc.
if $n$ is even then the last operation will be subtraction of the $n$-wise intersection
if $n$ is odd then the last operation will be the addition of the $n$-wise intersection

The Division Rule

There are $n/d$ ways to do a task if it can be done using a procedure that can be carried out in $n$ ways, and for every way $w$, exactly $d$ of the $n$ ways correspond to way $w$.
“If the finite set $A$ is the union of $n$ pairwise disjoint subsets each with $d$ elements, then $n = |A|/d$.”
“If $f$ is a function from $A$ to $B$ where $A$ and $B$ are finite sets, and that for every value $y \in B$ there are exactly $d$ values $x \in A$ such that $f(x) = y$ (in which case, we say that $f$ is $d$-to-one), then $|B| = |A|/d$.”

How many different ways are there to seat four people around a circular table, where two seatings are considered the same when each person has the same left neighbor and the same right neighbor?

We arbitrarily select a seat at the table and lable it seat $1$. We number the rest of the seats, proceeding clockwise. Note that there are four ways to select the person for seat $1$, three ways for seat $2$, etc. Thus, there are $4! = 24$ ways to order the given four people for these seats. However, each one of the four choices for seat $1$ leads to the same arrangement (same left neighbor, same right neighbor). Because there are four ways to choose the person for seat $1$, by the division rule there are $24/4 = 6$ different seating arrangements of four people around the circular table.

Examples

How many three letter initial combinations are there?

Use the product rule: $26 \cdot 26 \cdot 26$

If license plates can be DDDLLL or LLLDDD where D $\in \{0 \dots 9\}$ and L $\in \{A \dots Z\}$, how many license plates are possible?

Use rule of product to find that $10 \cdot 10 \cdot 10 \cdot 26 \cdot 26 \cdot 26 = 10^3 \cdot 26^3$ of the first type are possible, and that $26 \cdot 26 \cdot 26 \cdot 10 \cdot 10 \cdot 10$ of the second type are possible.
Use the rule of sum to add the two together to find that $35,152,000$ variations are possible.

How many bit strings are there of length $n$?

There are two possibilities for each so that the total can be expressed as $2^n$

A system accepts passwords of length 3 and 4 consisting of 26 lower case letters, 26 capital letters, and the 10 digits 0-9. What is the total possible number of passwords?

Use the rule of product to find There are $(26 + 26 + 10)^3$ passwords of length $3$ and $(26 + 26 + 10)^4$ passwords of length $4$
Use the rule of sum to add these together to find that there are $62^3 + 62^4 = 15,014,664$

How many functions are there from a set with $m$ elements to a set with $n$ elements?

Every $m$ can choose from one of the $n$ elements therefore there are $n \cdot n \cdot \dots \cdot n = n^m$ functions.

How many one-to-one functions are there from a set with $m$ elements to one with $n$ elements?

Consider that $m \leq n$ must be true. There are $n(n - 1)(n - 2) \dots (n - m + 1)$ ways to choose.

What is the value of $k$ at the end of this loop?

k := 0
for i1 := 1 to n1
  for i2 := 1 to n2
    .
    .
    .
  for im := 1 to nm
    k := k + 1

The final value of $k$ is $n_1 \cdot n_2 \dots n_m$.

Use the product rule to show that the numberof different subsets of a finite set $S$ is $2^{|S|}$.

For each set an element may be present or not present (2 choices) so we use the product rule to find that there are $2^{|S|}$ subsets.

What is the value of $k$ after the following code has been executed?

k := 0
for i_1 := 1 to n_1
  k := k + 1
for i_2 := 1 to n_2
  k := k + 1
    .
    .
    .
for i_m := 1 to n_m
  k := k + 1

The value $k$ after the code has been executed is $n_1 + n_2 + \dots + n_m$.

How many bit strings of length eight either start with a $1$ bit or end with the two bits $00$?

There are $2^7$ ways to create a bit string that starts with a one bit. This follows from 1 choice $\times 2 \times 2 \dots$. There are $2^5$ ways to create a bit string that ends with in $00$. This follows from 1 choice $\times$ 1 choice $\times 2 \cdot 2 \dots$. The number of ways to construct a bit string common to both is $2^5$. Subtract the common set from both to get $128 + 64 - 32 = 160$.

Imagine $24$ textbooks on computer science: $8$ of them cover assemblers (A); $13$ of them cover binary trees (B); $13$ of them cover complexity (C). $5$ of them cover assemblers and binary trees; $3$ of them cover assemblers and complexity; $6$ of them cover binary trees and complexity; $2$ of them cover assemblers, b-trees, complexity.

How many of the books include material on exactly one of the topics?
How many books do not deal with any of the topics?

\[ |A| = 8, |B| = 13, |C| = 13\\ |A \cap B| = 5, |A \cap C| = 3, |B \cap C| = 6\\ |A \cap B \cap C| = 2 \]

Using the notation $|eA|$ for “cardinality of exactly $A$,” and so on we have the following:

\[ |eA| = |A| - |A \cap B| - |A \cap C| + |A \cap B \cap C| = 2 |eB| = |B| - |A \cap B| - |B \cap C| + |A \cap B \cap C| = 4 |eC| = |C| - |A \cap C| - |B \cap C| + |A \cap B \cap C| = 6 \]

Adding $2 + 4 + 6$ tells us that exactly 12 books include material on exactly one topic.

To answer (2) we reason as follows. There are $24$ books altogether. The number of them dealing with the topics in question are $|A \cup B \cup C|$, so we want $24 - |A \cup B \cup C|$. $|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$. If we plug in the numbers we will get $8 + 13 + 13 - 5 - 3 - 6 + 2 = 22$. $24 - 22 = 2$. Thus there are $2$ books that do not deal with any of the topics.

In a survey of 270 people it is found that 64 liked Art, 94 liked Baseball, and 58 liked Classical music. Also, 26 liked both Art and Baseball, 28 liked both Art and Classical music, and 22 liked Baseball and Classical music. Finally, 14 liked Art, Baseball and Classical music. Of the 270, how many do not like any of these pastimes?

There are three sets such that $|A| = 64, |B| = 94, |C| = 58$. The intersections are $|A \cap B| = 26, |A \cap C| = 28, |B \cap C| = 22, |A \cap B \cap C| = 14$. The sum of those who like at least one of the pastimes is $(|A| + |B| + |C|) - (|A \cap B| + |A \cap C| + |B \cap C|) + |A \cap B \cap C| = 154$. Subtract this from the total surveyed to find those who did not like any of the pasttimes $270 - 154 = 116$

Tree Diagrams

used to solve counting problems
a tree consists of a root, branches, and leaves
branches represent different choices and leaves represent outcomes

Permutations

when order matters and elements cannot be repeated
a permutation is a way of ordering elements (an ordered arrangement) in a set where each arrangement is some specified length $r$ with no elements repeated in a given arrangement. E.g., Let $S = \{a, b, c\}$, then $bca$, $bac$, etc. are permutations of $S$
Given $S$, An r-permutation is a way of ordering $r$ elements of the set. E.g., $bc$ is a 2-permutation of $\{a,b,c\}$.
In general there are $n!/(n-r)!$ $r$-permutations of a set of size of $n$, denoted $P(n,r)$.
$P(n, n) = n!$
$P(n, 1) = n$

Examples

How many $3$-permutations of $\{a,b,c\}$ are there?

$P(3, 3) = 3 \cdot 2 \cdot 1 = \frac{3!}{(3 - 3)!} = 3! = 6$.

How many $7$-permutations of the English alphabet?

$P(26, 7) = 26 \cdot 25 \cdot \dots \cdot 20 = 26!/(26-7)!$ or $26!/19!$.

How many ways can we select three students from a group of five to stand in line for a picture?

$P(5, 3) = 5 \cdot 4 \cdot 3 = \frac{5!}{(5 - 3)!} = 60$

In a race of $12$ greyhounds, how many possible $1$-$2$-$3$- finishes are there?

$P(12,3) = \frac{12!}{(12-3)!} = 12 \cdot 11 \cdot 10 = 1320$

A salesman must visit eight different cities. If the first city is chosen, how many possibles orders can be used when visiting the remaining cities?

$P(7, 7) = \frac{7!}{(7 - 7)!} = 7! = 5040$

How many permutations of the letters ABCDEFGH contain the string ABC?

Treat the block as a single object to get $P(6, 6) = \frac{6!}{(6 - 6)!} = 720$.

There are six different candidates for an elected office. In how many different orders can the names of the candidates be printed on a ballet? In how many different orders can the names be printed if one of the six is the incumbent and her name is always first. Same as above except the incumbent’s name can never be listed first.

$P(6, 6) = \frac{6!}{(6 - 6)!} = 6!$
The first choice is made and $5$ remain, $P(5, 5) = \frac{5!}{(5 - 5)!}$
Subtract the number of permutations where the candidate is first from the total permutations: $6! - 5!= 600$ or $5 \cdot 5! = 600$

Permutations with Repetition

when repetition is allowed the number of $r$-permutations of a set of $n$ objects is $n^r$

Examples

How many strings of length $r$ can be formed from the uppercase letters of the English alphabet?

By the product rule $26^r$

Permutations with Indistinguishable Objects

when order matters
without repetition
a mix of types of elements where each type may be of varying number but exhaustable e.g. ‘SUCCESS’ consists of 4 types where ‘S’ is a type quantity 3, ‘C’ a type with quantity 2, etc.
the number of different permutations of $n$ objects, where there are $n_1$ indistinguishable objects of type 1, $n_2$ indistinguishable objects of type 2, $\dots$, and $n_k$ indistinguishable objects of type $k$, is

\[ \frac{n!}{n_1! n_2! \dots n_k!} \] - may also be treated as a sum of combinations as in the example below:

Examples

How many different strings can be made by reordering the letters of the word ‘SUCCESS’?

The three ’S’s can be placed among seven positions $C(7, 3)$ leaving four positions.
The two ’C’s can be placed in $C(4, 2)$ ways, leaving two positions.
The ‘U’ can be placed in $C(2, 1)$ ways, leaving a single position.
The ‘E’ can be placed in $C(1, 1)$ way.
Consequently from the product rule we have $C(7, 3) \cdot C(4, 2) \cdot C(2, 1) \cdot C(1, 1) = \frac{7!}{3! 4!} \cdot \frac{4!}{2! 2!} \cdot \frac{2!}{1! 1!} \cdot \frac{1!}{1! 0!} = \frac{7!}{3! 2! 1! 1!} = 420$

Combinations

Given the permutations $P(20, 5) = 1,860,480$, we can divide this by the permutations for $5$ (the different ways in which we can select the $5$), $P(5, 5) =20$ to get the combinations $C(20, 5)$.

when order doesn’t matter e.g. $ab$ is the same as $ba$ in contrast to permutations
an r-combination of elements of a set is an unordered selection of $r$ elements from the set.
there are more permutations for a set of elements than combinations
$C(n, r) = \frac{P(n, r)}{r!} = \frac{n!}{(n - r)!r!} = \frac{n(n - 1)(n - 2)(\dots)(n - r)}{r!}$
$C(n, r) = C(n, n - r)$—this means at $C(9, 2) = C(9, 7)$
$C(n, 1) = n$ e.g. $C(10, 1) = 10$
$C(n, n) = C(n, 0) = 1$ e.g. $C(10, 10) = C(10, 0) = 1$

There are a few different ways to express a combination. With combinations of $2$ elements from a set of $4$ elements we may say:

How many subsets of size $2$ can be chosen from a set of size $4$?
How many $2$-combinations of a set of $4$ objects?
What is $C(4,2)$?
What are $4$ things taken $2$ at a time?
What is $4$ take $2$?
What is ${4 \choose 2}$ “$4$ choose $2$”—This is called a binomial coefficient
${}_4 Cr_2$

Examples

Four people a, b, c, d, sit around the table and toast the New Year, each clinking glasses with the others. How many clinks?

If the people are the set $\{a, b, c, d\}$ then the clinks are between $ab$, $ac$, $ad$, $bc$, $bd$, and $cd$, or $6$ altogether. This is $C(4, 2) = \frac{4!}{(4 - 2)!2!} = 6$

How many different committees of three students can be formed from a group of four students?

one set for each student who is left out, $4$, or $\frac{4!}{(4 - 3)!}3! = 4$
Let $S = \{a, b, c, d\}$, $C(4, 3) = 4!/(4 - 3)!3! = 4$

How many possible bridge hands may be dealt from a deck of cards (a deck is $52$ and a hand is $13$ cards)?

$C(52,13) = \frac{52!}{(52 - 13)!13!} = \frac{52!}{39!13!}$

Suppose from a pool of $10$ men and $15$ women we want to form a committee of size $6$ consisting of $3$ men and $3$ women. How many ways are there to form such a committee?

There are $C(10,3)$ ways to choose the men, and $C(15,3)$ ways to choose the women. These choices are independent so the rule of product is used and the answer is $C(10,3) \cdot C(15,3)$.

How many bit strings of length $10$ contain at most $2$ zeros?

Break into nonoverlapping subcases and use the rule of sum.

There are $C(10, 2) = 45$ ways to get exactly $2$ zeros.
There are $C(10, 1) = 10$ ways to get exactly $1$ zeros.
There are $C(10, 0) = 1$ ways to get exactly $0$ zeros.
The sum of these numbers is the number of ways to arrive at “at most $2$ zeros,” which is $56$.

A nationwide pizza chain offers $17$ toppings from which you may choose to have $0$, $1$, $2$, or $3$ on your pizza. How many distinct pizzas do they offer assuming no doubling up of toppings? (i.e., no “extra” pepperoni.)

$C(17,0) + C(17,1) + C(17,2) + C(17,3) = 1 + 17 + 136 + 680 = 834$

The alphabet contains $21$ consonants and $5$ vowels. How many strings of $6$ letters contain exactly $2$ vowels?

This is two problems…
We can find the available positions for vowels with $C(6, 2)$ in other words this is the number of ways we can arrange vowels and consonants This is a combination because we don’t differentiate between a vowel in positions $2$ and $4$ and a vowel in positions $4$ and $2$. If there was one vowel and one consonant there would be $15$ such strings.
There are $2$ positions to choose for vowels with repetition allows so there are $5^2$ possibilities for choosing vowels
There are $4$ positions left to choose any of $21$ consonants so there are $21^4$ possibilities for choosing consonants
Therefore there are $C(6, 2) \cdot 5^2 cdot 21^4$ possible arrangements

How many poker hands of five cards can be dealt from a standard deck of $52$ cards? How many ways are there to select $47$ cards from a standard deck of $52$ cards?

There are $C(52, 5) = 2,598,960$ different poker hands that can be dealt from a standard deck of $52$ cards.
It turns out that $C(52, 47) = \frac{52!}{(52 - 47)47!} = C(52, 52 - 47) = C(52, 5)$, so there are also $2,598,960$ different ways to select $47$ cards from a deck of $52$ cards.

How many possibilities for a group of $4$ pizzas individually topped (up to $3$ toppings chosen from $17$)

You may choose up to $3$ toppings therefore there $C(17, 3) + C(17, 2) + C(17, 1) + C(17, 0)$ types of pizzas.
You may choose the same $4$ pizzas, $2$ of the same, etc.; If you decide on just three different pizzas, then you have $C(834, 3)$ to choose from, and since the fourth pizza is one of those three, the total possibilities for three different pizzas is $C(3, 1) \cdot C(834, 3)$. If you decide on just two different pizzas you have $C(834, 2)$ to choose from and there are three ways to arrange the four of them, namely X Y Y Y, X X X Y, and X X Y Y, assuming pizza types X and Y, so add in $3 \cdot C(834, 2)$ . Finally if everyone wants the same kind of pizza we have $C(834, 1)$. therefore, there are $C(834, 4) + C(3, 1) \cdot C(834, 3) + C(3, 1) \cdot C(834, 2) + C(834, 1) = 20,303,598,645$ possible choices.

What is the number of full houses in a deck of cards? What is the probability of a full house?

There are $13$ suits so we must chose one suit for the three of a kind and one for the two of a kind. Therefore, there are $13 \cdot 12$ permutations—order matters (though not necessarily explicitly mentioned) because order signifies whether the suit is for the two of a kind or the three of a kind.
Another way to think about it is that we pick a suit for the three of a kind and three cards from that suit, then we pick a suit for the two of a kind and choose two cards from that suit.
Therefore, there are $13 \cdot 12 \cdot C(4, 3) \cdot C(4, 2) = 3,744$ full houses in a deck
The total number of hands is $C(52, 5)$ so the probability of getting a full house is $\frac{3,744}{C(52, 5)}$

Combinations with Repetition

combination with repetition of element allowed
a multiset is a “set” in which repeated elements are permitted and counted. E.g., $\{a,a,b,b,c\}$ is a multiset of size 5. The elements of a multiset are not ordered, just like an ordinary set. Thus $\{a, a, b, b, c\} = \{a, b, a, b, c\} = \{c, b, b, a, a\}$, etc. Note that a set is a multiset under this definition that happens not to have repeated elements.
there are $C(n + r - 1, r) = C(n + r - 1, n - 1) r$-combinations from a set with $n$ elements when repetition of elements is allowed i.e. a multiset

Examples

How many ways are there to select five bills from a cash box containing $1, $2, $5, and $10 bills? The order in which the bills are chosen doesn’t matter, and the bills of each denomination are indistinguishable.

This involves counting $5$-combinations with repetition allowed from a set of $4$ elements.
The way to count this is by using bars to represent dividers for different bill types, and stars that represent bills.
This means $5$ stars and $3$ dividers.
So the problem is now about finding unique arrangements for stars and bars:

*|**|**|  - 1 x $1, 2 x $2, 2 x $5, 0 x $10
*****||| - 5 x $1, 0 x $2, 0 x $5, 0 x $10

Consequently, the number of ways to select five bills corresponds to the ways to select the positions of the five stars from the 8 positions, which can be done in $C(4 + 5 - 1, 5) = C(8, 5) = 56$

Given a bag full of donuts of three types. How many ways are there to choose a dozen donuts from the bag. (For example, 10 glazed, 1 chocolate, 1 plain, or 4 of each, etc.)

In this case the set has $3$ elements and we are being asked how many multisets of size $12$ may be formed, so $r = 12$, and of course $n = 3$. Therefore, the answer is $C(3 + 12 - 1, 12) = C(14, 12) = 91$.

Given four different kinds of cookies, how many different ways can six cookies be chosen? Only the type of cookie matters and not the individual cookies or order in which they are chosen.

$C(4 + 6 - 1, 6) = C(9, 6) = 84$

Given a bag of fruit containing apples, oranges, and bananas, how many ways are there of selecting four pieces of fruit?

$C(3 + 4 - 1, 4) = C(6, 4) = 15$

Binomial Theorem

the binomial theorem gives the coefficients of the expansion of powers of binomial expressions
a binomial expression is simply the sum of two terms, such as $x + y$.
$(x + y)^n = \sum_{i = 0}^{n} C(n, i)x^{n - i}y^i = \sum_{j = 0}^{n} {n \choose j} x^{n - j}y^j = {n \choose 0} x^n + {n \choose 1} x^{n - 1} y + \dots + {n \choose n - 1} x y^{n - 1} + {n \choose n}y^n$
e.g. $(x + y)^3 = C(3, 0)x^3y^0 + C(3, 1)x^2y^1 + C(3, 2)x^1y^2 + C(3, 3)x^0y^3 = x^3 + 3x^2y + 3xy^2 + y^3$

\[ (x + y)^3 = (x + y)(x + y)(x + y)\\ = (xx + xy + yx + yy)(x + y)\\ = xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy\\ = x^3 + 3x^2y + 3xy^2 + y^3 \]

Let $n$ be a nonnegative integer, then

\[ \sum_{k = 0}^n {n \choose k} = 2^n \]

Let $n$ be a positive integer, then

\[ \sum_{k = 0}^n (-1)^k {n \choose k} = 0 \]

Let $n$ be a nonnegative integer

\[ \sum_{k = 0}^n 2^k {n \choose k} = 3^n \]

Examples

This is a useful formula. For example, if asked to calculate C(7,0)+C(7,1)+C(7,2)+C(7,3) you can immediately write down 64???? What??

Well, C(7,0)+ . . . C(7,7)=27, and since C(7,0)=C(7,7) C(7,1)=C(7,6) C(7,2)=C(7,5) C(7,3)=C(7,4) the desired sum is one half of 27=128/2=64.

Of course this works similarly for numbers other than 7.

What is the expansion of $(x + y)^4$

\[ (x + y)^4 = \sum_{j = 0}^{4} {4 \choose j} x^{4 - j}y^j\\ = {4 \choose 0} x^4 + {4 \choose 1} x^3y + {4 \choose 2} x^2y^2 + {4 \choose 3} xy^3 + {4 \choose 4} y^4\\ = x^4 + 4x^3 y+ 6x^2y^2 + 4xy^3 + y^4 \]

Another way to solve… Given $(C_1 x + C_2 y)^C_3$, if asked what is the coefficient on $x^{C_3 - n} y^n$ use ${C_3 \choose n} C_1^{C_3 - n} C_2^n$

Pascal’s Identity and Triangle

Pascal’s identity: $C(n+1,k) = C(n,k-1) + C(n,k)$ or ${n + 1 \choose k} = {n \choose k - 1} + {n \choose k}$.
Pascal’s identity, together with the initial conditions ${n \choose 0} = {n \choose n} = 1$ for all integers $n$, can be used to recursively define binomial coefficients.
Pascal’s identity is the basis for a geometric arrangement of binomial coefficients in Pascal’s triangle The $n$th row in the triangle consists of the binomial coefficients ${n \choose k}, k = 0, 1, \dots, n$ When two adjacent binomial coefficients in the triangle are added, the binomial coefficient in the next row between these two coefficients is produced

Generating Functions

Suppose we have a sequence. A GENERATING FUNCTION for that sequence is a polynomial whose coefficients are elements of the sequence. This polynomial is often expressed in functional format.

E.g., consider the sequence of n things taken i at a time: C(n,0), C(n,1), . . C(n,n)

The generating function is (in one form) the polynomial: C(n,0) + C(n,1)x + C(n,2)x2 + . . . C(n,n)xn

What is of interest is that this polynomial can be expressed as a more compact function, namely

$G(x) = (1 + x)^n = \sum_{i = 0}^n C(n, i)x^i = 1 + C(n, 1)x + C(n, 2)x^2 + \dots + C(n, n)x^n$ by the binomial theorem Thus $(1 + x)^n$ is a Generating Function for the sequence of $C(n, i)$’s.

This actually allows you to compute combinations by the simple algebraic expedient of taking a polynomial to a power, convenient if, for example, you are “factorial phobic.” Thus (1+x)3 will, if you multiply it out, give you C(n,0) – C(n,3). (n=3)