Illinois State University Mathematics Department

MAT 305: Combinatorics Topics for K-8 Teachers



Total Number of Possible Arrangements

Introdutory Problem
Pascal's Formula
Binomial Expansion
Pascal's Triangle
Multinomial Expansion
Number of Subsets of a Set
General Result: Total Possible Arrangements
Review: Binomial and Multinomial Expansions

Let us return to the birth-order 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 birth-order 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 birth-order 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.

Pascal's Formula

Consider the set of seven elements {a,b,c,d,e,f,g} and all the 3-element 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 3-element subsets. Now, separate these 35 3-element 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 3-element 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 k-element subsets of an n-element set, we have C(n,k)=C(n-1,k-1)+C(n-1,k). More important that the particular symbols we use is the relationship among combinatorial representations, for we could have written C(2a,4t)=C(2a-1,4t-1)+C(2a-1,4t), or C(n+1,k)=C(n,k-1)+C(n,k).

This relationship is called Pascal's Formula

Pascal's Formula

For the k-element subsets of an n-element set, the following combinatorial relationship holds:

C(n,k)=C(n-1,k)+C(n-1,k-1)

We could repeatedly apply Pascal's Formula to create a sequence of equivalent representations. Here's just one numerical example:

and so on.

Binomial Expansion

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:

a*a*b
b*b*a

a*a*a
a*b*a
b*a*b
b*b*b

b*a*a
a*b*b

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 n-k items of a second type?

We related this to combinations, showing that the result is C(n,k), or equivalently, C(n,n-k).

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 4-k 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 n-k 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 n-1 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 n-1 places for a to appear and 1 place for b to appear. This is represented by C(n,n-1), or, equivalently, C(n,1).

We can continue this process, looking at n-2 letters a and 2 letters b, n-3 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,n-1) ways to generate the product a^(n-1)*b, C(n,n-2) ways to generate the product a^(n-2)*b^2, and so on, through to C(n,1) ways to generate the product a*b^(n-1) and C(n,0) ways to generate the product b^n.

We now sum these products to get the entire binomial expansion.

Binomial Expansion

The expansion of the binomial expression is

Pascal's Triangle

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

1

n=1

1
1

n=2

1
2
1

n=3

1
3
3
1

n=4

1
4
6
4
1

n=5

1
5
10
10
5
1

n=6

1
6
15
20
15
6
1
and so on.

This is Pascal's Triangle. What patterns do you see in these representations?

Multinomial Expansion

Binomials are just a special case of a larger class of expressions called multinomials--expressions 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 six-factor 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 6-element 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.

Number of Subsets of a Set

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 10-card 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 birth-order arrangements exist for all possible 10-child 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 n-element set, and 2^n - 1 proper subsets of that n-element 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 birth-order 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.

Total Possible Arrangements (I)

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

Notice, too, that this justifies another conjecture, namely, that the sum of the entries in the nth row of Pascal's triangle is .

Total Possible Arrangements (II)

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.

Review: Binomial & Multinomial Expansions

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.

  1. Expand (r + s)^3.
  2. Write the first three terms, beginning with the term containing the factor m^7, in the expansion of (4m - 3t)^7.
  3. After expanding and collecting all like terms, how many terms will there be in the expansion of (w + v)^18 ?
  4. Is r^4st^2v^3 a possible term in the expansion of (r + s + t +v)^12 ? Explain.
  5. Determine the coefficient for the collected term containing the factor a^2b^4cd in the expansion of (a + b + c + d)^8.
  6. Create a counting problem for which 9!/(2!4!3!) is the numerical solution.


Syllabus
Grades & Grading
Content Notes
Session Outlines
Assignments and Problem Sets
Tests and Quizzes

Possible Solutions to Review Problems

1. r^3+3r^2s+3rs^2+s^3
2. 4^7m^7-3(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?

Return to: | 1 | 2 | 3 | 4 | 5 | 6 |