ACW Strings, Permutations, Binomial Coefficients

Print preview

Worksheet 2.1 Strings, Permutations, Binomial Coefficients

1.

Suppose a state issues license plates that are numbered with strings of length $6$ so that the first three characters must be upper-case letters in the English alphabet and the last three characters must be base $10$ digits.

🔗

(a)

How many license plates are possible?

🔗

Solution.

$26^3\cdot 10^3$ because there are $26$ choices for each of the first three positions and $10$ choices for each of the last three positions.

🔗

(b)

Suppose the state starts suffering confusion between $O$ and $0\text{.}$

🔗

(i)

How many license plates are possible if they prohibit the use of the letter $O$ in the alphabetic part?

🔗

Solution.

$25^3\cdot 10^3$ because there are $25$ choices (any letter except O) for each of the first three positions and $10$ choices for each of the last three positions.

🔗

(ii)

What if they allow $O$ but prohibit $0\text{?}$

🔗

Solution.

$26^3\cdot 9^3$ because there are $26$ choices for each of the first three positions and $9$ choices (any digit except 0) for each of the last three positions.

🔗

(iii)

What about prohibiting both $O$ and $0\text{?}$

🔗

Solution.

$25^3\cdot 9^3$ because there are $25$ choices (any letter except O) for each of the first three positions and $9$ choices (any digit except 0) for each of the last three positions.

🔗

2.

How many $4$-digit positive integers are there? (Assume that we count by writing an integer using as few digits as possible so that $10$ is a $2$-digit integer but not a $4$-digit integer.) Make your count in two ways:

🔗

(a)

By figuring out the smallest and largest integers you want to count and determining how many there must therefore be.

🔗

Solution.

The smallest number to count is $1000$ and the largest is $9999\text{.}$ This means there are $9000$ four-digit numbers using this definition.

🔗

(b)

By considering $4$-digit positive integers as strings.

🔗

Solution.

There are nine choices (any digit except 0) for the first position and 10 choices for each of the remaining ones. This gives $9\times 10\times 10\times 10 = 9000$ four-digit numbers using this definition.

🔗

3.

How many $4$-digit positive integers are divisible by $10\text{?}$

🔗

Solution.

The last digit must be 0, so there are $9\cdot 10\cdot 10\cdot 1 = 900\text{.}$

🔗

4.

How many $4$-digit positive integers are divisible by $5\text{?}$

🔗

Solution.

The last digit must be 0 or 5, so there are $9\cdot 10\cdot 10\cdot 2 = 1800\text{.}$

🔗

5.

Let’s go back to license plates allowing any three uppercase letters followed by any three numbers.

🔗

(a)

How many license plates start with a vowel followed by a consonant?

🔗

Solution.

For our purposes, there are 5 vowels and thus 21 consonants. There are thus $5\cdot 21\cdot 26\cdot 10^3$ such license plates.

🔗

(b)

How many license plates end with a $3$-digit number divisible by $5\text{?}$ (Here we allow leading zeros in $3$-digit numbers, unlike in the previous three questions.)

🔗

Solution.

Being divisible by 5 requires ending in 0 or 5. There are thus $26^3\cdot 10\cdot 10\cdot 2$ such license plates.

🔗

(c)

How many license plates start with a vowel followed by a consonant and end with a $3$-digit number divisible by $5\text{?}$

🔗

Solution.

Now we have 5 choices for the first position, 21 for the second, 26 for the third, 10 each for the fourth and fifth, and two for the last. Thus, there are $5\cdot 21\cdot 26\cdot 10^2\cdot 2$ such license plates.

🔗

(d)

How many license plates start with a vowel followed by a consonant or end with a $3$-digit number divisible by $5\text{?}$

🔗

Solution.

We have to be careful here, because if we try adding the answers to the first two parts together, then we have counted license plates such as “EGA105” twice, since this is a vowel-consonant plate and a divisible by 5 plate. We can deal with this by subtracting the answer to the third part, as the plates that are both vowel-consonant plates and divisible by 5 plates are exactly those that are counted twice. Thus, the answer is

\begin{equation*} 26^3\cdot 10\cdot 10\cdot 2 + 26^3\cdot 10\cdot 10\cdot 2 - 5\cdot 21\cdot 26\cdot 10^2\cdot 2\text{.} \end{equation*}

🔗

6.

A scholarship selection committee has been tasked with choosing five winners from $250$ applicants. The winners will receive scholarships of $10,000, $8,000, $6,000, $4,000, and $2,000. How many possible outcomes are there from the scholarship competition?

🔗

Solution.

$P(250,5)$ since we must pick five different winners and the amounts of their scholarships are different.

🔗

7.

In this question, “$4$-digit” is defined as in Problem 2 above.

🔗

(a)

How many $4$-digit positive integers are there with all distinct digits?

🔗

Solution.

We have $9$ choices for the leftmost digit because we cannot use 0. The next digit can be any of the 10 digits other than the one in the first position. There are then 8 and 7 choices for the third and fourth digits. Thus, there are $9\cdot 9\cdot 8\cdot 7\text{.}$

🔗

(b)

How many $4$-digit positive integers with distinct digits are divisible by $5\text{?}$

🔗

Solution.

We have to be careful here. One good way to do that is by separating into two cases: ends with 0 and ends with 5. If we know that the last digit is 0, then there are 9 choices for the first digit, 8 choices for the second digit, and 7 choices for the third digit, so there are $9\cdot 8\cdot 7$ numbers ending with 0. When the final digit is 5, the first digit only has $8$ choices (0 and 5 are excluded). The second digit can be any of $8$ digits (not the first digit and not 5). The third digit can be any of the remaining $7$ digits. Thus, there are $8\cdot 8\cdot 7$ numbers ending with 5. Since these two groups are exclusive, we can add and have

