Chapter 6: Counting

Explain how the sum and product rules can be used to find the number of bit strings with a length not exceeding 10 .

How many ways are there to choose 6 items from 10 distinct items when

a) the items in the choices are ordered and repetition is not allowed?

b) the items in the choices are ordered and repetition is allowed?

c) the items in the choices are unordered and repetition is not allowed?

d) the items in the choices are unordered and repetition is allowed?

Suppose that and are integers with$\mathbf{1}\mathbf{\le }\mathit{k}\mathbf{<}\mathit{n}$ . Prove the hexagon identity$\left(\begin{array}{l}n-1\\ k-1\end{array}\right)\left(\begin{array}{c}n\\ k+1\end{array}\right)\left(\begin{array}{c}n+1\\ k\end{array}\right)\mathbf{=}\left(\begin{array}{c}n-1\\ k\end{array}\right)\left(\begin{array}{c}n\\ k-1\end{array}\right)\left(\begin{array}{l}n+1\\ k+1\end{array}\right)$ which relates terms in Pascal's triangle that form a hexagon.

How many solutions are there to the inequality, where, andare nonnegative integers? (Hint: Introduce an auxiliary variable x4 such that.)

How many bit strings of length \({\bf{10}}\) have

a) exactly three \(0s\)?

b) more \(0s\) than \(1s\) ?

c) at least seven \(1s\) ?

d) at least three \(1s\) ?

Once a computer worm infects a personal computer via an infected e-mail message, it sends a copy of itself to \({\bf{100}}\) email addresses it finds in the electronic message mailbox on this personal computer. What is the maximum number of different computers this one computer can infect in the time it takes for the infected message to be forwarded five times?

Prove that if\(n\)and\(k\)are integers with\(1 \le k \le n\), then\(k \cdot \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right) = n \cdot \left( {\begin{array}{*{20}{l}}{n - 1}\\{k - 1}\end{array}} \right)\),

a) using a combinatorial proof. [Hint: Show that the two sides of the identity count the number of ways to select a subset with\(k\)elements from a set with n elements and then an element of this subset.]

b) using an algebraic proof based on the formula for\(\left( {\begin{array}{*{20}{l}}n\\r\end{array}} \right)\)given in Theorem\(2\)in Section\(6.3\).

How many ways are there to distribute six indistinguishable balls into nine distinguishable bins?

How many permutations of the letters \(ABCDEFG\) contain

a) the string \(BCD\)?

b) the string \(CFGA\)?

c) the strings \(BA\) and \(GF\)?

d) the strings \(ABC\)and \(DE\)?

e) the strings \(ABC\)and \(CDE\)?

f) the strings \(CBA\)and \(BED\)?.

how many ways are there to choose a dozen donuts from \(20\) varieties a) if there are no two donuts of the same variety? b) If all donuts are of the same variety? c) If there are no restrictions? d) If there are at least two varieties among the dozen donuts chosen? e) If there must be at least six blueberry-filled donuts? f) If there can be no more than six blueberry-filled donuts?