Illinois State University Mathematics Department
MAT 305: Combinatorics Topics for K8 Teachers 
Let us return to the birthorder arrangement problem. Recall that we considered a family with three sons and four daughters. There are, of course, several other ways that the family could have had seven children. Here is a sequence of problems for you to investigate to extend the setting and foreshadow new material.
1) Show all gender combinations possible for a family with seven children, with no regard for birth order. The family of three sons and four daughters is one of many such combinations.
2) For each of the ways you find in (1) (there should be 8 total, including our initial example of three sons and four daughters), determine the number of different birthorder arrangements that are possible. Include the example we have already done with three sons and four daughters.
3) Sum the eight values you get in (2).
4) Repeat steps (1) through (3) for at least three family sizes different than seven children. Include:
5) Examine your results for (3) for the various family sizes you used in (4). Write a conjecture to describe a pattern you detect.
6) Justify your conjecture for the general case of a family with N children, k of whom are daughters.
We can also argue that there are 2^7 different birthorder sequences for families with 7 children that have from 0 to 7 sons (or 7 to 0 daughters). That is, we are claiming that C(7,0)+C(7,1)+...+C(7,7)=2^7=128.
The general result is that . How can we justify that this will always be the case?
We could expand the expression to get
which equals
and work to simplify this summation. We also might approach the task with an induction proof. You are urged to consider that option as a possible test question.
There is another efficient strategy, but to employ it we need some machinery. Particularly, we need a combinatorics relationship named for Pascal and we need to show how combinatorics relates to the expansion of a binomial expression.
Consider the set of seven elements {a,b,c,d,e,f,g} and all the 3element subsets of this set, such as {a,b,c}, {a,b,d}, and so on. We know that there are C(7,3)=35 different 3element subsets. Now, separate these 35 3element sets into those that contain the letter a and those that do not. In the first group are sets such as {a,b,c}, {a,b,d}, and so on, while the second group contains sets such as {b,c,d}, {e,f,g}, and so on. How many of each group are there?
The 3element subsets containing the letter a have two additional letters chosen from the six remaining letters. There are C(6,2)=15 of these. The subsets that do not contain the letter a have three letters from the remaining six in the set. There are C(6,3)=20 of these.
Notice the equivalence relationship we have established: C(7,3)=C(6,2)+C(6,3).
In general, for the kelement subsets of an nelement set, we have C(n,k)=C(n1,k1)+C(n1,k). More important that the particular symbols we use is the relationship among combinatorial representations, for we could have written C(2a,4t)=C(2a1,4t1)+C(2a1,4t), or C(n+1,k)=C(n,k1)+C(n,k).
This relationship is called Pascal's Formula
For the kelement subsets of an nelement set, the following combinatorial relationship holds: 
We could repeatedly apply Pascal's Formula to create a sequence of equivalent representations. Here's just one numerical example:
and so on.
Algebraic expressions of two terms are called binomials, such as 2x + 3y or a + b. Somewhere in our deep dark algebra histories, we developed one or more ways to expand binomials raised to various powers. You might have associated the mnemonic device called FOIL to the expansion of (a+b)(a+b) to get
Note that each term in the first binomial is multiplied, one by one, with each term in the second binomial. There are actually 4 pairs of terms being multiplied, but in simplifying we gathered together two like terms.
Let's look at other particular cases of the expansion of
If n=3, we have (a+b)(a+b)(a+b). Let's identify the various triplets of terms being multiplied together to generate the expansion:









Using exponents whenever possible and gathering together like terms, we have
Now we ask the combinatorics questions:
In the first and the last case, because we cannot distinguish among any terms called a (or b), there exists just one way to arrange three letters a: a a a. Likewise, we get one arrangement of three letters b: b b b.
For the second question, we have a a b, a b a, and b a a. There are three ways, just as there are for two letters b and one letter a: a b b, b a b, and b b a.
This ought to look familiar. Aside from using a and b instead of S and D, we're solving the same generic problem:
How many ways to arrange a set of n items such that there are k items of one type and nk items of a second type?
We related this to combinations, showing that the result is C(n,k), or equivalently, C(n,nk).
Let's try to apply this to the expansion of .
Each uniquely ordered product has 4 factors, and each product has k letters a and 4k letters b, where k=0,1,2,3,4. So, how many ways exist to formulate the product a*a*a*a?
We have C(4,4)=1=C(4,0).
How many ways to get ? C(4,2)=6.
Considering this for every possible product in the expansion, we have
We now ought to be able to generalize this for the expansion of Each uniquely ordered product has n factors, and each product has k letters a and nk letters b, where k=0,1,2,...,n.
How many ways exist to formulate the product that has n letters a in it? Just 1, a*a*a*...*a, where a appears n times. In combinatorial notation, this is just C(n,n).
How many ways exist to formulate the product that has n1 letters a in it and 1 letter b in it? We have b*a*a*...*a, a*b*a*...*a, a*a*b*a*...*a, and so on, through a*a*...*a*b. From a combinatorial perspective, we are selecting n1 places for a to appear and 1 place for b to appear. This is represented by C(n,n1), or, equivalently, C(n,1).
We can continue this process, looking at n2 letters a and 2 letters b, n3 letters a and 3 letters b, and so on, through to no letters a and n letters b. This results in the following coefficients associated with each product:
There are C(n,n) ways to generate the product a^n, C(n,n1) ways to generate the product a^(n1)*b, C(n,n2) ways to generate the product a^(n2)*b^2, and so on, through to C(n,1) ways to generate the product a*b^(n1) and C(n,0) ways to generate the product b^n.
We now sum these products to get the entire binomial expansion.
The expansion of the binomial expression is 
We have looked at several problem situations that can be represented in an equivalent way:
Let's look at the last situation and generate what may be for some of us a familiar pattern of relationships.
Here's a representation for the grid problem we have already considered. We want to know the number of paths that lead from one corner of the grid to the other.
This image shows the grid rotated 45 degrees.
Now let's start counting the ways to get to each subsequent street corner (vertex) in the grid.
Finally, if we strip away the grid itself (and place a "1" at the top), we're left with this triangle of numbers.
If we use n to represent a row number (starting with n=0) and k to represent the position of an entry from left to right (starting with k=0), we also can represent this as follows:
k=0 
k=1 
k=2 
k=3 
k=4 
k=5 
k=6 

