Homework 3 Solutions#

The write-ups below model the amount of explanation expected in a complete handwritten submission.

Selecting colored balls#

Problem. For this exercise, an outcome records only the number of balls selected of each color. Thus balls of the same color are not distinguished from one another, and the order of selection is irrelevant.

  1. A box contains 5 blue balls, 7 red balls, and 14 yellow balls. How many ways are there to select a total of 15 balls?

  2. A box contains 5 blue balls, 7 red balls, and 20 yellow balls. How many ways are there to select a total of 15 balls?

Solution.

Approach. Write each selection as a solution of and use inclusion–exclusion for the colors with limited supplies.

Let denote the numbers of blue, red, and yellow balls selected. An outcome is a nonnegative integer solution of Without the supply restrictions, stars and bars gives solutions.

(A) The invalid selections have , , or . These three sets have sizes

The only nonempty intersection of two invalid conditions is and . After subtracting 6 from and 8 from , it is counted by which has solutions. Hence

(B) The bound is automatic because only 15 balls are selected. The blue and red restrictions give

Strings avoiding specified substrings#

Problem. How many strings of length 15 can be formed from the 26 uppercase English letters if no letter may be repeated and none of the following strings may occur as a substring? Here a substring consists of consecutive letters in the given order.

Solution.

Approach. Use inclusion–exclusion, treating each required substring as one block. If two substrings share a letter, they must overlap at that letter because repetition is forbidden.

Let be the set of length-15 strings with no repeated letter. Then . Let be the sets of strings containing CAT, TUG, GAS, and SILK, respectively.

A three-letter block has 13 possible starting positions, and the remaining 12 positions can be filled in ways. Similarly,

The pairwise intersections are The intersection containing CAT and GAS is empty because their single copy of A would need both C and G immediately before it. For two disjoint blocks of lengths 3 and 4, compression leaves ten objects; the two blocks can occupy ordered positions in ways.

There are two nonempty triple intersections: The first uses the separate blocks CATUG and SILK; the second uses the block TUGASILK. Every other higher intersection contains the incompatible pair and is empty.

Therefore inclusion–exclusion gives

Permutations with forbidden positions#

Problem. The digits in the string are initially in their original positions. Rearrange all ten digits, using each digit exactly once.

  1. How many rearrangements have no digit in its original position?

  2. How many rearrangements satisfy all three of the following conditions?

    • No digit is in its original position.

    • The digits occupy the first three positions, in some order.

    • The digits occupy the last two positions, in some order.

Solution.

(A) These are the derangements of ten digits, so

(B) The three position groups force separate derangements of , , and . Therefore