1.2: Enumeration
- Page ID
- 97849
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
Many basic problems in combinatorics involve counting the number of distributions of objects into cells—where we may or may not be able to distinguish between the objects and the same for the cells. Also, the cells may be arranged in patterns. Here are concrete examples.
Amanda has three children: Dawn, Keesha and Seth.
- Amanda has ten one dollar bills and decides to give the full amount to her children. How many ways can she do this? For example, one way she might distribute the funds is to give Dawn and Keesha four dollars each with Seth receiving the balance—two dollars. Another way is to give the entire amount to Keesha, an option that probably won't make Dawn and Seth very happy. Note that hidden within this question is the assumption that Amanda does not distinguish the individual dollar bills, say by carefully examining their serial numbers. Instead, we intend that she need only decide the amount each of the three children is to receive.
- The amounts of money distributed to the three children form a sequence which if written in non-increasing order has the form: \(a_1, a_2, a_3\) with \(a_1 \geq a_2 \geq a_3 \) and \(a_1 + a_2 + a_3 = 10\). How many such sequences are there?
- Suppose Amanda decides to give each child at least one dollar. How does this change the answers to the first two questions?
- Now suppose that Amanda has ten books, in fact the top 10 books from the New York Times best-seller list, and decides to give them to her children. How many ways can she do this? Again, we note that there is a hidden assumption—the ten books are all different.
- Suppose the ten books are labeled \(B_1, B_2, ... , B_{10} \). The sets of books given to the three children are pairwise disjoint and their union is {\(B_1, B_2, ... , B_{10} \)}. How many different sets of the form {\(S_1, S_2, S_3 \)} where \(S_1\), \(S_2\), and \(S_2\) are pairwise disjoint and \(S_1 \cup S_2 \cup S_3\) = {\(B_1, B_2, ... , B_{10} \)}?
- Suppose Amanda decides to give each child at least one book. How does this change the answers to the preceding two questions?
- How would we possibly answer these kinds of questions if ten was really ten thousand (OK, we're not talking about children any more!) and three was three thousand? Could you write the answer on a single page in a book?
A circular necklace with a total of six beads will be assembled using beads of three different colors. In Figure 1.1, we show four such necklaces—however, note that the first three are actually the same necklace. Each has three red beads, two blues and one green. On the other hand, the fourth necklace has the same number of beads of each color but it is a different necklace.
- How many different necklaces of six beads can be formed using three reds, two blues and one green?
- How many different necklaces of six beads can be formed using red, blue and green beads (not all colors have to be used)?
- How many different necklaces of six beads can be formed using red, blue and green beads if all three colors have to be used?
- How would we possibly answer these questions for necklaces of six thousand beads made with beads from three thousand different colors? What special software would be required to find the exact answer and how long would the computation take?