Chapter 6: Counting

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

a) the string \(ED\)?

b) the string \(CDE\)?

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

d) the strings \(AB\;,\;DE\) and \(GH\)?

e) the strings \(CAB\) and \(BED\)?

f) the strings \(BCA\) and \(ABF\)?

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

Prove the identity\(\left( {\begin{array}{*{20}{l}}n\\r\end{array}} \right)\left( {\begin{array}{*{20}{l}}r\\k\end{array}} \right) = \left( {\begin{array}{*{20}{l}}n\\k\end{array}} \right)\left( {\begin{array}{*{20}{l}}{n - k}\\{r - k}\end{array}} \right)\), whenever\(n\),\(r\), and\(k\)are nonnegative integers with\(r \le n\)and\(k{\rm{ }} \le {\rm{ }}r\),

a) using a combinatorial argument.

b) using an argument based on the formula for the number of \(r\)-combinations of a set with\(n\)elements.

Find n if \({\bf{a}}){\rm{ }}{\bf{P}}{\rm{ }}\left( {{\bf{n}},{\rm{ }}{\bf{2}}} \right){\rm{ }} = {\rm{ }}{\bf{110}}.{\rm{ }}{\bf{b}}){\rm{ }}{\bf{P}}{\rm{ }}\left( {{\bf{n}},{\rm{ }}{\bf{n}}} \right){\rm{ }} = {\rm{ }}{\bf{5040}}.{\rm{ }}{\bf{c}}){\rm{ }}{\bf{P}}{\rm{ }}\left( {{\bf{n}},{\rm{ }}{\bf{4}}} \right){\rm{ }} = {\rm{ }}{\bf{12P}}{\rm{ }}\left( {{\bf{n}},{\rm{ }}{\bf{2}}} \right)\).

How many ways are there for eight men and five women to stand in a line so that no two women stand next to each other? (Hint: First position the men and then consider possible positions for the women.)

How many positive integers between \(100\) and \(999\) inclusive are divisible by \(3\)and by \(4\) ?

Show that if \(n\)and\(k\)are positive integers, then\(\left( {\begin{array}{*{20}{c}}{n + 1}\\k\end{array}} \right) = (n + 1)\left( {\begin{array}{*{20}{c}}n\\{k - 1}\end{array}} \right)/k\). Use this identity to construct an inductive definition of the binomial coefficients.

How many ways are there to distribute 12 distinguishable objects into six distinguishable boxes so that two objects are placed in each box?

Find n if a) \({\bf{C}}\left( {{\bf{n}},{\rm{ }}{\bf{2}}} \right){\rm{ }} = {\rm{ }}{\bf{45}}.{\rm{ }}{\bf{b}}){\rm{ }}{\bf{C}}\left( {{\bf{n}},{\rm{ }}{\bf{3}}} \right){\rm{ }} = {\rm{ }}{\bf{P}}{\rm{ }}\left( {{\bf{n}},{\rm{ }}{\bf{2}}} \right).{\rm{ }}{\bf{c}}){\rm{ }}{\bf{C}}\left( {{\bf{n}},{\rm{ }}{\bf{5}}} \right){\rm{ }} = {\rm{ }}{\bf{C}}\left( {{\bf{n}},{\rm{ }}{\bf{2}}} \right)\)

How many ways are there for 10 women and six men to stand in a line so that no two men stand next to each other? (Hint: First position the women and then consider possible positions for the men.)