Homework 1 Solutions#

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

Using every letter#

Problem. How many strings of length 10 over the alphabet contain each of the three letters at least once?

Solution 1.

Approach. Count all strings and subtract those that use fewer than three letters.

There are strings in all. A forbidden string either uses exactly one letter or exactly two letters.

There are 3 strings that use exactly one letter (one for each letter).

To compute the number of strings that use exactly 2 letters, first we choose which letters we use (3 ways: , , or )

For each of the 3 pairs of letters, there are strings that use both letters in the pair. are the total strings and accounts for the two strings that use only one of the two letters

Therefore

Forming a committee#

Problem. A company has 20 employees in Marketing and 10 employees in Research and Development (R&D). It must form a committee with the following five positions:

one chair;
one vice-chair; and
three ordinary members, whose positions are not distinguished from one another.

No employee may hold more than one position. The chair and vice-chair must come from different departments; the ordinary members may come from either department. How many committees are possible?

Solution 1.

Approach. Choose the officers first. Then choose the ordinary members in order and divide by the number of orders of those three members.

The officers can be chosen in ways. Afterward, 28 employees remain. Ordering three ordinary members gives choices, but each unordered group is counted times. Therefore

Digits on a pentagon, without repetition#

Problem. Place five distinct digits chosen from at the vertices of a regular pentagon. Two patterns are considered the same when one can be obtained from the other by rotating the pentagon. Reflections are not considered the same.

The examples below illustrate this convention. The labels name the fixed vertex positions , beginning at the top vertex and proceeding clockwise.

Figure 1: Pentagon with digits 1, 2, 3, 4, 5 clockwise from the top vertex.#

A rotation of Pattern 1, with digits 5, 1, 2, 3, 4 clockwise from the top vertex. — Figure 2: A rotation of Pattern 1.#

Pentagon with digits 1, 2, 3, 5, 4 clockwise from the top vertex. — Figure 3: A nonrotation of Pattern 1 using digits 1, 2, 3, 5, 4.#

Pentagon with digits 1, 2, 4, 6, 8 clockwise from the top vertex. — Figure 4: A pattern using digits 1, 2, 4, 6, 8.#

Patterns 1 and 2 are considered the same because a rotation carries one to the other. No other pair among the four displayed patterns is considered the same. How many different patterns are there?

Solution.

Approach. Count assignments to five labeled vertices, then divide by the five rotations of each pattern.

With the vertices labeled , the number of assignments of five distinct digits is Each pattern has five distinct rotations because its digits are distinct. We do not divide by reflections, since reflections count as different patterns. Thus

Why division by five can fail#

Problem. Now change the preceding exercise by allowing digits to repeat. Thus each of the five vertices may receive any digit from , while patterns that differ only by a rotation are still considered the same.

A tempting argument is:

There are assignments to five fixed vertices, and every pattern is represented five times by rotation, so the answer is .

Explain carefully why this argument is incorrect. You are not being asked to find the correct total.

Solution.

The count is correct because each of the five labeled vertices has 10 digit choices. The division by 5 fails because patterns do not all have five distinct rotations. For example, has only one distinct rotation, while and each have five. Therefore the labeled assignments do not represent every pattern the same number of times, so the division rule cannot be applied.