n=0 


n=1 



n=2 




n=3 





n=4 






n=5 







n=6 







This is Pascal's Triangle. What patterns do you see in these representations?
Binomials are just a special case of a larger class of expressions called multinomialsexpressions with more than one term. The expression (a + b + c) is a trinomial. We seek to generalize the counting strategies developed for binomials so that we can answer the same questions for multinomial expansion. Here's a specific question to get us started:
What do we know about the expansion of (a + b + c + d)^6? What would we like to know?
We know:
We'd like to know . . .
In expanding
,
we form sixfactor terms by choosing one factor (a,b,c,d) from each of the six identical expressions (a + b + c + d). How many ways can we choose . . . a a a a a a ? a a b b c d ? c c c c c d ?
Another way to look at this question is to consider each term of the expansion to contain factors a,b,c,d in various amounts, but always getting six factors in all. Expressed in relation to "words" with arrangements of six letters, we might ask:
From a total of six letters, we choose 2 that are a, 2 that are b, 1 that is c, and 1 that is d. Extending the binomial case (or the case of arranging two types of objects where repetition is allowed), we have C(6,2) ways to place the letters a, then C(4,2) ways to place the letters b, then C(2,1) ways to place the c, and finally C(1,1) to place the letter d. Multiplying these and simplifying using factorial notation, we get 6!/(2!2!1!1!)=180.
This tells us there are 180 ways to create a 6element set with two letters a, two letters b, and one letter each of c and d. Thus, when we expand and collect all the like terms together, one term in the expansion will be . The value 180 is the coefficient of the term .
More generally, in the expansion of , the coefficient of each term will be n!/(a!b!c!...k!), where a represents the number of repetitions of the factor A, b represents the number of repetitions of the factor B, and so on, and we have a + b + . . . + k = n.
My nephew Seth collects baseball cards, so for his birthday I offered Seth the opportunity to take any number of cards that he wanted from a 10card set I had accumulated. How many different collections of cards could Seth have assembled?
Assuming the cards are distinguishable from one another, there are lots of possibilities. If we label the cards 1,2,3,4,5,6,7,8,9,10, some sets he could have taken include {1,5,6}, {7,8,3,5,2}, {5}, and even {} and {1,2,3,4,5,6,7,8,9,10}. How many such sets are there?
There are at least a couple different ways we can think about this.
Think of the 10 cards as a family of 10 children, and think of a card selected by Seth as male and a card not selected by Seth as a female. How many different family birthorder arrangements exist for all possible 10child families that have from 10 to 0 daughters? The answer is 2^10 as we reviewed in the previous section.
We can also look at the possibility for each card: Either Seth chooses it or he does not. So, for card 1 Seth has two choices, for card 2 there are two choices, and so on. Because Seth's selection of each card is independent from his choice of any other card, we multiply the number of choices for each card, again resulting in 2^10 possible sets.
We should note that in this case, we consider {1,2,3,4,5,6,7,8,9,10} as a possible set. In the mathematics of sets, we say this is not a proper subset of the original set, because it contains the entire set. All other subsets, including the empty set, are considered proper subsets. Therefore, there are 2^10  1 proper subsets of {1,2,3,4,5,6,7,8,9,10}. More generally, there are 2^n subsets of an nelement set, and 2^n  1 proper subsets of that nelement set.
Full Circle: Total Possible Arrangements
One of the very first questions we posed that explored this situation was about children in families:
In a family with n children, how many different birthorder arrangements are possible given from 0 to n possible sons (and, correspondingly, n to 0 possible daughters)?
We concluded that for a family with n children, k of them sons, there are C(n,k) different birth order arrangements. We went on to simplify the expression
By relating this combinatorial representation to the binomial expansion, we can solve the problem.
In the expansion
if we let a and b both equal 1, we get
which is just
Relating this to the family/children question, we see that in a family of 4 children, there are
different birth orders for all possible numbers of sons and daughters in the family.
The general result is that
tells us the total number of possible ways to arrange n objects when we have from 0 to n of the first type of object and n to 0 of the second type of object.
The total number of possible ways to arrange n objects when we have from 0 to n of the first type of object and n to 0 of the second type of object is 
Given n objects of k different types, we have total possible ways to arrange the n objects given all possible ways to group the k types. 
Here are several problems to help review our discussion of the binomial and multinomial expansions. Click on the highlighted word to take you to a possible solution or hint for that problem.






Possible Solutions to Review Problems
1. r^3+3r^2s+3rs^2+s^3
2. 4^7m^73(4^6)m^6t+9(4^5)m^5t^2
3. 19
4. No. Its exponents do not sum to 12.
5. [8!/(2!4!1!1!)](a^2b^4cd)
6. Example: How many different arrangements are
there for the letters in the nonsense word aabbbbccc?