Illinois State University Mathematics Department


MAT 305: Combinatorics Topics for K-8 Teachers

Spring 2000
6:00 - 8:50 pm Tuesday STV 332
Dr. Roger Day (day@math.ilstu.edu)



Possible Solutions: Test #2

Evaluation Criteria

You may earn up to 10 points on each of questions 1 through 6. For each question:

  • 6 points count toward a correct solution to the problem. I will evaluate the mathematics you use:
    • Is it accurate and appropriate?
    • Have you provided adequate justification?
  • 4 points count toward how you express your solution. I will evaluate how you communicate your results:
    • Is your solution clear and complete?
    • Have you expressed logical connections among components of your solution?

1.

Respond to each of these questions. While you may show steps leading to your solution, you do not need to generate written explanations for questions (a) through (e) on this page.

a) Express P(16,5) using factorial notation.

b) How many distinct arrangements exist for the letters in the word reverberator?

c) In the expansion of , state:

i) the number of uncollected terms:

4^12

ii) the coefficient J in the collected term :

d) Determine the number of collected terms in the expansion of .

6

e) Replace w, x, y, and z in C(12,6) = C(w,x) + C(y,z) to illustrate Pascal's Formula, a fundamental relationship that exists in Pascal's Triangle.

C(12,6) = C(11,6) + C(11,5)

2.

Thum lives in Grid City, where the streets are laid our in a grid, running east/west and north/south. Thum's house is in the northwest corner of the city and his girlfriend, Bolina, lives in the southeast corner of the city. Thum's house is 8 blocks north and 12 blocks west of Bolina's. The image below shows the entire city.

a) How many 20-block paths are there from Thum's to Bolina's, assuming all streets exist and are open to traffic?

Traveling from Thum's to Bolina's in a 20-block path requires traversal of 8 southbound streets and 12 eastbound streets. Thus, we need to look at all permutations of the "word" SSSSSSSSEEEEEEEEEEEE to determine the number of paths.

The number of unique arrangements of this 20-character word is C(20,8)=C(20,12)=20!/(12!8!).

b) Grid City eventually will build a walking mall in the shaded location shown below, thereby eliminating a one-block length of street. Under these conditions, how many 20-block paths are there from Thum's to Bolina's?

From the C(20,8) paths determined in (a), we must subtract all paths that contain the restricted street, shown above as going from x to y.

Using the same reasoning as in (a), there are C(9,4) paths from T to x, 1 path from x to y, and C(10,4) paths from y to B. Because each of these legs (T to x, x to y, and y to B) are independent from each other and each must be included in a 20-block path from T to B through the restricted street, we multiply the three values to determine the total number of 20-block paths from T to B through the restricted street. This is C(9,4)*1*C(10,4)=C(9,4)*C(10,4). We subtract this from C(20,8) to determine the number of paths we can use to go from T to B and avoid the restricted street.

The resulting number of paths is C(20,8)-C(9,4)*C(10,4).

3.

Referring to the letters in the word ACMAESTHESIA, solve each of the following problems. Each problem is independent and separate from the others.

a) How many unique arrangements are there for the letters in this word?

There are 12! permutations of the letters in the word, but we must account for duplication and therefore divide by 3!2!2! because there are 3 identical As, 2 identical Es, and 2 identical Ss. There are 12!/(3!2!2!) unique arrangements for the letters in this word.

b) How many unique arrangements exist if two or more vowels cannot be adjacent to one another?

Begin by placing the 6 consonants in the word. Accounting for two Ss, this can be done in 6!/2! ways. This leaves us 7 places among the 6 consonants in which to place vowels so no vowels will be adjacent. We first choose 6 of the 7 places for the vowels, done in C(7,6) ways. We now permute the vowels within the places chosen. this can be done in 6!/(3!2!) ways, accounting for duplicate As and Es. We multiply the results to determine the total number of ways of arranging the letters in the word so no vowels are adjacent. This is (6!/2!)*C(7,6)*[6!/(3!2!)].

c) If the only distinction we can make is between consonants and vowels, how many arrangements can be made?

With no distinction among the vowels or among the consonants, we have 12 total objects of just two types, 6 of type "consonant" and 6 of type "vowel." We permute the 12 objects and account for the duplicates among the types. This results in 12!/(6!6!) ways to make this sort of arrangement.

d) If the only distinction we can make is between consonants and vowels, and two or more consonants cannot be adjacent to one another, how many arrangements can be made?

Again with no distinction among the vowels or among the consonants, we have 12 total objects of just two types, 6 of type "consonant" and 6 of type "vowel." We first place the vowels, and because they are indistinguishable, there is 1 way to do that. We create 7 spaces among the vowels, and we choose 6 of these for the consonants. This is just C(7,6), our desired result. There are 7 arrangements that can be made under these conditions.