\begin{equation*} 9\cdot 8\cdot 7 + 8\cdot 8\cdot 7 = 17\cdot 8\cdot 7 \end{equation*}

$4$-digit numbers with distinct digits that are divisible by $5\text{.}$ One way to come up with the $17$ on its own would be to recognize that there are $18$ choices for the first and last digits in a $4$-digit number that is divisible by $5$ (9 choices for the first digit and two choices for the last digit), but this allows for numbers where the first and last digits are both $5\text{.}$ We need to exclude that to get at distinct digits, so we have $18-1=17\text{.}$

🔗

8.

Let’s change the scholarship problem from Problem 6. Suppose the committee is instead tasked with choosing five winners (from $250$ applicants), each of whom will receive a $6,000 scholarship. Is the number of possible outcomes here less than, the same as, or greater than the number of ways to award scholarships of $10,000, $8,000, $6,000, $4,000, and $2,000?

🔗

Solution.

Since the scholarships now all have the same value, all that matters is which 5 students are selected. Thus, the answer is $\binom{250}{5}\text{.}$

🔗

9.

How many binary strings of length $10$ are there containing exactly three $1$s?

🔗

Solution.

A binary string has symbols only 0 and 1. Once we choose the 3 positions to put 1’s, we must fill the rest with 0’s. Thus, there are $\binom{10}{3}$ such binary strings.

🔗

10.

Suppose a basketball team has $15$ players.

🔗

(a)

How many ways are there to choose the $5$ players who are on the court at any given time?

🔗

Solution.

At this point, order doesn’t matter, so we have $\binom{15}{5}\text{.}$

🔗

(b)

To be a bit more realistic, suppose there are $6$ players who play guard, $5$ players who play forward, and $4$ players who play center. The team’s offense calls for two guards, two forwards, and one center to be on the court at all times. How many ways are there for the coach to pick the players to put in the game in this scenario?

🔗

Solution.

Assuming that there’s no reason to care about order for which two players are playing guard and which two players are playing forward, we have

\begin{equation*} \binom{6}{2}\binom{5}{2}\binom{4}{1}\text{.} \end{equation*}

🔗

11.

Alice’s Diner is a meat and three restaurant at which customers order a plate consisting of one of five meats and three sides chosen from a list of $15$ options. How many different plates can be ordered? What if Alice’s Diner offers a “deluxe plate” offering the customer’s choice of two meats (but still three sides)?

🔗

Solution.

There are 5 choices for the meat and $\binom{15}{3}$ ways to choose the three sides. (We assume here that you cannot, for example, declare that you really like mashed potatoes and want three portions of mashed potatoes. Allowing repeated selection of sides requires some tools we haven’t discussed yet.) Thus, there are $5\cdot \binom{15}{3}$ options.

🔗

For the deluxe plate, we now have $\binom{5}{2}$ ways to choose the meats, so there are $\binom{5}{2}\binom{15}{3}$ options.

🔗

12.

Suppose we’re making six-character license plates using uppercase letters and digits.

🔗

(a)

How many license plates are possible if we require the license plate to contain exactly two W’s, which are allowed to appear in any of the six positions, and then can fill the other four positions with any uppercase digit or letter (other than W)?

🔗

Solution.

We first pick the two places to put the W’s. There are $\binom{6}{2}$ ways to do this. We then have 25 letters and 10 digits, or a total of 35 characters that we can use in the four remaining positions. Thus, there are $\binom{6}{2} 35^4$ license plates.

🔗

(b)

How about if we modify the scenario above by not allowing any character to be repeated when filling the other four positions?

🔗

Solution.

Again, we have $\binom{6}{2}$ ways to pick where the W’s go. We have $P(35,4)$ ways to fill in the remaining positions, for a total of $\binom{6}{2}P(35,4)\text{.}$

🔗

(c)

Suppose we want to keep the requirement of exactly three uppercase letters and exactly three digits (repetition allowed for both) but no longer want to mandate which positions are letters and which positions are digits. How many license plates can we make now?

🔗

Solution.

For this problem, we proceed in two phases. First we pick where the letters go (or where the digits go, as once we’ve made either choice, the other is forced). Then we fill in the positions. Since there are 6 positions and we need 3 letters, there are $\binom{6}{3}$ ways to choose where the letters go. We then have $26^3$ ways to fill in the letters. As noted, there is one way to pick where the digits now go, which we confirm by noting that $\binom{3}{3}=1\text{.}$ There are $10^3$ ways to fill in the digits. We must make all of these choices to fill out the license plate, so there are

\begin{equation*} \binom{6}{3}26^3 10^3 \end{equation*}

such license plates.

🔗

13.

Come up with a simple value for the sum

\begin{equation*} \binom{n}{0}+ \binom{n}{1}+ \binom{n}{2}+ \cdots + \binom{n}{n-1}+\binom{n}{n}\text{.} \end{equation*}

🔗

Hint.

Start by trying it out for small values of $n\text{.}$ Maybe think about binary strings to prove your conjecture true.

🔗

Solution.

We will talk more about this in class, so no solution provided for now.

🔗

Prev TopNext

Print preview

Worksheet 2.1 Strings, Permutations, Binomial Coefficients

1.

(a)

(b)

(i)

(ii)

(iii)

2.

(a)

(b)

3.

4.

5.

(a)

(b)

(c)

(d)

6.

7.

(a)

(b)

8.

9.

10.

(a)

(b)

11.

12.

(a)

(b)

(c)

13.

Worksheet 2.1 Strings, Permutations, Binomial Coefficients