4.

Louise invests her money in $200 lots. She has $3000 to invest and her daughter Gina has suggested five different mutual funds for Louise's investments.

a) How many different ways can Louise invest her money if she insists on putting at least $200 in each of the five funds her daughter recommended and uses only these five funds?

Note that Louise has 15 lots of $200 each to invest. Thus we are dealing with the placement of 15 objects that are identical.

If Louise drops 1 lot into each of the five funds, she has 10 lots remaining to distribute. This distribution of 10 lots can be done in any way among the five funds. This is analogous to solving the equation A+B+C+D+E=10 where A,B,C,D, and E must be nonnegative integers. This placement can be done in C(10+5-1,5-1)=C(14,4) ways.

In terms of objects and dividers, we have 10 objects and 4 dividers to permute. This can be done in 14!/(10!4!) ways.

b) If Louise restricts her investments to these five funds but may choose to not invest any money in one or more of the funds, how many different ways can Louise invest her money?

Again we have 15 lots of $200 each to invest.

This distribution of 15 lots can be done in any way among the five funds. This is analogous to solving the equation A+B+C+D+E=15 where A,B,C,D, and E must be nonnegative integers. This placement can be done in C(15+5-1,5-1)=C(19,4) ways.

In terms of objects and dividers, we have 15 objects and 4 dividers to permute. This can be done in 19!/(15!4!) ways.

5.

Consider the binomial .

a) Determine the number of uncollected terms in the expansion of this binomial.

For the expansion of a binomial, this is just 2^t.

b) Show and describe a typical collected term in the expansion of this binomial.

A typical term in the expansion will be , where x+y=t and C=t!/(x!y!).

c) If k = x, m = 2y, and t=8, determine N in the collected term Nx^3y^5.

We are expanding the binomial (x+2y)^8. for the collected term in question, we will have C(8,3)*(x)^3*(2y)^5, which simplifies to . Therefore, .

6.

A bag contains a virtually unlimited supply of red marbles, blue marbles, white marbles, and yellow marbles. Marbles of any one color are indistinguishable from each other.

a) Marbles are drawn from the bag without looking until a set of 6 marbles is created. How many different 6-marble sets could be created?

We have an essentially unlimited supply of four different objects, so as we draw from the bag we could generate a set of 6 marbles with various numbers of each color marble, as many as 6 of one color and as few as 0 of one or more colors.

This is analogous to solving the equation R+B+W+Y=6 where R,B,W, and Y must be nonnegative integers. This distribution can occur in C(6+4-1,4-1)=C(9,3) ways.

In terms of objects and dividers, we have 6 objects and 3 dividers to permute. This can be done in 9!/(6!3!) ways.

b) Marbles are drawn from the bag without looking until a set of 24 marbles is created. Of all the 24-marble sets we could create, how many have at least two marbles of each color?

Again we have an essentially unlimited supply of four different objects, so as we draw from the bag we generate a set of 24 marbles with various numbers of each color marble. We are restricted to having at least two of each color marble.

If we preselect 2 marbles of each of the four colors, we have 16 marbles remaining to select. This selection of 16 marbles can be done in any way among the four colors. This is analogous to solving the equation R+B+W+Y=16 where R,B,W, and Y must be nonnegative integers. This distribution can occur in C(16+4-1,4-1)=C(19,3) ways.

In terms of objects and dividers, we have 16 objects and 3 dividers to permute. This can be done in 19!/(16!3!) ways.

c) Marbles are drawn from the bag without looking until a set of 30 marbles is created. Of all the 30-marble sets we could create, how many have marbles of exactly three colors in them?

Again we have an essentially unlimited supply of four different objects and we draw from the bag to generate a set of 30 marbles with various numbers of each color marble. We are restricted to 30-marble sets that contain exactly three colors. This is equivalent to saying in the 30-marble set exactly one color is NOT represented.

If we preselect red as the marble color not selected, we have 30 marbles to select from among three colors. This selection of 30 marbles can be done in any way among the three colors, with the restriction that each of the remaining three colors is represented by at least one marble. This is analogous to solving the equation B+W+Y=30 where B,W, and Y must be positve integers. This distribution can occur in C(30-1,3-1)=C(29,2) ways.

In terms of objects and dividers, we have 30 objects and 2 dividers to work with. Because all remaining colors among the three must be represented, the 2 dividers must be placed somewhere among the 29 spaces between the 30 objects. This can be done in C(29,2) ways.

The same logic and calculations will result for each of the other three cases, that is, when blue is the preselected absent color, when white is the preselected absent color, and when yellow is the preselected absent color. Therefore, of all the 30-marble sets we could create, there are 4*C(29,2) with exactly three colors in them.


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