1_1_3A_Additive_and_Multiplicative_Principles
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/1%3A_Counting/1.1%3A_Additive_and_Multiplicative_Principles
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
Investigate!
1. A restaurant offers 8 appetizers and 14 entrées. How many choices do you have if:
1. you will eat one dish, either an appetizer or an entrée?
2. you are extra hungry and want to eat both an appetizer and an entrée?
2. Think about the methods you used to solve question 1. Write down the rules for these methods.
3. Do your rules work? A standard deck of playing cards has 26 red cards and 12 face cards.
1. How many ways can you select a card which is either red or a face card?
2. How many ways can you select a card which is both red and a face card?
3. How many ways can you select two cards so that the first one is red and the second one is a face card?
Consider this rather simple counting problem: at Red Dogs and Donuts, there are 14 varieties of donuts, and 16 types of hot dogs. If you want either a donut or a dog, how many options do you have? This isn't too hard, just add 14 and 16. Will that always work? What is important here?
Additive Principle
The additive principle states that if event \\A\\ can occur in \\m\\ ways, and event \\B\\ can occur in \\n\\ *disjoint* ways, then the event “\\A\\ or \\B\\” can occur in \\m + n\\ ways.
It is important that the events be disjoint : i.e., that there is no way for \\A\\ and \\B\\ to both happen at the same time. For example, a standard deck of 52 cards contains \\26\\ red cards and \\12\\ face cards. However, the number of ways to select a card which is either red or a face card is not \\26 + 12 = 38\text{.}\\ This is because there are 6 cards which are both red and face cards.
Example \\\PageIndex{1}\\
How many two letter “words” start with either A or B? (A word is just a string of letters; it doesn't have to be English, or even pronounceable.)
Solution
First, how many two letter words start with A? We just need to select the second letter, which can be accomplished in 26 ways. So there are 26 words starting with A. There are also 26 words that start with B. To select a word which starts with either A or B, we can pick the word from the first 26 or the second 26, for a total of 52 words.
The additive principle also works with more than two events. Say, in addition to your 14 choices for donuts and 16 for dogs, you would also consider eating one of 15 waffles? How many choices do you have now? You would have \\14 + 16 + 15 = 45\\ options.
Example \\\PageIndex{2}\\
How many two letter words start with one of the 5 vowels?
Solution
There are 26 two letter words starting with A, another 26 starting with E, and so on. We will have 5 groups of 26. So we add 26 to itself 5 times. Of course it would be easier to just multiply \\5\cdot 26\text{.}\\ We are really using the additive principle again, just using multiplication as a shortcut.
Example \\\PageIndex{3}\\
Suppose you are going for some fro-yo. You can pick one of 6 yogurt choices, and one of 4 toppings. How many choices do you have?
Solution
Break your choices up into disjoint events: \\A\\ are the choices with the first topping, \\B\\ the choices featuring the second topping, and so on. There are four events; each can occur in 6 ways (one for each yogurt flavor). The events are disjoint, so the total number of choices is \\6 + 6 + 6 + 6 = 24\text{.}\\
Note that in both of the previous examples, when using the additive principle on a bunch of events all the same size, it is quicker to multiply. This really is the same, and not just because \\6 + 6 + 6 + 6 = 4\cdot 6\text{.}\\ We can first select the topping in 4 ways (that is, we first select which of the disjoint events we will take). For each of those first 4 choices, we now have 6 choices of yogurt. We have:
Multiplicative Principle
The multiplicative principle states that if event \\A\\ can occur in \\m\\ ways, and each possibility for \\A\\ allows for exactly \\n\\ ways for event \\B\text{,}\\ then the event “\\A\\ and \\B\\” can occur in \\m \cdot n\\ ways.
The multiplicative principle generalizes to more than two events as well.
Example \\\PageIndex{4}\\
How many license plates can you make out of three letters followed by three numerical digits?
Solution
Here we have six events: the first letter, the second letter, the third letter, the first digit, the second digit, and the third digit. The first three events can each happen in 26 ways; the last three can each happen in 10 ways. So the total number of license plates will be \\26\cdot 26\cdot 26 \cdot 10 \cdot 10 \cdot 10\text{,}\\ using the multiplicative principle.
Does this make sense? Think about how we would pick a license plate. How many choices we would have? First, we need to pick the first letter. There are 26 choices. Now for each of those, there are 26 choices for the second letter: 26 second letters with first letter A, 26 second letters with first letter B, and so on. We add 26 to itself 26 times. Or quicker: there are \\26 \cdot 26\\ choices for the first two letters.
Now for each choice of the first two letters, we have 26 choices for the third letter. That is, 26 third letters for the first two letters AA, 26 choices for the third letter after starting AB, and so on. There are \\26 \cdot 26\\ of these \\26\\ third letter choices, for a total of \$26\cdot26)\cdot 26\\ choices for the first three letters. And for each of these \\26\cdot26\cdot26\\ choices of letters, we have a bunch of choices for the remaining digits.
In fact, there are going to be exactly 1000 choices for the numbers. We can see this because there are 1000 three-digit numbers (000 through 999). This is 10 choices for the first digit, 10 for the second, and 10 for the third. The multiplicative principle says we multiply: \\10\cdot 10 \cdot 10 = 1000\text{.}\\
All together, there were \\26^3\\ choices for the three letters, and \\10^3\\ choices for the numbers, so we have a total of \\26^3 \cdot 10^3\\ choices of license plates.
Careful: “and” doesn't mean “times.” For example, how many playing cards are both red and a face card? Not \\26 \cdot 12\text{.}\\ The answer is 6, and we needed to know something about cards to answer that question.
Another caution: how many ways can you select two cards, so that the first one is a red card and the second one is a face card? This looks more like the multiplicative principle (you are counting two separate events) but the answer is not \\26 \cdot 12\\ here either. The problem is that while there are 26 ways for the first card to be selected, it is not the case that *for each* of those there are 12 ways to select the second card. If the first card was both red and a face card, then there would be only 11 choices for the second card. 1 To solve this problem, you could break it into two cases. First, count how many ways there are to select the two cards when the first card is a red non-face card. Second, count how many ways when the first card is a red face card. Doing so makes the events in each separate case independent, so the multiplicative principle can be applied.
Counting functions
How many functions \\f:\\1,2,3,4,5\\ \to \\a,b,c,d\\\\ are there?
Solution
Remember that a function sends each element of the domain to exactly one element of the codomain. To determine a function, we just need to specify the image of each element in the domain. Where can we send 1? There are 4 choices. Where can we send 2? Again, 4 choices. What we have here is 5 “events” (picking the image of an element in the domain) each of which can happen in 4 ways (the choices for that image). Thus there are \\4 \cdot 4 \cdot 4 \cdot 4 \cdot 4 = 4^5\\ functions.
This is more than just an example of how we can use the multiplicative principle in a particular counting question. What we have here is a general interpretation of certain applications of the multiplicative principle using rigorously defined mathematical objects: functions. Whenever we have a counting question that asks for the the number of outcomes of a repeated event, we can interpret that as asking for the number of functions from \\\\1,2,\ldots, n\\\\ (where \\n\\ is the number of times the event is repeated) to \\\\1,2,\ldots,k\\\\ (where \\k\\ is the number of ways that event can occur).
Counting With Sets
Do you believe the additive and multiplicative principles? How would you convince someone they are correct? This is surprisingly difficult. They seem so simple, so obvious. But why do they work?
To make things clearer, and more mathematically rigorous, we will use sets. Do not skip this section! It might seem like we are just trying to give a proof of these principles, but we are doing a lot more. If we understand the additive and multiplicative principles rigorously, we will be better at applying them, and knowing when and when not to apply them at all.
We will look at the additive and multiplicative principles in a slightly different way. Instead of thinking about event \\A\\ and event \\B\text{,}\\ we want to think of a set \\A\\ and a set \\B\text{.}\\ The sets will contain all the different ways the event can happen. (It will be helpful to be able to switch back and forth between these two models when checking that we have counted correctly.) Here's what we mean:
Example \\\PageIndex{6}\\
Suppose you own 9 shirts and 5 pairs of pants.
1. How many outfits can you make?
2. If today is half-naked-day, and you will wear only a shirt or only a pair of pants, how many choices do you have?
Answer
By now you should agree that the answer to the first question is \\9 \cdot 5 = 45\\ and the answer to the second question is \\9 + 5 = 14\text{.}\\ These are the multiplicative and additive principles. There are two events: picking a shirt and picking a pair of pants. The first event can happen in 9 ways and the second event can happen in 5 ways. To get both a shirt and a pair of pants, you multiply. To get just one article of clothing, you add.
Now look at this using sets. There are two sets, call them \\S\\ and \\P\text{.}\\ The set \\S\\ contains all 9 shirts so \\\|S\| = 9\\ while \\\|P\| = 5\text{,}\\ since there are 5 elements in the set \\P\\ (namely your 5 pairs of pants). What are we asking in terms of these sets? Well in question 2, we really want \\\|S \cup P\|\text{,}\\ the number of elements in the union of shirts and pants. This is just \\\|S\| + \|P\|\\ (since there is no overlap; \\\|S \cap P\| = 0\$. Question 1 is slightly more complicated. Your first guess might be to find \\\|S \cap P\|\text{,}\\ but this is not right (there is nothing in the intersection). We are not asking for how many clothing items are both a shirt and a pair of pants. Instead, we want one of each. We could think of this as asking how many pairs \$x,y)\\ there are, where \\x\\ is a shirt and \\y\\ is a pair of pants. As we will soon verify, this number is \\\|S\| \cdot \|P\|\text{.}\\
From this example we can see right away how to rephrase our additive principle in terms of sets:
Additive Principle (with sets)
Given two sets \\A\\ and \\B\text{,}\\ if \\A \cap B = \emptyset\\ (that is, if there is no element in common to both \\A\\ and \\B\$, then
\begin{equation\*} \card{A \cup B} = \card{A} + \card{B}. \end{equation\*}
This hardly needs a proof. To find \\A \cup B\text{,}\\ you take everything in \\A\\ and throw in everything in \\B\text{.}\\ Since there is no element in both sets already, you will have \\\card{A}\\ things and add \\\card{B}\\ new things to it. This is what adding does! Of course, we can easily extend this to any number of disjoint sets.
From the example above, we see that in order to investigate the multiplicative principle carefully, we need to consider ordered pairs. We should define this carefully:
Cartesian Product
Given sets \\A\\ and \\B\text{,}\\ we can form the *set* \\A \times B = \$x,y) \st x \in A \wedge y \in B\\\\ to be the set of all ordered pairs \$x,y)\\ where \\x\\ is an element of \\A\\ and \\y\\ is an element of \\B\text{.}\\ We call \\A \times B\\ the Cartesian product of \\A\\ and \\B\text{.}\\
Example \\\PageIndex{7}\\
Let \\A = \\1,2\\\\ and \\B=\\3,4,5\\\text{.}\\ Find \\A \times B\text{.}\\
Answer
We want to find ordered pairs \$a,b)\\ where \\a\\ can be either \\1\\ or \\2\\ and \\b\\ can be either 3, 4, or 5. \\A \times B\\ is the set of all of these pairs:
\begin{equation\*} A \times B = \$1,3), (1,4), (1,5), (2,3), (2,4), (2,5)\\ \end{equation\*}
The question is, what is \\\card{A \times B}\text{?}\\ To figure this out, write out \\A \times B\text{.}\\ Let \\A = \\a_1,a_2, a_3, \ldots, a_m\\\\ and \\B = \\b_1,b_2, b_3, \ldots, b_n\\\\ (so \\\card{A} = m\\ and \\\card{B} = n\$. The set \\A \times B\\ contains all pairs with the first half of the pair being some \\a_i \in A\\ and the second being one of the \\b_j \in B\text{.}\\ In other words:
\begin{align\*}
A \times B = \\ & (a_1, b_1), (a_1, b_2), (a_1, b_3), \ldots (a_1, b_n),\\
& (a_2, b_1), (a_2, b_2), (a_2, b_3), \ldots, (a_2, b_n),\\
& (a_3, b_1), (a_3, b_2), (a_3, b_3), \ldots, (a_3, b_n),\\
& \vdots\\
& (a_m, b_1), (a_m, b_2), (a_m, b_3), \ldots, (a_m, b_n)\\.
\end{align\*}
Notice what we have done here: we made \\m\\ rows of \\n\\ pairs, for a total of \\m \cdot n\\ pairs.
Each row above is really \\\\a_i\\ \times B\\ for some \\a_i \in A\text{.}\\ That is, we fixed the \\A\\-element. Broken up this way, we have
\begin{equation\*} A \times B = (\\a_1\\ \times B) \cup (\\a_2\\ \times B) \cup (\\a_3\\\times B) \cup \cdots \cup (\\a_m\\ \times B). \end{equation\*}
So \\A \times B\\ is really the union of \\m\\ disjoint sets. Each of those sets has \\n\\ elements in them. The total (using the additive principle) is \\n + n + n + \cdots + n = m \cdot n\text{.}\\
To summarize:
Multiplicative Principle (with sets)
Given two sets \\A\\ and \\B\text{,}\\ we have \\\card{A \times B} = \card{A} \cdot \card{B}\text{.}\\
Again, we can easily extend this to any number of sets.
Principle of Inclusion/Exclusion
Investigate!
A recent buzz marketing campaign for *Village Inn* surveyed patrons on their pie preferences. People were asked whether they enjoyed (A) Apple, (B) Blueberry or (C) Cherry pie (respondents answered yes or no to each type of pie, and could say yes to more than one type). The following table shows the results of the survey.
| | | | | | | | |
|-------------------|-----|-----|-----|-----|-----|-----|-----|
| Pies enjoyed: | A | B | C | AB | AC | BC | ABC |
| Number of people: | 20 | 13 | 26 | 9 | 15 | 7 | 5 |
How many of those asked enjoy at least one of the kinds of pie? Also, explain why the answer is not 95.
While we are thinking about sets, consider what happens to the additive principle when the sets are NOT disjoint. Suppose we want to find \\\card{A \cup B}\\ and know that \\\card{A} = 10\\ and \\\card{B} = 8\text{.}\\ This is not enough information though. We do not know how many of the 8 elements in \\B\\ are also elements of \\A\text{.}\\ However, if we also know that \\\card{A \cap B} = 6\text{,}\\ then we can say exactly how many elements are in \\A\text{,}\\ and, of those, how many are in \\B\\ and how many are not (6 of the 10 elements are in \\B\text{,}\\ so 4 are in \\A\\ but not in \\B\$. We could fill in a Venn diagram as follows:
\![image-28.svg$$(https://math.libretexts.org/@api/deki/files/12818/image-28.svg?revision=1&size=bestfit&width=292&height=204)
\![$$(https://math.libretexts.org/images/image-28.svg)
This says there are 6 elements in \\A \cap B\text{,}\\ 4 elements in \\A \setminus B\\ and 2 elements in \\B \setminus A\text{.}\\ Now *these* three sets *are* disjoint, so we can use the additive principle to find the number of elements in \\A \cup B\text{.}\\ It is \\6 + 4 + 2 = 12\text{.}\\
This will always work, but drawing a Venn diagram is more than we need to do. In fact, it would be nice to relate this problem to the case where \\A\\ and \\B\\ are disjoint. Is there one rule we can make that works in either case?
Here is another way to get the answer to the problem above. Start by just adding \\\card{A} + \card{B}\text{.}\\ This is \\10 + 8 = 18\text{,}\\ which would be the answer if \\\card{A \cap B} = 0\text{.}\\ We see that we are off by exactly 6, which just so happens to be \\\card{A \cap B}\text{.}\\ So perhaps we guess,
\begin{equation\*} \card{A \cup B} = \card{A} + \card{B} - \card{A \cap B}. \end{equation\*}
This works for this one example. Will it always work? Think about what we are doing here. We want to know how many things are either in \\A\\ or \\B\\ (or both). We can throw in everything in \\A\text{,}\\ and everything in \\B\text{.}\\ This would give \\\card{A} + \card{B}\\ many elements. But of course when you actually take the union, you do not repeat elements that are in both. So far we have counted every element in \\A \cap B\\ exactly twice: once when we put in the elements from \\A\\ and once when we included the elements from \\B\text{.}\\ We correct by subtracting out the number of elements we have counted twice. So we added them in twice, subtracted once, leaving them counted only one time.
In other words, we have:
Cardinality of a union (2 sets)
For any finite sets \\A\\ and \\B\text{,}\\
\begin{equation\*} \card{A \cup B} = \card{A} + \card{B} - \card{A \cap B}. \end{equation\*}We can do something similar with three sets.
Example \\\PageIndex{8}\\
An examination in three subjects, Algebra, Biology, and Chemistry, was taken by 41 students. The following table shows how many students failed in each single subject and in their various combinations:
| | | | | | | | |
|----------|-----|-----|-----|-----|-----|-----|-----|
| Subject: | A | B | C | AB | AC | BC | ABC |
| Failed: | 12 | 5 | 8 | 2 | 6 | 3 | 1 |
How many students failed at least one subject?
Solution
The answer is not 37, even though the sum of the numbers above is 37. For example, while 12 students failed Algebra, 2 of those students also failed Biology, 6 also failed Chemestry, and 1 of those failed all three subjects. In fact, that 1 student who failed all three subjects is counted a total of 7 times in the total 37. To clarify things, let us think of the students who failed Algebra as the elements of the set \\A\text{,}\\ and similarly for sets \\B\\ and \\C\text{.}\\ The one student who failed all three subjects is the lone element of the set \\A \cap B \cap C\text{.}\\ Thus, in Venn diagrams:
\![$$(https://math.libretexts.org/images/image-29.svg)
Now let's fill in the other intersections. We know \\A\cap B\\ contains 2 elements, but 1 element has already been counted. So we should put a 1 in the region where \\A\\ and \\B\\ intersect (but \\C\\ does not). Similarly, we calculate the cardinality of \$A\cap C) \setminus B\text{,}\\ and \$B \cap C) \setminus A\text{:}\\
\![$$(https://math.libretexts.org/images/image-30.svg)
Next, we determine the numbers which should go in the remaining regions, including outside of all three circles. This last number is the number of students who did not fail any subject:
\![$$(https://math.libretexts.org/images/image-31.svg)
We found 5 goes in the “\\A\\ only” region because the entire circle for \\A\\ needed to have a total of 12, and 7 were already accounted for. Similarly, we calculate the “\\B\\ only” region to contain only 1 student and the “\\C\\ only” region to contain no students.
Thus the number of students who failed at least one class is 15 (the sum of the numbers in each of the eight disjoint regions). The number of students who passed all three classes is 26: the total number of students, 41, less the 15 who failed at least one class.
Note that we can also answer other questions. For example, now many students failed just Chemistry? None. How many passed Algebra but failed both Biology and Chemistry? This corresponds to the region inside both \\B\\ and \\C\\ but outside of \\A\text{,}\\ containing 2 students.
Could we have solved the problem above in an algebraic way? While the additive principle generalizes to any number of sets, when we add a third set here, we must be careful. With two sets, we needed to know the cardinalities of \\A\text{,}\\ \\B\text{,}\\ and \\A \cap B\\ in order to find the cardinality of \\A \cup B\text{.}\\ With three sets we need more information. There are more ways the sets can combine. Not surprisingly then, the formula for cardinality of the union of three non-disjoint sets is more complicated:
Cardinality of a union (3 sets)
For any finite sets \\A\text{,}\\ \\B\text{,}\\ and \\C\text{,}\\
\begin{equation\*} \card{A \cup B \cup C} = \card{A} + \card{B} + \card{C} - \card{A \cap B} - \card{A \cap C} - \card{B \cap C} + \card{A \cap B \cap C} \end{equation\*}To determine how many elements are in at least one of \\A\text{,}\\ \\B\text{,}\\ or \\C\\ we add up all the elements in each of those sets. However, when we do that, any element in both \\A\\ and \\B\\ is counted twice. Also, each element in both \\A\\ and \\C\\ is counted twice, as are elements in \\B\\ and \\C\text{,}\\ so we take each of those out of our sum once. But now what about the elements which are in \\A \cap B \cap C\\ (in all three sets)? We added them in three times, but also removed them three times. They have not yet been counted. Thus we add those elements back in at the end.
Returning to our example above, we have \\\card{A} = 12\text{,}\\ \\\card{B} = 5\text{,}\\ \\\card{C} = 8\text{.}\\ We also have \\\card{A \cap B} = 2\text{,}\\ \\\card{A \cap C} = 6\text{,}\\ \\\card{B \cap C} = 3\text{,}\\ and \\\card{A \cap B \cap C} = 1\text{.}\\ Therefore:
\begin{equation\*} \card{A \cup B \cup C} = 12 + 5 + 8 - 2 - 6 - 3 + 1 = 15 \end{equation\*}
This is what we got when we solved the problem using Venn diagrams.
This process of adding in, then taking out, then adding back in, and so on is called the *Principle of Inclusion/Exclusion*, or simply PIE. We will return to this counting technique later to solve for more complicated problems (involving more than 3 sets).
---
1_2_3A_Binomial_Coefficients
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/1%3A_Counting/1.2%3A_Binomial_Coefficients
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
Investigate!
In chess, a rook can move only in straight lines (not diagonally). Fill in each square of the chess board below with the number of different shortest paths the rook, in the upper left corner, can take to get to that square. For example, one square is already filled in. There are six different paths from the rook to the square: DDRR (down down right right), DRDR, DRRD, RDDR, RDRD and RRDD.
\![chessboard.svg$$(https://math.libretexts.org/@api/deki/files/12811/chessboard.svg?revision=1&size=bestfit&width=295&height=295)
\![$$(https://math.libretexts.org/images/chessboard.svg)
Here are some apparently different discrete objects we can count: subsets, bit strings, lattice paths, and binomial coefficients. We will give an example of each type of counting problem (and say what these things even are). As we will see, these counting problems are surprisingly similar.
Subsets
Subsets should be familiar, otherwise read over Section 0.3 again. Suppose we look at the set \\A = \\1,2,3,4,5\\\\. How many subsets of \\A\\ contain exactly 3 elements?
First, a simpler question: How many subsets of \\A\\ are there total? In other words, what is \\\|\pow(A)\|\\ (the cardinality of the power set of \\A\$? Think about how we would build a subset. We need to decide, for each of the elements of \\A\text{,}\\ whether or not to include the element in our subset. So we need to decide “yes” or “no” for the element 1. And for each choice we make, we need to decide “yes” or “no” for the element 2. And so on. For each of the 5 elements, we have 2 choices. Therefore the number of subsets is simply \\2\cdot 2\cdot 2 \cdot 2\cdot 2 = 2^5\\ (by the multiplicative principle).
Of those 32 subsets, how many have 3 elements? This is not obvious. Note that we cannot just use the multiplicative principle. Maybe we want to say we have 2 choices (yes/no) for the first element, 2 choices for the second, 2 choices for the third, and then only 1 choice for the other two. But what if we said “no” to one of the first three elements? Then we would have two choices for the 4th element. What a mess!
Another (bad) idea: we need to pick three elements to be in our subset. There are 5 elements to choose from. So there are 5 choices for the first element, and for each of those 4 choices for the second, and then 3 for the third (last) element. The multiplicative principle would say then that there are a total of \\5 \cdot 4 \cdot 3 = 60\\ ways to select the 3 element subset. But this cannot be correct (\\60 \> 32\\ for one thing). One of the outcomes we would get from these choices would be the set \\\\3,2,5\\\text{,}\\ by choosing the element 3 first, then the element 2, then the element 5. Another outcome would be \\\\5,2,3\\\\ by choosing the element 5 first, then the element 2, then the element 3. But these are the same set! We can correct this by dividing: for each set of three elements, there are 6 outcomes counted amoung our 60 (since there are 3 choices for which element we list first, 2 for which we list second, and 1 for which we list last). So we expect there to be 10 3-element subsets of \\A\\.
Is this right? Well, we could list out all 10 of them, being very systematic in doing so, to make sure we don't miss any or list any twice. Or we could try to count how many subsets of \\A\\ *don't* have 3 elements in them. How many have no elements? Just 1 (the empty set). How many have 5? Again, just 1. These are the cases in which we say “no” to all elements, or “yes” to all elements. Okay, what about the subsets which contain a single element? There are 5 of these. We must say “yes” to exactly one element, and there are 5 to choose from. This is also the number of subsets containing 4 elements. Those are the ones for which we must say “no” to exactly one element.
So far we have counted 12 of the 32 subsets. We have not yet counted the subsets with cardinality 2 and with cardinality 3. There are a total of 20 subsets left to split up between these two groups. But the number of each must be the same! If we say “yes” to exactly two elements, that can be accomplished in exactly the same number of ways as the number of ways we can say “no” to exactly two elements. So the number of 2-element subsets is equal to the number of 3-element subsets. Together there are 20 of these subsets, so 10 each.
| | | | | | | |
|---------------------|-----|-----|-----|-----|-----|-----|
| Number of elements: | 0 | 1 | 2 | 3 | 4 | 5 |
| Number of subsets: | 1 | 5 | 10 | 10 | 5 | 1 |
Bit Strings
“Bit” is short for “binary digit,” so a bit string is a string of binary digits. The binary digits are simply the numbers 0 and 1. All of the following are bit strings:
\begin{equation\*} 1001 \quad 0 \quad 1111 \quad 1010101010 \end{equation\*}
The number of bits (0's or 1's) in the string is the length of the string; the strings above have lengths 4, 1, 4, and 10 respectively. We also can ask how many of the bits are 1's. The number of 1's in a bit string is the weight of the string; the weights of the above strings are 2, 0, 4, and 5 respectively.
Definition: Bit Strings
- An \\n\\-bit string is a bit string of length \\n\\. That is, it is a string containing \\n\\ symbols, each of which is a bit, either 0 or 1.
- The weight of a bit string is the number of 1's in it.
- \\\B^n\\ is the *set* of all \\n\\-bit strings.
- \\\B^n_k\\ is the set of all \\n\\-bit strings of weight \\k\\.
For example, the elements of the set \\\B^3_2\\ are the bit strings 011, 101, and 110. Those are the only strings containing three bits exactly two of which are 1's.
The counting questions: How many bit strings have length 5? How many of those have weight 3? In other words, we are asking for the cardinalities \\\|\B^5\|\\ and \\\|\B^5_3\|\\.
To find the number of 5-bit strings is straight forward. We have 5 bits, and each can either be a 0 or a 1. So there are 2 choices for the first bit, 2 choices for the second, and so on. By the multiplicative principle, there are \\2 \cdot 2 \cdot 2\cdot 2 \cdot 2 = 2^5 = 32\\ such strings.
Finding the number of 5-bit strings of weight 3 is harder. Think about how such a string could start. The first bit must be either a 0 or a 1. In the first case (the string starts with a 0), we must then decide on four more bits. To have a total of three 1's, among those four remaining bits there must be three 1's. To count all of these strings, we must include all 4-bit strings of weight 3. In the second case (the string starts with a 1), we still have four bits to choose, but now only two of them can be 1's, so we should look at all the 4-bit strings of weight 2. So the strings in \\\B^5_3\\ all have the form \\1\B^4_2\\ (that is, a 1 followed by a string from \\\B^4_2\$ or \\0\B^4_3\\. These two sets are disjoint, so we can use the additive principle:
\begin{equation\*} \|\B^5_3\| = \|\B^4_2\| + \|\B^4_3\|. \end{equation\*}
This is an example of a recurrence relation . We represented one instance of our counting problem in terms of two simpler instances of the problem. If only we knew the cardinalities of \\\B^4_2\\ and \\\B^4_3\\. Repeating the same reasoning,
\begin{equation\*} \|\B^4_2\| = \|\B^3_1\| + \|\B^3_2\| \quad \mbox{and} \quad \|\B^4_3\| = \|\B^3_2\| + \|\B^3_3\|. \end{equation\*}
We can keep going down, but this should be good enough. Both \\\B^3_1\\ and \\\B^3_2\\ contain 3 bit strings: we must pick one of the three bits to be a 1 (three ways to do that) or one of the three bits to be a 0 (three ways to do that). Also, \\\B^3_3\\ contains just one string: 111. Thus \\\|\B^4_2\| = 6\\ and \\\|\B^4_3\| = 4\text{,}\\ which puts \\\B^5_3\\ at a total of 10 strings.
But wait —32 and 10 were the answers to the counting questions about subsets. Coincidence? Not at all. Each bit string can be thought of as a *code* for a subset. For the set \\A = \\1,2,3,4,5\\\text{,}\\ we would use 5-bit strings, one bit for each element of \\A\\. Each bit in the string is a 0 if its corresponding element of \\A\\ is not in the subset, and a 1 if the element of \\A\\ is in the subset. Remember, deciding the subset amounted to a sequence of five yes/no votes for the elements of \\A\\. Instead of yes, we put a 1; instead of no, we put a 0.
For example, the bit string \\11001\\ represents the subset \\\\1,2,5\\\\ since the first, second and fifth bits are 1's. The subset \\\\3,5\\\\ would be coded by the string \\00101\\. What we really have here is a bijection from \\\pow(A)\\ to \\\B^5\\.
Now for a subset to contain exactly three elements, the corresponding bit string must contain exactly three 1's. In other words, the weight must be 3. Thus counting the number of 3-element subsets of \\A\\ is the same as counting the number 5-bit strings of weight 3.
Lattice Paths
The integer lattice is the set of all points in the Cartesian plane for which both the \\x\\ and \\y\\ coordinates are integers. If you like to draw graphs on graph paper, the lattice is the set of all the intersections of the grid lines.
A lattice path is one of the shortest possible paths connecting two points on the lattice, moving only horizontally and vertically. For example, here are three possible lattice paths from the points \$0,0)\\ to \$3,2)\text{:}\\
\![lattice-path-1.svg$$(https://math.libretexts.org/@api/deki/files/12812/lattice-path-1.svg?revision=1&size=bestfit&width=258&height=165)\![lattice-path-3.svg$$(https://math.libretexts.org/@api/deki/files/12814/lattice-path-3.svg?revision=1&size=bestfit&width=258&height=165)\![lattice-path-2.svg$$(https://math.libretexts.org/@api/deki/files/12813/lattice-path-2.svg?revision=1&size=bestfit&width=258&height=165)
\![$$(https://math.libretexts.org/images/lattice-path-1.svg) \![$$(https://math.libretexts.org/images/lattice-path-2.svg) \![$$(https://math.libretexts.org/images/lattice-path-3.svg)
Notice to ensure the path is the *shortest* possible, each move must be either to the right or up. Additionally, in this case, note that no matter what path we take, we must make three steps right and two steps up. No matter what order we make these steps, there will always be 5 steps. Thus each path has *length* 5.
The counting question: how many lattice paths are there between \$0,0)\\ and \$3,2)\text{?}\\ We could try to draw all of these, or instead of drawing them, maybe just list which direction we travel on each of the 5 steps. One path might be RRUUR, or maybe UURRR, or perhaps RURRU (those correspond to the three paths drawn above). So how many such strings of R's and U's are there?
Notice that each of these strings must contain 5 symbols. Exactly 3 of them must be R's (since our destination is 3 units to the right). This seems awfully familiar. In fact, what if we used \\1\\'s instead of R's and 0's instead of U's? Then we would just have 5-bit strings of weight 3. There are 10 of those, so there are 10 lattice paths from (0,0) to (3,2).
The correspondence between bit strings and lattice paths does not stop there. Here is another way to count lattice paths. Consider the lattice shown below:
\![lattice-ab.svg$$(https://math.libretexts.org/@api/deki/files/12815/lattice-ab.svg?revision=1&size=bestfit&width=290&height=185)
\![$$(https://math.libretexts.org/images/lattice-ab.svg)
Any lattice path from (0,0) to (3,2) must pass through exactly one of \\A\\ and \\B\\. The point \\A\\ is 4 steps away from (0,0) and two of them are towards the right. The number of lattice paths to \\A\\ is the same as the number of 4-bit strings of weight 2, namely 6. The point \\B\\ is 4 steps away from (0,0), but now 3 of them are towards the right. So the number of paths to point \\B\\ is the same as the number of 4-bit strings of weight 3, namely 4. So the total number of paths to (3,2) is just \\6+4\\. This is the same way we calculated the number of 5-bit strings of weight 3. The point: the exact same recurrence relation exists for bit strings and for lattice paths.
Binomial Coefficients
Binomial coefficients are the coefficients in the expanded version of a binomial, such as \$x+y)^5\\. What happens when we multiply such a binomial out? We will expand \$x+y)^n\\ for various values of \\n\\. Each of these are done by multiplying everything out (i.e., FOIL-ing) and then collecting like terms.
\begin{equation\*} (x+y)^1 = x + y \end{equation\*} \begin{equation\*} (x+y)^2 = x^2 + 2xy + y^2 \end{equation\*} \begin{equation\*} (x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3 \end{equation\*} \begin{equation\*} (x+y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4. \end{equation\*}
In fact, there is a quicker way to expand the above binomials. For example, consider the next one, \$x+y)^5\\. What we are really doing is multiplying out,
\begin{equation\*} (x+y)(x+y)(x+y)(x+y)(x+y). \end{equation\*}
If that looks daunting, go back to the case of \$x+y)^3 = (x+y)(x+y)(x+y)\\. Why do we only have one \\x^3\\ and \\y^3\\ but three \\x^2y\\ and \\xy^2\\ terms? Every time we distribute over an \$x+y)\\ we create two copies of what is left, one multiplied by \\x\text{,}\\ the other multiplied by \\y\\. To get \\x^3\text{,}\\ we need to pick the “multiplied by \\x\\” side every time (we don't have any \\y\\'s in the term). This will only happen once. On the other hand, to get \\x^2y\\ we need to select the \\x\\ side twice and the \\y\\ side once. In other words, we need to pick one of the three \$x+y)\\ terms to “contribute” their \\y\\.
Similarly, in the expansion of \$x+y)^5\text{,}\\ there will be only one \\x^5\\ term and one \\y^5\\ term. This is because to get an \\x^5\text{,}\\ we need to use the \\x\\ term in each of the copies of the binomial \$x+y)\text{,}\\ and similarly for \\y^5\\. What about \\x^4y\text{?}\\ To get terms like this, we need to use four \\x\\'s and one \\y\text{,}\\ so we need exactly one of the five binomials to contribute a \\y\\. There are 5 choices for this, so there are 5 ways to get \\x^4y\text{,}\\ so the coefficient of \\x^4y\\ is 5. This is also the coefficient for \\xy^4\\ for the same (but opposite) reason: there are 5 ways to pick which of the 5 binomials contribute the single \\x\\. So far we have
\begin{equation\*} (x+y)^5 = x^5 + 5x^4y + \underline{~?~}~x^3y^2 + \underline{~?~}~x^2y^3 + 5 xy^4 + y^5. \end{equation\*}
We still need the coefficients of \\x^3y^2\\ and \\x^2y^3\\. In both cases, we need to pick exactly 3 of the 5 binomials to contribute one variable, the other two to contribute the other. Wait. This sounds familiar. We have 5 things, each can be one of two things, and we need a total of 3 of one of them. That's just like taking 5 bits and making sure exactly 3 of them are 1's. So the coefficient of \\x^3y^2\\ (and also \\x^2y^3\$ will be exactly the same as the number of bit strings of length 5 and weight 3, which we found earlier to be 10. So we have:
\begin{equation\*} (x+y)^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5 xy^4 + y^5. \end{equation\*}
These numbers we keep seeing over and over again. They are the number of subsets of a particular size, the number of bit strings of a particular weight, the number of lattice paths, and the coefficients of these binomial products. We will call them binomial coefficients . We even have a special symbol for them: \\{n \choose k}\\.
Definition: Binomial Coefficients
For each integer \\n \ge 0\\ and integer \\k\\ with \\0 \le k \le n\\ there is a number
\begin{equation\*} {n\choose k} \end{equation\*}
read “\\n\\ choose \\k\\.” We have:
- \\{n\choose k} = \|\B^n_k\|\text{,}\\ the number of \\n\\-bit strings of weight \\k\\.
- \\{n \choose k}\\ is the number of subsets of a set of size \\n\\ each with cardinality \\k\\.
- \\{n \choose k}\\ is the number of lattice paths of length \\n\\ containing \\k\\ steps to the right.
- \\{n \choose k}\\ is the coefficient of \\x^ky^{n-k}\\ in the expansion of \$x+y)^n\\.
- \\{n \choose k}\\ is the number of ways to select \\k\\ objects from a total of \\n\\ objects.
The last bullet point is usually taken as the definition of \\{n \choose k}\\. Out of \\n\\ objects we must choose \\k\\ of them, so there are \\n\\ choose \\k\\ ways of doing this. Each of our counting problems above can be viewed in this way:
- How many subsets of \\\\1,2,3,4,5\\\\ contain exactly 3 elements? We must choose \\3\\ of the 5 elements to be in our subset. There are \\{5 \choose 3}\\ ways to do this, so there are \\{5 \choose 3}\\ such subsets.
- How many bit strings have length 5 and weight 3? We must choose \\3\\ of the 5 bits to be 1's. There are \\{5 \choose 3}\\ ways to do this, so there are \\{5 \choose 3}\\ such bit strings.
- How many lattice paths are there from (0,0) to (3,2)? We must choose 3 of the 5 steps to be towards the right. There are \\{5 \choose 3}\\ ways to do this, so there are \\{5 \choose 3}\\ such lattice paths.
- What is the coefficient of \\x^3y^2\\ in the expansion of \$x+y)^5\text{?}\\ We must choose 3 of the 5 copies of the binomial to contribute an \\x\\. There are \\{5 \choose 3}\\ ways to do this, so the coefficient is \\{5 \choose 3}\\.
It should be clear that in each case above, we have the right answer. All we had to do is phrase the question correctly and it became obvious that \\{5 \choose 3}\\ is correct. However, this does not tell us that the answer is in fact 10 in each case. We will eventually find a formula for \\{n \choose k}\text{,}\\ but for now, look back at how we arrived at the answer 10 in our counting problems above. It all came down to bit strings, and we have a recurrence relation for bit strings:
\begin{equation\*} \|\B^n_k\| = \|\B^{n-1}\_{k-1}\| + \|\B^{n-1}\_k\|. \end{equation\*}
Remember, this is because we can start the bit string with either a 1 or a 0. In both cases, we have \\n-1\\ more bits to pick. The strings starting with 1 must contain \\k-1\\ more 1's, while the strings starting with 0 still need \\k\\ more 1's.
Since \\\|\B^n_k\| = {n \choose k}\text{,}\\ the same recurrence relation holds for binomial coefficients:
Recurrence relation for \\{n \choose k}\\
\begin{equation\*} {n \choose k} = {n-1 \choose k-1} + {n-1 \choose k} \end{equation\*}
Pascal's Triangle
Let's arrange the binomial coefficients \\{n \choose k}\\ into a triangle like follows:
\![pascal-nCk.svg$$(https://math.libretexts.org/@api/deki/files/12816/pascal-nCk.svg?revision=1&size=bestfit&width=386&height=224)
\![$$(https://math.libretexts.org/images/pascal-nCk.svg)
This can continue as far down as we like. The recurrence relation for \\{n \choose k}\\ tells us that each entry in the triangle is the sum of the two entries above it. The entries on the sides of the triangle are always 1. This is because \\{n \choose 0} = 1\\ for all \\n\\ since there is only one way to pick 0 of \\n\\ objects and \\{n \choose n} = 1\\ since there is one way to select all \\n\\ out of \\n\\ objects. Using the recurrence relation, and the fact that the sides of the triangle are 1's, we can easily replace all the entries above with the correct values of \\{n \choose k}\\. Doing so gives us Pascal's triangle .
\![pascal-large.svg$$(https://math.libretexts.org/@api/deki/files/12817/pascal-large.svg?revision=1&size=bestfit&width=795&height=817)
We can use Pascal's triangle to calculate binomial coefficients. For example, using the triangle below, we can find \\{12 \choose 6} = 924\\.
\![$$(https://math.libretexts.org/images/pascal-large.svg)
---
1_3_3A_Combinations_and_Permutations
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/1%3A_Counting/1.3%3A_Combinations_and_Permutations
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
Investigate!
You have a bunch of chips which come in five different colors: red, blue, green, purple and yellow.
1. How many different two-chip stacks can you make if the bottom chip must be red or blue? Explain your answer using both the additive and multiplicative principles.
2. How many different three-chip stacks can you make if the bottom chip must be red or blue and the top chip must be green, purple or yellow? How does this problem relate to the previous one?
3. How many different three-chip stacks are there in which no color is repeated? What about four-chip stacks?
4. Suppose you wanted to take three different colored chips and put them in your pocket. How many different choices do you have? What if you wanted four different colored chips? How do these problems relate to the previous one?
A permutation is a (possible) rearrangement of objects. For example, there are 6 permutations of the letters *a, b, c*:
\begin{equation\*} abc, \~~ acb, \~~ bac, \~~bca, \~~ cab, \~~ cba. \end{equation\*}
We know that we have them all listed above —there are 3 choices for which letter we put first, then 2 choices for which letter comes next, which leaves only 1 choice for the last letter. The multiplicative principle says we multiply \\3\cdot 2 \cdot 1\text{.}\\
Example \\\PageIndex{1}\\
How many permutations are there of the letters *a, b, c, d, e, f*?
Answer
We do NOT want to try to list all of these out. However, if we did, we would need to pick a letter to write down first. There are 6 choices for that letter. For each choice of first letter, there are 5 choices for the second letter (we cannot repeat the first letter; we are rearranging letters and only have one of each), and for each of those, there are 4 choices for the third, 3 choices for the fourth, 2 choices for the fifth and finally only 1 choice for the last letter. So there are \\6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720\\ permutations of the 6 letters.
A piece of notation is helpful here: \\n!\text{,}\\ read “\\n\\ factorial”, is the product of all positive integers less than or equal to \\n\\ (for reasons of convenience, we also define 0! to be 1). So the number of permutation of 6 letters, as seen in the previous example is \\6! = 6\cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\text{.}\\ This generalizes:
Permutations of \\n\\ elements
There are \\n! = n\cdot (n-1)\cdot (n-2)\cdot \cdots \cdot 2\cdot 1\\ permutations of \\n\\ (distinct) elements.
Counting Bijective Functions
How many functions \\f:\\1,2,\ldots,8\\ \to \\1,2,\ldots, 8\\\\ are *bijective*?
Solution
Remember what it means for a function to be bijective: each element in the codomain must be the image of exactly one element of the domain. Using two-line notation, we could write one of these bijections as
\begin{equation\*} f = \twoline{1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \amp 7 \amp 8} {3 \amp 1 \amp 5 \amp 8 \amp 7 \amp 6 \amp 2 \amp 4} \end{equation\*}
What we are really doing is just rearranging the elements of the codomain, so we are creating a permutation of 8 elements. In fact, “permutation” is another term used to describe bijective functions from a finite set to itself.
If you believe this, then you see the answer must be \\8! = 8 \cdot 7 \cdot\cdots\cdot 1 = 40320\text{.}\\ You can see this directly as well: for each element of the domain, we must pick a distinct element of the codomain to map to. There are 8 choices for where to send 1, then 7 choices for where to send 2, and so on. We multiply using the multiplicative principle.
Sometimes we do not want to permute all of the letters/numbers/elements we are given.
Example \\\PageIndex{3}\\
How many 4 letter “words” can you make from the letters *a* through *f*, with no repeated letters?
Solution
This is just like the problem of permuting 4 letters, only now we have more choices for each letter. For the first letter, there are 6 choices. For each of those, there are 5 choices for the second letter. Then there are 4 choices for the third letter, and 3 choices for the last letter. The total number of words is \\6\cdot 5\cdot 4 \cdot 3 = 360\text{.}\\ This is not \\6!\\ because we never multiplied by 2 and 1. We could start with \\6!\\ and then cancel the 2 and 1, and thus write \\\frac{6!}{2!}\text{.}\\
In general, we can ask how many permutations exist of \\k\\ objects choosing those objects from a larger collection of \\n\\ objects. (In the example above, \\k = 4\text{,}\\ and \\n = 6\text{.}\$ We write this number \\P(n,k)\\ and sometimes call it a \\k\\-permutation of \\n\\ elements . From the example above, we see that to compute \\P(n,k)\\ we must apply the multiplicative principle to \\k\\ numbers, starting with \\n\\ and counting backwards. For example
\begin{equation\*} P(10, 4) = 10\cdot 9 \cdot 8 \cdot 7. \end{equation\*}
Notice again that \\P(10,4)\\ starts out looking like \\10!\text{,}\\ but we stop after 7. We can formally account for this “stopping” by dividing away the part of the factorial we do not want:
\begin{equation\*} P(10,4) = \frac{10\cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1} = \frac{10!}{6!}. \end{equation\*}
Careful: The factorial in the denominator is not \\4!\\ but rather \$10-4)!\text{.}\\
\\k\\-permutations of \\n\\ elements
\\P(n,k)\\ is the number of \\k\\-permutations of \\n\\ elements, the number of ways to arrange \\k\\ objects chosen from \\n\\ distinct objects.
\begin{equation\*} P(n,k) = \frac{n!}{(n-k)!}. \end{equation\*}
Note that when \\n = k\text{,}\\ we have \\P(n,n) = \frac{n!}{(n-n)!} = n!\\ (since we defined \\0!\\ to be 1). This makes sense —we already know \\n!\\ gives the number of permutations of all \\n\\ objects.
Counting injective functions
How many functions \\f:\\1,2,3\\ \to \\1,2,3,4,5,6,7,8\\\\ are *injective*?
Solution
Note that it doesn't make sense to ask for the number of *bijections* here, as there are none (because the codomain is larger than the domain, there are no surjections). But for a function to be injective, we just can't use an element of the codomain more than once.
We need to pick an element from the codomain to be the image of 1. There are 8 choices. Then we need to pick one of the remaining 7 elements to be the image of 2. Finally, one of the remaining 6 elements must be the image of 3. So the total number of functions is \\8\cdot 7 \cdot 6 = P(8,3)\text{.}\\
What this demonstrates in general is that the number of injections \\f:A \to B\text{,}\\ where \\\card{A} = k\\ and \\\card{B} = n\text{,}\\ is \\P(n,k)\text{.}\\
Here is another way to find the number of \\k\\-permutations of \\n\\ elements: first select which \\k\\ elements will be in the permutation, then count how many ways there are to arrange them. Once you have selected the \\k\\ objects, we know there are \\k!\\ ways to arrange (permute) them. But how do you select \\k\\ objects from the \\n\text{?}\\ You have \\n\\ objects, and you need to *choose* \\k\\ of them. You can do that in \\{n \choose k}\\ ways. Then for each choice of those \\k\\ elements, we can permute *them* in \\k!\\ ways. Using the multiplicative principle, we get another formula for \\P(n,k)\text{:}\\
\begin{equation\*} P(n,k) = {n \choose k}\cdot k!. \end{equation\*}
Now since we have a closed formula for \\P(n,k)\\ already, we can substitute that in:
\begin{equation\*} \frac{n!}{(n-k)!} = {n \choose k} \cdot k!. \end{equation\*}
If we divide both sides by \\k!\\ we get a closed formula for \\{n \choose k}\text{.}\\
Closed formula for \\{n \choose k}\\
\begin{equation\*} {n \choose k} = \frac{n!}{(n-k)!k!} \end{equation\*}
We say \\P(n,k)\\ counts *permutations*, and \\{n \choose k}\\ counts *combinations*. The formulas for each are very similar, there is just an extra \\k!\\ in the denominator of \\{n \choose k}\text{.}\\ That extra \\k!\\ accounts for the fact that \\{n \choose k}\\ does not distinguish between the different orders that the \\k\\ objects can appear in. We are just selecting (or choosing) the \\k\\ objects, not arranging them. Perhaps “combination” is a misleading label. We don't mean it like a combination lock (where the order would definitely matter). Perhaps a better metaphor is a combination of flavors — you just need to decide which flavors to combine, not the order in which to combine them.
To further illustrate the connection between combinations and permutations, we close with an example.
Example \\\PageIndex{5}\\
You decide to have a dinner party. Even though you are incredibly popular and have 14 different friends, you only have enough chairs to invite 6 of them.
1. How many choices do you have for which 6 friends to invite?
2. What if you need to decide not only which friends to invite but also where to seat them along your long table? How many choices do you have then?
Solution
1. You must simply choose 6 friends from a group of 14. This can be done in \\{14 \choose 6}\\ ways. We can find this number either by using Pascal's triangle or the closed formula: \\\frac{14!}{8!\cdot 6!} = 3003\text{.}\\
2. Here you must count all the ways you can permute 6 friends chosen from a group of 14. So the answer is \\P(14, 6)\text{,}\\ which can be calculated as \\\frac{14!}{8!} = 2192190\text{.}\\
Notice that we can think of this counting problem as a question about counting functions: how many injective functions are there from your set of 6 chairs to your set of 14 friends (the functions are injective because you can't have a single chair go to two of your friends).
How are these numbers related? Notice that \\P(14,6)\\ is much larger than \\{14 \choose 6}\text{.}\\ This makes sense. \\{14 \choose 6}\\ picks 6 friends, but \\P(14,6)\\ arranges the 6 friends as well as picks them. In fact, we can say exactly how much larger \\P(14,6)\\ is. In both counting problems we choose 6 out of 14 friends. For the first one, we stop there, at 3003 ways. But for the second counting problem, each of those 3003 choices of 6 friends can be arranged in exactly \\6!\\ ways. So now we have \\3003\cdot 6!\\ choices and that is exactly \\2192190\text{.}\\
Alternatively, look at the first problem another way. We want to select 6 out of 14 friends, but we do not care about the order they are selected in. To select 6 out of 14 friends, we might try this:
\begin{equation\*} 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9. \end{equation\*}
This is a reasonable guess, since we have 14 choices for the first guest, then 13 for the second, and so on. But the guess is wrong (in fact, that product is exactly \\2192190 = P(14,6)\$. It distinguishes between the different orders in which we could invite the guests. To correct for this, we could divide by the number of different arrangements of the 6 guests (so that all of these would count as just one outcome). There are precisely \\6!\\ ways to arrange 6 guests, so the correct answer to the first question is
\begin{equation\*} \frac{14 \cdot 13 \cdot 12 \cdot 11\cdot 10 \cdot 9}{6!}. \end{equation\*}
Note that another way to write this is
\begin{equation\*} \frac{14!}{8!\cdot 6!}. \end{equation\*}
which is what we had originally.
---
1_4_3A_Combinatorial_Proofs
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/1%3A_Counting/1.4%3A_Combinatorial_Proofs
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
Investigate!
1. The Stanley Cup is decided in a best of 7 tournament between two teams. In how many ways can your team win? Let's answer this question two ways:
1. How many of the 7 games does your team need to win? How many ways can this happen?
2. What if the tournament goes all 7 games? So you win the last game. How many ways can the first 6 games go down?
3. What if the tournament goes just 6 games? How many ways can this happen? What about 5 games? 4 games?
4. What are the two different ways to compute the number of ways your team can win? Write down an equation involving binomial coefficients (that is, \\{n \choose k}\\'s). What pattern in Pascal's triangle is this an example of?
2. Generalize. What if the rules changed and you played a best of \\9\\ tournament (5 wins required)? What if you played an \\n\\ game tournament with \\k\\ wins required to be named champion?
Patterns in Pascal's Triangle
Have a look again at Pascal's triangle. Forget for a moment where it comes from. Just look at it as a mathematical object. What do you notice?
\![pascal-small.svg$$(https://math.libretexts.org/@api/deki/files/12809/pascal-small.svg?revision=1&size=bestfit&width=358&height=324)
\![$$(https://math.libretexts.org/images/pascal-small.svg)
There are lots of patterns hidden away in the triangle, enough to fill a reasonably sized book. Here are just a few of the most obvious ones:
1. The entries on the border of the triangle are all 1.
2. Any entry not on the border is the sum of the two entries above it.
3. The triangle is symmetric. In any row, entries on the left side are mirrored on the right side.
4. The sum of all entries on a given row is a power of 2. (You should check this!)
We would like to state these observations in a more precise way, and then prove that they are correct. Now each entry in Pascal's triangle is in fact a binomial coefficient. The 1 on the very top of the triangle is \\{0 \choose 0}\\. The next row (which we will call row 1, even though it is not the top-most row) consists of \\{1 \choose 0}\\ and \\{1 \choose 1}\\. Row 4 (the row 1, 4, 6, 4, 1) consists of the binomial coefficients
\begin{equation\*} {4 \choose 0} \~~ {4 \choose 1} \~~ {4 \choose 2} \~~ {4 \choose 3} \~~ {4 \choose 4}. \end{equation\*}
Given this description of the elements in Pascal's triangle, we can rewrite the above observations as follows:
1. \\{n \choose 0} = 1\\ and \\{n \choose n} = 1\\.
2. \\{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\\.
3. \\{n \choose k} = {n \choose n-k}\\.
4. \\{n\choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n\\.
Each of these is an example of a binomial identity : an identity (i.e., equation) involving binomial coefficients.
Our goal is to establish these identities. We wish to prove that they hold for all values of \\n\\ and \\k\\. These proofs can be done in many ways. One option would be to give algebraic proofs, using the formula for \\{n \choose k}\text{:}\\
\begin{equation\*} {n \choose k} = \frac{n!}{(n-k)!\\k!}. \end{equation\*}
Here's how you might do that for the second identity above.
Example \\\PageIndex{1}\\
Give an algebraic proof for the binomial identity
\begin{equation\*} {n \choose k} = {n-1\choose k-1} + {n-1 \choose k}. \end{equation\*}
Solution
*Proof*
By the definition of \\{n \choose k}\\, we have
\begin{equation\*} {n-1 \choose k-1} = \frac{(n-1)!}{(n-1-(k-1))!(k-1)!} = \frac{(n-1)!}{(n-k)!(k-1)!} \end{equation\*}
and
\begin{equation\*} {n-1 \choose k} = \frac{(n-1)!}{(n-1-k)!k!}. \end{equation\*}
Thus, starting with the right-hand side of the equation:
\begin{align\*} {n-1 \choose k-1} + {n-1 \choose k} \amp = \frac{(n-1)!}{(n-k)!(k-1)!}+ \frac{(n-1)!}{(n-1-k)!\\k!}\\ \amp = \frac{(n-1)!k}{(n-k)!\\k!} + \frac{(n-1)!(n-k)}{(n-k)!\\k!}\\ \amp = \frac{(n-1)!(k+n-k)}{(n-k)!\\k!}\\ \amp = \frac{n!}{(n-k)!\\ k!}\\ \amp = {n \choose k}. \end{align\*}
The second line (where the common denominator is found) works because \\k(k-1)! = k!\\ and \$n-k)(n-k-1)! = (n-k)!\\.
\\\square\\
This is certainly a valid proof, but also is entirely useless. Even if you understand the proof perfectly, it does not tell you *why* the identity is true. A better approach would be to explain what \\{n \choose k}\\ *means* and then say why that is also what \\{n-1 \choose k-1} + {n-1 \choose k}\\ means. Let's see how this works for the four identities we observed above.
Example \\\PageIndex{2}\\
Explain why \\{n \choose 0} = 1\\ and \\{n \choose n} = 1\\.
Solution
What do these binomial coefficients tell us? Well, \\{n \choose 0}\\ gives the number of ways to select 0 objects from a collection of \\n\\ objects. There is only one way to do this, namely to not select any of the objects. Thus \\{n \choose 0} = 1\\. Similarly, \\{n \choose n}\\ gives the number of ways to select \\n\\ objects from a collection of \\n\\ objects. There is only one way to do this: select all \\n\\ objects. Thus \\{n \choose n} = 1\\.
Alternatively, we know that \\{n \choose 0}\\ is the number of \\n\\-bit strings with weight 0. There is only one such string, the string of all 0's. So \\{n \choose 0} = 1\\. Similarly \\{n \choose n}\\ is the number of \\n\\-bit strings with weight \\n\\. There is only one string with this property, the string of all 1's.
Another way: \\{n \choose 0}\\ gives the number of subsets of a set of size \\n\\ containing 0 elements. There is only one such subset, the empty set. \\{n \choose n}\\ gives the number of subsets containing \\n\\ elements. The only such subset is the original set (of all elements).
Example \\\PageIndex{3}\\
Explain why \\{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\\.
Solution
The easiest way to see this is to consider bit strings. \\{n \choose k}\\ is the number of bit strings of length \\n\\ containing \\k\\ 1's. Of all of these strings, some start with a 1 and the rest start with a 0. First consider all the bit strings which start with a 1. After the 1, there must be \\n-1\\ more bits (to get the total length up to \\n\$ and exactly \\k-1\\ of them must be 1's (as we already have one, and we need \\k\\ total). How many strings are there like that? There are exactly \\{n-1 \choose k-1}\\ such bit strings, so of all the length \\n\\ bit strings containing \\k\\ 1's, \\{n-1 \choose k-1}\\ of them start with a 1. Similarly, there are \\{n-1\choose k}\\ which start with a 0 (we still need \\n-1\\ bits and now \\k\\ of them must be 1's). Since there are \\{n-1 \choose k}\\ bit strings containing \\n-1\\ bits with \\k\\ 1's, that is the number of length \\n\\ bit strings with \\k\\ 1's which start with a 0. Therefore \\{n \choose k} = {n-1\choose k-1} + {n-1 \choose k}\\.
Another way: consider the question, how many ways can you select \\k\\ pizza toppings from a menu containing \\n\\ choices? One way to do this is just \\{n \choose k}\\. Another way to answer the same question is to first decide whether or not you want anchovies. If you do want anchovies, you still need to pick \\k-1\\ toppings, now from just \\n-1\\ choices. That can be done in \\{n-1 \choose k-1}\\ ways. If you do not want anchovies, then you still need to select \\k\\ toppings from \\n-1\\ choices (the anchovies are out). You can do that in \\{n-1 \choose k}\\ ways. Since the choices with anchovies are disjoint from the choices without anchovies, the total choices are \\{n-1 \choose k-1}+{n-1 \choose k}\\. But wait. We answered the same question in two different ways, so the two answers must be the same. Thus \\{n \choose k} = {n-1\choose k-1} + {n-1 \choose k}\\.
You can also explain (prove) this identity by counting subsets, or even lattice paths.
Example \\\PageIndex{4}\\
Prove the binomial identity \\{n \choose k} = {n \choose n-k}. \nonumber\\
Solution
Why is this true? \\{n \choose k}\\ counts the number of ways to select \\k\\ things from \\n\\ choices. On the other hand, \\{n \choose n-k}\\ counts the number of ways to select \\n-k\\ things from \\n\\ choices. Are these really the same? Well, what if instead of selecting the \\n-k\\ things you choose to exclude them. How many ways are there to choose \\n-k\\ things to exclude from \\n\\ choices. Clearly this is \\{n \choose n-k}\\ as well (it doesn't matter whether you include or exclude the things once you have chosen them). And if you exclude \\n-k\\ things, then you are including the other \\k\\ things. So the set of outcomes should be the same.
Let's try the pizza counting example like we did above. How many ways are there to pick \\k\\ toppings from a list of \\n\\ choices? On the one hand, the answer is simply \\{n \choose k}\\. Alternatively, you could make a list of all the toppings you don't want. To end up with a pizza containing exactly \\k\\ toppings, you need to pick \\n-k\\ toppings to not put on the pizza. You have \\{n \choose n-k}\\ choices for the toppings you don't want. Both of these ways give you a pizza with \\k\\ toppings, in fact all the ways to get a pizza with \\k\\ toppings. Thus these two answers must be the same: \\{n \choose k} = {n \choose n-k}\\.
You can also prove (explain) this identity using bit strings, subsets, or lattice paths. The bit string argument is nice: \\{n \choose k}\\ counts the number of bit strings of length \\n\\ with \\k\\ 1's. This is also the number of bit string of length \\n\\ with \\k\\ 0's (just replace each 1 with a 0 and each 0 with a 1). But if a string of length \\n\\ has \\k\\ 0's, it must have \\n-k\\ 1's. And there are exactly \\{n\choose n-k}\\ strings of length \\n\\ with \\n-k\\ 1's.
Example \\\PageIndex{5}\\
Prove the binomial identity \\{n\choose 0} + {n \choose 1} + {n\choose 2} + \cdots + {n \choose n} = 2^n. \nonumber\\
Solution
*Proof*
Let's do a “pizza proof” again. We need to find a question about pizza toppings which has \\2^n\\ as the answer. How about this: If a pizza joint offers \\n\\ toppings, how many pizzas can you build using any number of toppings from no toppings to all toppings, using each topping at most once?
On one hand, the answer is \\2^n\\. For each topping you can say “yes” or “no,” so you have two choices for each topping.
On the other hand, divide the possible pizzas into disjoint groups: the pizzas with no toppings, the pizzas with one topping, the pizzas with two toppings, etc. If we want no toppings, there is only one pizza like that (the empty pizza, if you will) but it would be better to think of that number as \\{n \choose 0}\\ since we choose 0 of the \\n\\ toppings. How many pizzas have 1 topping? We need to choose 1 of the \\n\\ toppings, so \\{n \choose 1}\\. We have:
Pizzas with 0 toppings: \\{n \choose 0}\\ Pizzas with 1 topping: \\{n \choose 1}\\ Pizzas with 2 toppings: \\{n \choose 2}\\
The total number of possible pizzas will be the sum of these, which is exactly the left-hand side of the identity we are trying to prove.
Again, we could have proved the identity using subsets, bit strings, or lattice paths (although the lattice path argument is a little tricky).
- \\\vdots\\
- Pizzas with \\n\\ toppings: \\{n \choose n}\\.
\\\square\\
Hopefully this gives some idea of how explanatory proofs of binomial identities can go. It is worth pointing out that more traditional proofs can also be beautiful. 3 Most every binomial identity can be proved using mathematical induction, using the recursive definition for \\n \choose k\\. We will discuss induction in Section 2.5. For example, consider the following rather slick proof of the last identity.
Expand the binomial \$x+y)^n\text{:}\\
\begin{equation\*} (x + y)^n = {n \choose 0}x^n + {n \choose 1}x^{n-1}y + {n \choose 2}x^{n-2}y^2 + \cdots + {n \choose n-1}x\cdot y^n + {n \choose n}y^n. \end{equation\*}
Let \\x = 1\\ and \\y = 1\\. We get:
\begin{equation\*} (1 + 1)^n = {n \choose 0}1^n + {n \choose 1}1^{n-1}1 + {n \choose 2}1^{n-2}1^2 + \cdots + {n \choose n-1}1\cdot 1^n + {n \choose n}1^n. \end{equation\*}
Of course this simplifies to:
\begin{equation\*} (2)^n = {n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n-1} + {n \choose n}. \end{equation\*}
Something fun to try: Let \\x = 1\\ and \\y = 2\\. Neat huh?
More Proofs
The explanatory proofs given in the above examples are typically called combinatorial proofs . In general, to give a combinatorial proof for a binomial identity, say \\A = B\\ you do the following:
1. Find a counting problem you will be able to answer in two ways.
2. Explain why one answer to the counting problem is \\A\\.
3. Explain why the other answer to the counting problem is \\B\\.
Since both \\A\\ and \\B\\ are the answers to the same question, we must have \\A = B\\.
The tricky thing is coming up with the question. This is not always obvious, but it gets easier the more counting problems you solve. You will start to recognize types of answers as the answers to types of questions. More often what will happen is you will be solving a counting problem and happen to think up two different ways of finding the answer. Now you have a binomial identity and the proof is right there. The proof *is* the problem you just solved together with your two solutions.
For example, consider this counting question:
> How many 10-letter words use exactly four A's, three B's, two C's and one D?
Let's try to solve this problem. We have 10 spots for letters to go. Four of those need to be A's. We can pick the four A-spots in \\{10 \choose 4}\\ ways. Now where can we put the B's? Well there are only 6 spots left, we need to pick \\3\\ of them. This can be done in \\{6 \choose 3}\\ ways. The two C's need to go in two of the 3 remaining spots, so we have \\{3 \choose 2}\\ ways of doing that. That leaves just one spot of the D, but we could write that 1 choice as \\{1 \choose 1}\\. Thus the answer is:
\begin{equation\*} {10 \choose 4}{6 \choose 3}{3 \choose 2}{1 \choose 1}. \end{equation\*}
But why stop there? We can find the answer another way too. First let's decide where to put the one D: we have 10 spots, we need to choose 1 of them, so this can be done in \\{10 \choose 1}\\ ways. Next, choose one of the \\{9 \choose 2}\\ ways to place the two C's. We now have \\7\\ spots left, and three of them need to be filled with B's. There are \\{7 \choose 3}\\ ways to do this. Finally the A's can be placed in \\{4 \choose 4}\\ (that is, only one) ways. So another answer to the question is
\begin{equation\*} {10 \choose 1}{9 \choose 2}{7 \choose 3}{4 \choose 4}. \end{equation\*}
Interesting. This gives us the binomial identity:
\begin{equation\*} {10 \choose 4}{6 \choose 3}{3 \choose 2}{1 \choose 1} = {10 \choose 1}{9 \choose 2}{7 \choose 3}{4 \choose 4}. \end{equation\*}
Here are a couple of other binomial identities with combinatorial proofs.
Example \\\PageIndex{6}\\
Prove the identity
\begin{equation\*} 1 n + 2(n-1) + 3 (n-2) + \cdots + (n-1) 2 + n 1 = {n+2 \choose 3}. \end{equation\*}
Solution
To give a combinatorial proof we need to think up a question we can answer in two ways: one way needs to give the left-hand-side of the identity, the other way needs to be the right-hand-side of the identity. Our clue to what question to ask comes from the right-hand side: \\{n+2 \choose 3}\\ counts the number of ways to select 3 things from a group of \\n+2\\ things. Let's name those things \\1, 2, 3, \ldots, n+2\\. In other words, we want to find 3-element subsets of those numbers (since order should not matter, subsets are exactly the right thing to think about). We will have to be a bit clever to explain why the left-hand-side also gives the number of these subsets. Here's the proof.
*Proof*
Consider the question “How many 3-element subsets are there of the set \\\\1,2,3,\ldots, n+2\\\text{?}\\” We answer this in two ways:
Answer 1: We must select 3 elements from the collection of \\n+2\\ elements. This can be done in \\{n+2 \choose 3}\\ ways.
Answer 2: Break this problem up into cases by what the middle number in the subset is. Say each subset is \\\\a,b,c\\\\ written in increasing order. We count the number of subsets for each distinct value of \\b\\. The smallest possible value of \\b\\ is \\2\\, and the largest is \\n+1\\.
When \\b = 2\\, there are \\1 \cdot n\\ subsets: 1 choice for \\a\\ and \\n\\ choices (3 through \\n+2\$ for \\c\\.
When \\b = 3\\, there are \\2 \cdot (n-1)\\ subsets: 2 choices for \\a\\ and \\n-1\\ choices for \\c\\.
When \\b = 4\\, there are \\3 \cdot (n-2)\\ subsets: 3 choices for \\a\\ and \\n-2\\ choices for \\c\\.
And so on. When \\b = n+1\\, there are \\n\\ choices for \\a\\ and only 1 choice for \\c\\, so \\n \cdot 1\\ subsets.
Therefore the total number of subsets is
\begin{equation\*} 1 n + 2 (n-1) + 3 (n-2) + \cdots + (n-1)2 + n 1. \end{equation\*}
Since Answer 1 and Answer 2 are answers to the same question, they must be equal. Therefore
\begin{equation\*} 1 n + 2 (n-1) + 3 (n-2) + \cdots + (n-1) 2 + n 1 = {n+2 \choose 3}. \end{equation\*}
\\\square\\
Example \\\PageIndex{7}\\
Prove the binomial identity
\begin{equation\*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2 = {2n \choose n}. \end{equation\*}
Solution 1
*We will give two different proofs of this fact. The first will be very similar to the previous example (counting subsets). The second proof is a little slicker, using lattice paths.*
*Proof*
Consider the question: “How many pizzas can you make using \\n\\ toppings when there are \\2n\\ toppings to choose from?”
Answer 1: There are \\2n\\ toppings, from which you must choose \\n\\. This can be done in \\{2n \choose n}\\ ways.
Answer 2: Divide the toppings into two groups of \\n\\ toppings (perhaps \\n\\ meats and \\n\\ veggies). Any choice of \\n\\ toppings must include some number from the first group and some number from the second group. Consider each possible number of meat toppings separately:
0 meats: \\{n \choose 0}{n \choose n}\\, since you need to choose 0 of the \\n\\ meats and \\n\\ of the \\n\\ veggies.
1 meat: \\{n \choose 1}{n \choose n-1}\\, since you need 1 of \\n\\ meats so \\n-1\\ of \\n\\ veggies.
2 meats: \\{n \choose 2}{n \choose n-2}\\. Choose 2 meats and the remaining \\n-2\\ toppings from the \\n\\ veggies.
And so on. The last case is \\n\\ meats, which can be done in \\{n \choose n}{n \choose 0}\\ ways.
Thus the total number of pizzas possible is
\begin{equation\*} {n \choose 0}{n \choose n} + {n \choose 1}{n \choose n-1} + {n \choose 2}{n \choose n-2} + \cdots + {n \choose n}{n \choose 0}. \end{equation\*}
This is not quite the left-hand side … yet. Notice that \\{n \choose n} = {n \choose 0}\\ and \\{n \choose n-1} = {n \choose 1}\\ and so on, by the identity in Example 1.4.4. Thus we do indeed get
\begin{equation\*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2. \end{equation\*}
Since these two answers are answers to the same question, they must be equal, and thus
\begin{equation\*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2 = {2n \choose n}. \end{equation\*}
\\\square\\
For an alternative proof, we use lattice paths. This is reasonable to consider because the right-hand side of the identity reminds us of the number of paths from \$0,0)\\ to \$n,n)\\.
Proof
Consider the question: How many lattice paths are there from \$0,0)\\ to \$n,n)\text{?}\\
Answer 1: We must travel \\2n\\ steps, and \\n\\ of them must be in the up direction. Thus there are \\{2n \choose n}\\ paths.
Answer 2: Note that any path from \$0,0)\\ to \$n,n)\\ must cross the line \\x + y = n\\. That is, any path must pass through exactly one of the points: \$0,n)\\, \$1,n-1)\\, \$2,n-2)\\, …, \$n, 0)\\. For example, this is what happens in the case \\n = 4\text{:}\\
\![lattice-paths-comb-proof.svg$$(https://math.libretexts.org/@api/deki/files/12810/lattice-paths-comb-proof.svg?revision=1&size=bestfit&width=354&height=242)
\![$$(https://math.libretexts.org/images/lattice-paths-comb-proof.svg)
How many paths pass through \$0,n)\text{?}\\ To get to that point, you must travel \\n\\ units, and \\0\\ of them are to the right, so there are \\{n \choose 0}\\ ways to get to \$0,n)\\. From \$0,n)\\ to \$n,n)\\ takes \\n\\ steps, and \\0\\ of them are up. So there are \\{n \choose 0}\\ ways to get from \$0,n)\\ to \$n,n)\\. Therefore there are \\{n \choose 0}{n \choose 0}\\ paths from \$0,0)\\ to \$n,n)\\ through the point \$0,n)\\.
What about through \$1,n-1)\\. There are \\{n \choose 1}\\ paths to get there (\\n\\ steps, 1 to the right) and \\{n \choose 1}\\ paths to complete the journey to \$n,n)\\ (\\n\\ steps, \\1\\ up). So there are \\{n \choose 1}{n \choose 1}\\ paths from \$0,0)\\ to \$n,n)\\ through \$1,n-1)\\.
In general, to get to \$n,n)\\ through the point \$k,n-k)\\ we have \\{n \choose k}\\ paths to the midpoint and then \\{n \choose k}\\ paths from the midpoint to \$n,n)\\. So there are \\{n \choose k}{n \choose k}\\ paths from \$0,0)\\ to \$n,n)\\ through \$k, n-k)\\.
All together then the total paths from \$0,0)\\ to \$n,n)\\ passing through exactly one of these midpoints is
\begin{equation\*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2. \end{equation\*}
Since these two answers are answers to the same question, they must be equal, and thus
\begin{equation\*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2 = {2n \choose n}. \end{equation\*}
\\\square\\
---
1_5_3A_Stars_and_Bars
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/1%3A_Counting/1.5%3A_Stars_and_Bars
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
Investigate!
Suppose you have some number of identical Rubik's cubes to distribute to your friends. Imagine you start with a single row of the cubes.
1. Find the number of different ways you can distribute the cubes provided:
1. You have 3 cubes to give to 2 people.
2. You have 4 cubes to give to 2 people.
3. You have 5 cubes to give to 2 people.
4. You have 3 cubes to give to 3 people.
5. You have 4 cubes to give to 3 people.
6. You have 5 cubes to give to 3 people.
2. Make a conjecture about how many different ways you could distribute 7 cubes to 4 people. Explain.
3. What if each person were required to get *at least one* cube? How would your answers change?
Consider the following counting problem:
*You have 7 cookies to give to 4 kids. How many ways can you do this?*
Take a moment to think about how you might solve this problem. You may assume that it is acceptable to give a kid no cookies. Also, the cookies are all identical and the order in which you give out the cookies does not matter.
Before solving the problem, here is a wrong answer: You might guess that the answer should be \\4^7\\ because for each of the 7 cookies, there are 4 choices of kids to which you can give the cookie. This is reasonable, but wrong. To see why, consider a few possible outcomes: we could assign the first six cookies to kid A, and the seventh cookie to kid B. Another outcome would assign the first cookie to kid B and the six remaining cookies to kid A. Both outcomes are included in the \\4^7\\ answer. But for our counting problem, both outcomes are really the same – kid A gets six cookies and kid B gets one cookie.
What do outcomes actually look like? How can we represent them? One approach would be to write an outcome as a string of four numbers like this:
\begin{equation\*} 3112, \end{equation\*}
which represent the outcome in which the first kid gets 3 cookies, the second and third kid each get 1 cookie, and the fourth kid gets 2 cookies. Represented this way, the order in which the numbers occur matters. 1312 is a different outcome, because the first kid gets a one cookie instead of 3. Each number in the string can be any integer between 0 and 7. But the answer is not \\7^4\text{.}\\ We need the *sum* of the numbers to be 7.
Another way we might represent outcomes is to write a string of seven letters:
\begin{equation\*} \mbox{ABAADCD} , \end{equation\*}
which represents that the first cookie goes to kid A, the second cookie goes to kid B, the third and fourth cookies go to kid A, and so on. In fact, this outcome is identical to the previous one—A gets 3 cookies, B and C get 1 each and D gets 2. Each of the seven letters in the string can be any of the 4 possible letters (one for each kid), but the number of such strings is not \\4^7\text{,}\\ because here order does *not* matter. In fact, another way to write the same outcome is
\begin{equation\*} \mbox{AAABCDD} . \end{equation\*}
This will be the preferred representation of the outcome. Since we can write the letters in any order, we might as well write them in *alphabetical* order for the purposes of counting. So we will write all the A's first, then all the B's, and so on.
Now think about how you could specify such an outcome. All we really need to do is say when to switch from one letter to the next. In terms of cookies, we need to say after how many cookies do we stop giving cookies to the first kid and start giving cookies to the second kid. And then after how many do we switch to the third kid? And after how many do we switch to the fourth? So yet another way to represent an outcome is like this:
\begin{equation\*} \*\*\*\|\*\|\*\|\*\* \end{equation\*}
Three cookies go to the first kid, then we switch and give one cookie to the second kid, then switch, one to the third kid, switch, two to the fourth kid. Notice that we need 7 stars and 3 bars – one star for each cookie, and one bar for each switch between kids, so one fewer bars than there are kids (we don't need to switch after the last kid – we are done).
Why have we done all of this? Simple: to count the number of ways to distribute 7 cookies to 4 kids, all we need to do is count how many *stars and bars* charts there are. But a stars and bars chart is just a string of symbols, some stars and some bars. If instead of stars and bars we would use 0's and 1's, it would just be a bit string. We know how to count those.
Before we get too excited, we should make sure that really *any* string of (in our case) 7 stars and 3 bars corresponds to a different way to distribute cookies to kids. In particular consider a string like this:
\begin{equation\*} \|\*\*\*\|\|\*\*\*\* \end{equation\*}
Does that correspond to a cookie distribution? Yes. It represents the distribution in which kid A gets 0 cookies (because we switch to kid B before any stars), kid B gets three cookies (three stars before the next bar), kid C gets 0 cookies (no stars before the next bar) and kid D gets the remaining 4 cookies. No matter how the stars and bars are arranged, we can distribute cookies in that way. Also, given any way to distribute cookies, we can represent that with a stars and bars chart. For example, the distribution in which kid A gets 6 cookies and kid B gets 1 cookie has the following chart:
\begin{equation\*} \*\*\*\*\*\*\|\*\|\| \end{equation\*}
After all that work we are finally ready to count. Each way to distribute cookies corresponds to a stars and bars chart with 7 stars and 3 bars. So there are 10 symbols, and we must choose 3 of them to be bars. Thus:
\begin{equation\*} \mbox{ There are } {10 \choose 3}\mbox{ ways to distribute 7 cookies to 4 kids.} \end{equation\*}
While we are at it, we can also answer a related question: how many ways are there to distribute 7 cookies to 4 kids so that each kid gets at least one cookie? What can you say about the corresponding stars and bars charts? The charts must start and end with at least one star (so that kids A and D) get cookies, and also no two bars can be adjacent (so that kids B and C are not skipped). One way to assure this is to only place bars in the spaces *between* the stars. With 7 stars, there are 6 spots between the stars, so we must choose 3 of those 6 spots to fill with bars. Thus there are \\{6 \choose 3}\\ ways to distribute 7 cookies to 4 kids giving at least one cookie to each kid.
Another (and more general) way to approach this modified problem is to first give each kid one cookie. Now the remaining 3 cookies can be distributed to the 4 kids without restrictions. So we have 3 stars and 3 bars for a total of 6 symbols, 3 of which must be bars. So again we see that there are \\{6 \choose 3}\\ ways to distribute the cookies.
Stars and bars can be used in counting problems other than kids and cookies. Here are a few examples:
Example \\\PageIndex{1}\\
Your favorite mathematical pizza chain offers 10 toppings. How many pizzas can you make if you are allowed 6 toppings? The order of toppings does not matter but now you are allowed repeats. So one possible pizza is triple sausage, double pineapple, and onions.
Solution
We get 6 toppings (counting possible repeats). Represent each of these toppings as a star. Think of going down the menu one topping at a time: you see anchovies first, and skip to the next, sausage. You say yes to sausage 3 times (use 3 stars), then switch to the next topping on the list. You keep skipping until you get to pineapple, which you say yes to twice. Another switch and you are at onions. You say yes once. Then you keep switching until you get to the last topping, never saying yes again (since you already have said yes 6 times. There are 10 toppings to choose from, so we must switch from considering one topping to the next 9 times. These are the bars.
Now that we are confident that we have the right number of stars and bars, we answer the question simply: there are 6 stars and 9 bars, so 15 symbols. We need to pick 9 of them to be bars, so there number of pizzas possible is
\begin{equation\*} {15 \choose 9}. \end{equation\*}
Example \\\PageIndex{2}\\
How many 7 digit phone numbers are there in which the digits are non-increasing? That is, every digit is less than or equal to the previous one.
Solution
We need to decide on 7 digits so we will use 7 stars. The bars will represent a switch from each possible single digit number down the next smaller one. So the phone number 866-5221 is represented by the stars and bars chart
\begin{equation\*} \|\*\|\|\*\*\|\*\|\|\|\*\*\|\*\| \end{equation\*}
There are 10 choices for each digit (0-9) so we must switch between choices 9 times. We have 7 stars and 9 bars, so the total number of phone numbers is
\begin{equation\*} {16 \choose 9}. \end{equation\*}
Example \\\PageIndex{3}\\
How many integer solutions are there to the equation
\begin{equation\*} x_1 + x_2 + x_3 + x_4 + x_5 = 13. \end{equation\*}
(An integer solution to an equation is a solution in which the unknown must have an integer value.)
1. where \\x_i \ge 0\\ for each \\x_i\text{?}\\
2. where \\x_i \> 0\\ for each \\x_i\text{?}\\
3. where \\x_i \ge 2\\ for each \\x_i\text{?}\\
Solution
This problem is just like giving 13 cookies to 5 kids. We need to say how many of the 13 units go to each of the 5 variables. In other words, we have 13 stars and 4 bars (the bars are like the “+” signs in the equation).
1. If \\x_i\\ can be 0 or greater, we are in the standard case with no restrictions. So 13 stars and 4 bars can be arranged in \\{17 \choose 4}\\ ways.
2. Now each variable must be at least 1. So give one unit to each variable to satisfy that restriction. Now there are 8 stars left, and still 4 bars, so the number of solutions is \\{12 \choose 4}\text{.}\\
3. Now each variable must be 2 or greater. So before any counting, give each variable 2 units. We now have 3 remaining stars and 4 bars, so there are \\{7 \choose 4}\\ solutions.
Counting with Functions
Many of the counting problems in this section might at first appear to be examples of counting *functions*. After all, when we try to count the number of ways to distribute cookies to kids, we are assigning each cookie to a kid, just like you assign elements of the domain of a function to elements in the codomain. However, the number of ways to assign 7 cookies to 4 kids is \\{10 \choose 7} = 120\text{,}\\ while the number of functions \\f: \\1,2,3,4,5,6,7\\ \to \\a,b,c,d\\\\ is \\4^7 = 16384\text{.}\\ What is going on here?
When we count functions, we consider the following two functions, for example, to be different:
\\f = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{a \amp b \amp c \amp c \amp c \amp c \amp c} \qquad g = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{b \amp a \amp c \amp c \amp c \amp c \amp c}.\\
But these two functions would correspond to the *same* cookie distribution: kids \\a\\ and \\b\\ each get one cookie, kid \\c\\ gets the rest (and none for kid \\d\$.
The point: elements of the domain are distinguished, cookies are indistinguishable. This is analogous to the distinction between permutations (like counting functions) and combinations (not).
Contributors and Attributions
- Oscar Levin (School of Mathematical Science, University of Northern Colorado)
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
---
1_6_3A_Advanced_Counting_Using_PIE
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/1%3A_Counting/1.6%3A_Advanced_Counting_Using_PIE
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
Investigate!
You have 11 identical mini key-lime pies to give to 4 children. However, you don't want any kid to get more than 3 pies. How many ways can you distribute the pies?
1. How many ways are there to distribute the pies without any restriction?
2. Let's get rid of the ways that one or more kid gets too many pies. How many ways are there to distribute the pies if Al gets too many pies? What if Bruce gets too many? Or Cat? Or Dent?
3. What if two kids get too many pies? How many ways can this happen? Does it matter which two kids you pick to overfeed?
4. Is it possible that three kids get too many pies? If so, how many ways can this happen?
5. How should you combine all the numbers you found above to answer the original question?
Suppose now you have 13 pies and 7 children. No child can have more than 2 pies. How many ways can you distribute the pies?
Stars and bars allows us to count the number of ways to distribute 10 cookies to 3 kids and natural number solutions to \\x+y+z = 11\text{,}\\ for example. A relatively easy modification allows us to put a *lower bound* restriction on these problems: perhaps each kid must get at least two cookies or \\x,y,z \ge 2\text{.}\\ This was done by first assigning each kid (or variable) 2 cookies (or units) and then distributing the rest using stars and bars.
What if we wanted an *upper bound* restriction? For example, we might insist that no kid gets more than 4 cookies or that \\x, y, z \le 4\text{.}\\ It turns out this is considerably harder, but still possible. The idea is to count all the distributions and then remove those that violate the condition. In other words, we must count the number of ways to distribute 11 cookies to 3 kids in which *one or more* of the kids gets more than 4 cookies. For any particular kid, this is not a problem; we do this using stars and bars. But how to combine the number of ways for kid A, or B or C? We must use the PIE.
The Principle of Inclusion/Exclusion (PIE) gives a method for finding the cardinality of the union of not necessarily disjoint sets. We saw in Subsection how this works with three sets. To find how many things are in *one or more* of the sets \\A\text{,}\\ \\B\text{,}\\ and \\C\text{,}\\ we should just add up the number of things in each of these sets. However, if there is any overlap among the sets, those elements are counted multiple times. So we subtract the things in each intersection of a pair of sets. But doing this removes elements which are in all three sets once too often, so we need to add it back in. In terms of cardinality of sets, we have
\begin{equation\*} \|A \cup B \cup C\| = \|A\| + \|B\| + \|C\| - \|A \cap B\| - \|A \cap C\| - \|B \cap C\| + \|A\cap B \cap C\|. \end{equation\*}
Example \\\PageIndex{1}\\:
Three kids, Alberto, Bernadette, and Carlos, decide to share 11 cookies. They wonder how many ways they could split the cookies up provided that none of them receive more than 4 cookies (someone receiving no cookies is for some reason acceptable to these kids).
Solution
Without the “no more than 4” restriction, the answer would be \\{13 \choose 2}\text{,}\\ using 11 stars and 2 bars (separating the three kids). Now count the number of ways that one or more of the kids violates the condition, i.e., gets at least 4 cookies.
Let \\A\\ be the set of outcomes in which Alberto gets more than 4 cookies. Let \\B\\ be the set of outcomes in which Bernadette gets more than 4 cookies. Let \\C\\ be the set of outcomes in which Carlos gets more than 4 cookies. We then are looking (for the sake of subtraction) for the size of the set \\A \cup B \cup C\text{.}\\ Using PIE, we must find the sizes of \\\|A\|\text{,}\\ \\\|B\|\text{,}\\ \\\|C\|\text{,}\\ \\\|A\cap B\|\\ and so on. Here is what we find.
\\\|A\| = {8 \choose 2}\text{.}\\ First give Alberto 5 cookies, then distribute the remaining 6 to the three kids without restrictions, using 6 stars and 2 bars.
\\\|B\| = {8 \choose 2}\text{.}\\ Just like above, only now Bernadette gets 5 cookies at the start.
\\\|C\| = {8 \choose 2}\text{.}\\ Carlos gets 5 cookies first.
\\\|A \cap B\| = {3 \choose 2}\text{.}\\ Give Alberto and Bernadette 5 cookies each, leaving 1 (star) to distribute to the three kids (2 bars).
\\\|A \cap C\| = {3 \choose 2}\text{.}\\ Alberto and Carlos get 5 cookies first.
\\\|B \cap C\| = {3 \choose 2}\text{.}\\ Bernadette and Carlos get 5 cookies first.
\\\|A \cap B \cap C\| = 0\text{.}\\ It is not possible for all three kids to get 4 or more cookies.
Combining all of these we see
\begin{equation\*} \|A \cup B \cup C\| = {8 \choose 2} + {8 \choose 2} + {8 \choose 2} - {3 \choose 2} - {3 \choose 2} - {3 \choose 2} + 0 = 75. \end{equation\*}
Thus the answer to the original question is \\{13 \choose 2} - 75 = 78 - 75 = 3\text{.}\\ This makes sense now that we see it. The only way to ensure that no kid gets more than 4 cookies is to give two kids 4 cookies and one kid 3; there are three choices for which kid that should be. We could have found the answer much quicker through this observation, but the point of the example is to illustrate that PIE works!
For four or more sets, we do not write down a formula for PIE. Instead, we just think of the principle: add up all the elements in single sets, then subtract out things you counted twice (elements in the intersection of a *pair* of sets), then add back in elements you removed too often (elements in the intersection of groups of three sets), then take back out elements you added back in too often (elements in the intersection of groups of four sets), then add back in, take back out, add back in, etc. This would be very difficult if it wasn't for the fact that in these problems, all the cardinalities of the single sets are equal, as are all the cardinalities of the intersections of two sets, and that of three sets, and so on. Thus we can group all of these together and multiply by how many different combinations of 1, 2, 3, … sets there are.
Example \\\PageIndex{2}\\
How many ways can you distribute 10 cookies to 4 kids so that no kid gets more than 2 cookies?
Solution
There are \\{13 \choose 3}\\ ways to distribute 10 cookies to 4 kids (using 10 stars and 3 bars). We will subtract all the outcomes in which a kid gets 3 or more cookies. How many outcomes are there like that? We can force kid A to eat 3 or more cookies by giving him 3 cookies before we start. Doing so reduces the problem to one in which we have 7 cookies to give to 4 kids without any restrictions. In that case, we have 7 stars (the 7 remaining cookies) and 3 bars (one less than the number of kids) so we can distribute the cookies in \\{10 \choose 3}\\ ways. Of course we could choose any one of the 4 kids to give too many cookies, so it would appear that there are \\{4 \choose 1}{10 \choose 3}\\ ways to distribute the cookies giving too many to one kid. But in fact, we have over counted.
We must get rid of the outcomes in which two kids have too many cookies. There are \\{4 \choose 2}\\ ways to select 2 kids to give extra cookies. It takes 6 cookies to do this, leaving only 4 cookies. So we have 4 stars and still 3 bars. The remaining 4 cookies can thus be distributed in \\{7 \choose 3}\\ ways (for each of the \\{4 \choose 2}\\ choices of which 2 kids to over-feed).
But now we have removed too much. We must add back in all the ways to give too many cookies to three kids. This uses 9 cookies, leaving only 1 to distribute to the 4 kids using stars and bars, which can be done in \\{4 \choose 3}\\ ways. We must consider this outcome for every possible choice of which three kids we over-feed, and there are \\{4 \choose 3}\\ ways of selecting that set of 3 kids.
Next we would subtract all the ways to give four kids too many cookies, but in this case, that number is 0.
All together we get that the number of ways to distribute 10 cookies to 4 kids without giving any kid more than 2 cookies is:
\begin{equation\*} {13 \choose 3} - \left$${4 \choose 1}{10 \choose 3} - {4 \choose 2}{7 \choose 3} + {4\choose 3}{4\choose 3}\right$$ \end{equation\*}
which is
\begin{equation\*} 286 - $$480 - 210 + 16$$ = 0. \end{equation\*}
This makes sense: there is NO way to distribute 10 cookies to 4 kids and make sure that nobody gets more than 2. It is slightly surprising that
\begin{equation\*} {13 \choose 3} = \left$${4 \choose 1}{10 \choose 3} - {4 \choose 2}{7 \choose 3} + {4\choose 3}{4\choose 3}\right$$ \end{equation\*}
but since PIE works, this equality must hold.
Just so you don't think that these problems always have easier solutions, consider the following example.
Example \\\PageIndex{3}\\
Earlier (Example 1.5.3) we counted the number of solutions to the equation
\begin{equation\*} x_1 + x_2 + x_3 + x_4 + x_5 = 13 \end{equation\*}
where \\x_i \ge 0\\ for each \\x_i\text{.}\\
How many of those solutions have \\0 \le x_i \le 3\\ for each \\x_i\text{?}\\
Solution
We must subtract off the number of solutions in which one or more of the variables has a value greater than 3. We will need to use PIE because counting the number of solutions for which each of the five variables separately are greater than 3 counts solutions multiple times. Here is what we get:
- Total solutions: \\{17 \choose 4}\text{.}\\
- Solutions where \\x_1 \> 3\text{:}\\ \\{13 \choose 4}\text{.}\\ Give \\x_1\\ 4 units first, then distribute the remaining 9 units to the 5 variables.
- Solutions where \\x_1 \> 3\\ and \\x_2 \> 3\text{:}\\ \\{9 \choose 4}\text{.}\\ After you give 4 units to \\x_1\\ and another 4 to \\x_2\text{,}\\ you only have 5 units left to distribute.
- Solutions where \\x_1 \> 3\text{,}\\ \\x_2 \> 3\\ and \\x_3 \> 3\text{:}\\ \\{5 \choose 4}\text{.}\\
- Solutions where \\x_1 \> 3\text{,}\\ \\x_2 \> 3\text{,}\\ \\x_3 \> 3\text{,}\\ and \\x_4 \> 3\text{:}\\ 0.
We also need to account for the fact that we could choose any of the five variables in the place of \\x_1\\ above (so there will be \\{5 \choose 1}\\ outcomes like this), any pair of variables in the place of \\x_1\\ and \\x_2\\ (\\{5 \choose 2}\\ outcomes) and so on. It is because of this that the double counting occurs, so we need to use PIE. All together we have that the number of solutions with \\0 \le x_i \le 3\\ is
\begin{equation\*} {17 \choose 4} - \left$${5\choose 1}{13 \choose 4} - {5 \choose 2}{9 \choose 4} + {5 \choose 3}{5 \choose 4}\right$$ = 15. \end{equation\*}
Counting Derangements
Investigate!
For your senior prank, you decide to switch the nameplates on your favorite 5 professors' doors. So that none of them feel left out, you want to make sure that all of the nameplates end up on the wrong door. How many ways can this be accomplished?
The advanced use of PIE has applications beyond stars and bars. A derangement of \\n\\ elements \\\\1,2,3,\ldots, n\\\\ is a permutation in which no element is fixed. For example, there are \\6\\ permutations of the three elements \\\\1,2,3\\\text{:}\\
\begin{equation\*} 123 \~~ 132 \~~ 213 \~~ 231 \~~ 312 \~~ 321. \end{equation\*}
but most of these have one or more elements fixed: \\123\\ has all three elements fixed since all three elements are in their original positions, \\132\\ has the first element fixed (1 is in its original first position), and so on. In fact, the only derangements of three elements are
\begin{equation\*} 231 \text{ and } 312. \end{equation\*}
If we go up to 4 elements, there are 24 permutations (because we have 4 choices for the first element, 3 choices for the second, 2 choices for the third leaving only 1 choice for the last). How many of these are derangements? If you list out all 24 permutations and eliminate those which are not derangements, you will be left with just 9 derangements. Let's see how we can get that number using PIE.
Example \\\PageIndex{4}\\
How many derangements are there of 4 elements?
Solution
We count all permutations, and subtract those which are not derangements. There are \\4! = 24\\ permutations of 4 elements. Now for a permutation to not be a derangement, at least one of the 4 elements must be fixed. There are \\{4 \choose 1}\\ choices for which single element we fix. Once fixed, we need to find a permutation of the other three elements. There are \\3!\\ permutations on 3 elements. But now we have counted too many non-derangements, so we must subtract those permutations which fix two elements. There are \\{4 \choose 2}\\ choices for which two elements we fix, and then for each pair, \\2!\\ permutations of the remaining elements. But this subtracts too many, so add back in permutations which fix 3 elements, all \\{4 \choose 3}1!\\ of them. Finally subtract the \\{4 \choose 4}0!\\ permutations (recall \\0! = 1\$ which fix all four elements. All together we get that the number of derangements of 4 elements is:
\begin{equation\*} 4! - \left$${4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4}0!\right$$ = 24 - 15 = 9. \end{equation\*}
Of course we can use a similar formula to count the derangements of any number of elements. However, the more elements we have, the longer the formula gets. Here is another example:
Example \\\PageIndex{5}\\
Five gentlemen attend a party, leaving their hats at the door. At the end of the party, they hastily grab hats on their way out. How many different ways could this happen so that none of the gentlemen leave with their own hat?
Solution
We are counting derangements on 5 elements. There are \\5!\\ ways for the gentlemen to grab hats in any order—but many of these permutations will result in someone getting their own hat. So we subtract all the ways in which one or more of the men get their own hat. In other words, we subtract the non-derangements. Doing so requires PIE. Thus the answer is:
\begin{equation\*} 5! - \left$${5 \choose 1}4! - {5 \choose 2}3! + {5 \choose 3}2! - {5 \choose 4}1! + {5 \choose 5}0!\right$$. \end{equation\*}
Counting Functions
Investigate!
- Consider all functions \\f: \\1,2,3,4,5\\ \to \\1,2,3,4,5\\\text{.}\\ How many functions are there all together? How many of those are injective? Remember, a function is an injection if every input goes to a different output.
- Consider all functions \\f: \\1,2,3,4,5\\ \to \\1,2,3,4,5\\\text{.}\\ How many of the *injections* have the property that \\f(x) \ne x\\ for any \\x \in \\1,2,3,4,5\\\\? Your friend claims that the answer is: \begin{equation\*} 5! - \left$$ {5\choose 1}4! - {5 \choose 2}3! + {5\choose 3}2! - {5 \choose 4}1! + {5\choose 5}0! \right$$. \end{equation\*} Explain why this is correct.
- Recall that a *surjection* is a function for which every element of the codomain is in the range. How many of the functions \\f: \\1,2,3,4,5\\ \to \\1,2,3,4,5\\\\ are surjective? Use PIE!
We have seen throughout this chapter that many counting questions can be rephrased as questions about counting functions with certain properties. This is reasonable since many counting questions can be thought of as counting the number of ways to assign elements from one set to elements of another.
Example \\\PageIndex{6}\\
You decide to give away your video game collection so to better spend your time studying advance mathematics. How many ways can you do this, provided:
1. You want to distribute your 3 different PS4 games among 5 friends, so that no friend gets more than one game?
2. You want to distribute your 8 different 3DS games among 5 friends?
3. You want to distribute your 8 different SNES games among 5 friends, so that each friend gets at least one game?
In each case, model the counting question as a function counting question.
Solution
We must use the three games (call them 1, 2, 3) as the domain and the 5 friends (a,b,c,d,e) as the codomain (otherwise the function would not be defined for the whole domain when a friend didn't get any game). So how many functions are there with domain \\\\1,2,3\\\\ and codomain \\\\a,b,c,d,e\\\text{?}\\ The answer to this is \\5^3=125\text{,}\\ since we can assign any of 5 elements to be the image of 1, any of 5 elements to be the image of 2 and any of 5 elements to be the image of 3.
But this is not the correct answer to our counting problem, because one of these functions is \\f= \twoline{1\amp 2\amp 3}{a\amp a\amp a}\text{;}\\ one friend can get more than one game. What we really need to do is count *injective* functions. This gives \\P(5,3) = 60\\ functions, which is the answer to our counting question.
Again, we need to use the 8 games as the domain and the 5 friends as the codomain. We are counting all functions, so the number of ways to distribute the games is \\5^8\text{.}\\
This question is harder. Use the games as the domain and friends as the codomain (otherwise an element of the domain would have more than one image, which is impossible). To ensure that every friend gets at least one game means that every element of the codomain is in the range. In other words, we are looking for *surjective* functions. How do you count those?
In Example 1.1.5 we saw how to count all functions (using the multiplicative principle) and in Example 1.3.4 we learned how to count injective functions (using permutations). Surjective functions are not as easily counted (unless the size of the domain is smaller than the codomain, in which case there are none).
The idea is to count the functions which are *not* surjective, and then subtract that from the total number of functions. This works very well when the codomain has two elements in it:
Example \\\PageIndex{7}\\
How many functions \\f: \\1,2,3,4,5\\ \to \\a,b\\\\ are surjective?
Solution
There are \\2^5\\ functions all together, two choices for where to send each of the 5 elements of the domain. Now of these, the functions which are *not* surjective must exclude one or more elements of the codomain from the range. So first, consider functions for which \\a\\ is not in the range. This can only happen one way: everything gets sent to \\b\text{.}\\ Alternatively, we could exclude \\b\\ from the range. Then everything gets sent to \\a\text{,}\\ so there is only one function like this. These are the only ways in which a function could not be surjective (no function excludes both \\a\\ and \\b\\ from the range) so there are exactly \\2^5 - 2\\ surjective functions.
When there are three elements in the codomain, there are now three choices for a single element to exclude from the range. Additionally, we could pick pairs of two elements to exclude from the range, and we must make sure we don't over count these. It's PIE time!
Example \\\PageIndex{8}\\
How many functions \\f: \\1,2,3,4,5\\ \to \\a,b,c\\\\ are surjective?
Solution
Again start with the total number of functions: \\3^5\\ (as each of the five elements of the domain can go to any of three elements of the codomain). Now we count the functions which are *not* surjective.
Start by excluding \\a\\ from the range. Then we have two choices (\\b\\ or \\c\$ for where to send each of the five elements of the domain. Thus there are \\2^5\\ functions which exclude \\a\\ from the range. Similarly, there are \\2^5\\ functions which exclude \\b\text{,}\\ and another \\2^5\\ which exclude \\c\text{.}\\ Now have we counted all functions which are not surjective? Yes, but in fact, we have counted some multiple times. For example, the function which sends everything to \\c\\ was one of the \\2^5\\ functions we counted when we excluded \\a\\ from the range, and also one of the \\2^5\\ functions we counted when we excluded \\b\\ from the range. We must subtract out all the functions which specifically exclude two elements from the range. There is 1 function when we exclude \\a\\ and \\b\\ (everything goes to \\c\$, one function when we exclude \\a\\ and \\c\text{,}\\ and one function when we exclude \\b\\ and \\c\text{.}\\
We are using PIE: to count the functions which are not surjective, we added up the functions which exclude \\a\text{,}\\ \\b\text{,}\\ and \\c\\ separately, then subtracted the functions which exclude pairs of elements. We would then add back in the functions which exclude groups of three elements, except that there are no such functions. We find that the number of functions which are *not* surjective is
\begin{equation\*} 2^5 + 2^5 + 2^5 - 1 - 1 - 1 + 0. \end{equation\*}
Perhaps a more descriptive way to write this is
\begin{equation\*} {3 \choose 1}2^5 - {3 \choose 2}1^5 + {3 \choose 3}0^5. \end{equation\*}
since each of the \\2^5\\'s was the result of choosing 1 of the 3 elements of the codomain to exclude from the range, each of the three \\1^5\\'s was the result of choosing 2 of the 3 elements of the codomain to exclude. Writing \\1^5\\ instead of 1 makes sense too: we have 1 choice of were to send each of the 5 elements of the domain.
Now we can finally count the number of surjective functions:
\begin{equation\*} 3^5 - \left$${3 \choose 1}2^5 - {3 \choose 2}1^5\right$$ = 150. \end{equation\*}
You might worry that to count surjective functions when the codomain is larger than 3 elements would be too tedious. We need to use PIE but with more than 3 sets the formula for PIE is very long. However, we have lucked out. As we saw in the example above, the number of functions which exclude a single element from the range is the same no matter which single element is excluded. Similarly, the number of functions which exclude a pair of elements will be the same for every pair. With larger codomains, we will see the same behavior with groups of 3, 4, and more elements excluded. So instead of adding/subtracting each of these, we can simply add or subtract all of them at once, if you know how many there are. This works just like it did in for the other types of counting questions in this section, only now the size of the various combinations of sets is a number raised to a power, as opposed to a binomial coefficient or factorial. Here's what happens with \\4\\ and \\5\\ elements in the codomain.
Example \\\PageIndex{9}\\
1. How many functions \\f: \\1,2,3,4,5\\ \to \\a,b,c,d\\\\ are surjective?
2. How many functions \\f: \\1,2,3,4,5\\ \to \\a,b,c,d,e\\\\ are surjective?
Solution
There are \\4^5\\ functions all together; we will subtract the functions which are not surjective. We could exclude any one of the four elements of the codomain, and doing so will leave us with \\3^5\\ functions for each excluded element. This counts too many so we subtract the functions which exclude two of the four elements of the codomain, each pair giving \\2^5\\ functions. But this excludes too many, so we add back in the functions which exclude three of the four elements of the codomain, each triple giving \\1^5\\ function. There are \\{4 \choose 1}\\ groups of functions excluding a single element, \\{4 \choose 2}\\ groups of functions excluding a pair of elements, and \\{4 \choose 3}\\ groups of functions excluding a triple of elements. This means that the number of functions which are *not* surjective is:
\begin{equation\*} {4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5. \end{equation\*}
We can now say that the number of functions which are surjective is:
\begin{equation\*} 4^5 - \left$${4 \choose 1}3^5 - {4 \choose 2}2^5 + {4 \choose 3}1^5\right$$. \end{equation\*}
The number of surjective functions is:
\begin{equation\*} 5^5 - \left$${5 \choose 1}4^5 - {5 \choose 2}3^5 + {5 \choose 3}2^5 - {5 \choose 4}1^5\right$$. \end{equation\*}
We took the total number of functions \\5^5\\ and subtracted all that were not surjective. There were \\{5 \choose 1}\\ ways to select a single element from the codomain to exclude from the range, and for each there were \\4^5\\ functions. But this double counts, so we use PIE and subtract functions excluding two elements from the range: there are \\{5 \choose 2}\\ choices for the two elements to exclude, and for each pair, \\3^5\\ functions. This takes out too many functions, so we add back in functions which exclude 3 elements from the range: \\{5 \choose 3}\\ choices for which three to exclude, and then \\2^5\\ functions for each choice of elements. Finally we take back out the 1 function which excludes 4 elements for each of the \\{5 \choose 4}\\ choices of 4 elements.
If you happen to calculate this number precisely, you will get 120 surjections. That happens to also be the value of \\5!\text{.}\\ This might seem like an amazing coincidence until you realize that every surjective function \\f:X \to Y\\ with \\\card{X} = \card{Y}\\ finite must necessarily be a bijection. The number of bijections is always \\\card{X}!\\ in this case. What we have here is a *combinatorial proof* of the following identity:
\begin{equation\*} n^n - \left$${n\choose 1}(n-1)^n - {n \choose 2}(n-2)^n + \cdots + {n \choose n-1}1^n \right$$ = n!. \end{equation\*}
We have seen that counting surjective functions is another nice example of the advanced use of the Principle of Inclusion/Exclusion. Also, counting injective functions turns out to be equivalent to permutations, and counting all functions has a solution akin to those counting problems where order matters but repeats are allowed (like counting the number of words you can make from a given set of letters).
These are not just a few more examples of the techniques we have developed in this chapter. Quite the opposite: everything we have learned in this chapter are examples of *counting functions*!
Example \\\PageIndex{10}\\
How many 5-letter words can you make using the eight letters \\a\\ through \\h\text{?}\\ How many contain no repeated letters?
Solution
By now it should be no surprise that there are \\8^5\\ words, and \\P(8,5)\\ words without repeated letters. The new piece here is that we are actually counting functions. For the first problem, we are counting all functions from \\\\1,2,\ldots, 5\\\\ to \\\\a,b,\ldots, h\\\text{.}\\ The numbers in the domain represent the *position* of the letter in the word, the codomain represents the letter that could be assigned to that position. If we ask for no repeated letters, we are asking for injective functions.
If \\A\\ and \\B\\ are *any* sets with \\\|A\| = 5\\ and \\\|B\| = 8\text{,}\\ then the number of functions \\f: A \to B\\ is \\8^5\\ and the number of injections is \\P(8,5)\text{.}\\ So if you can represent your counting problem as a function counting problem, most of the work is done.
Example \\\PageIndex{11}\\
How many subsets are there of \\\\1,2,\ldots, 9\\\text{?}\\ How many 9-bit strings are there (of any weight)?
Solution
We saw in Section 1.2 that the answer to both these questions is \\2^9\text{,}\\ as we can say yes or no (or 0 or 1) to each of the 9 elements in the set (positions in the bit-string). But \\2^9\\ also looks like the answer you get from counting functions. In fact, if you count all functions \\f: A \to B\\ with \\\|A\| = 9\\ and \\\|B\| = 2\text{,}\\ this is exactly what you get.
This makes sense! Let \\A = \\1,2,\ldots, 9\\\\ and \\B = \\y, n\\\text{.}\\ We are assigning each element of the set either a yes or a no. Or in the language of bit-strings, we would take the 9 positions in the bit string as our domain and the set \\\\0,1\\\\ as the codomain.
So far we have not used a function as a model for binomial coefficients (combinations). Think for a moment about the relationship between combinations and permutations, say specifically \\{9 \choose 3}\\ and \\P(9,3)\text{.}\\ We *do* have a function model for \\P(9,3)\text{.}\\ This is the number of *injective* functions from a set of size 3 (say \\\\1,2,3\\\\ to a set of size 9 (say \\\\1,2,\ldots, 9\\\$ since there are 9 choices for where to send the first element of the domain, then only 8 choices for the second, and 7 choices for the third. For example, the function might look like this:
\begin{equation\*} f(1) = 5 \qquad f(2) = 8 \qquad f(3) = 4. \end{equation\*}
This is a different function from:
\begin{equation\*} f(1) = 4 \qquad f(2) = 5 \qquad f(3) = 8. \end{equation\*}
Now \\P(9,3)\\ counts these as different outcomes correctly, but \\{9\choose 3}\\ will count these (among others) as just one outcome. In fact, in terms of functions \\{9 \choose 3}\\ just counts the number of different ranges possible of injective functions. This should not be a surprise since binomial coefficients counts subsets, and the range is a possible subset of the codomain. 4 A more mathematically sophisticated interpretation of combinations is that we are defining two injective functions to be *equivalent* if they have the same range, and then counting the number of equivalence classes under this notion of equivalence.
While it is possible to interpret combinations as functions, perhaps the better advice is to instead use combinations (or stars and bars) when functions are not quite the right way to interpret the counting question.
---
1_E_3A_Counting__Exercises_
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/1%3A_Counting/1.E%3A_Counting_(Exercises)
Skip to main content
\\ \def\d{\displaystyle}\\
\\ \newcommand{\f}$$1$${\mathfrak \#1}\\
\\ \newcommand{\s}$$1$${\mathscr \#1}\\
\\ \def\N{\mathbb N}\\
\\ \def\B{\mathbf{B}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\Z{\mathbb Z}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\Q{\mathbb Q}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\R{\mathbb R}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\C{\mathbb C}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\F{\mathbb F}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\A{\mathbb A}\\
\\ \def\twosetbox{(-2,-1.5) rectangle (2,1.5)}\\
\\ \def\X{\mathbb X}\\
\\ \def\threesetbox{(-2,-2.5) rectangle (2,1.5)}\\
\\ \def\E{\mathbb E}\\
\\ \def\O{\mathbb O}\\
\\ \def\U{\mathcal U}\\
\\ \def\pow{\mathcal P}\\
\\ \def\inv{^{-1}}\\
\\ \def\nrml{\triangleleft}\\
\\ \def\st{:}\\
\\ \def\\{\widetilde}\\
\\ \def\rem{\mathcal R}\\
\\ \def\sigalg{\$\sigma\$-algebra }\\
\\ \def\Gal{\mbox{Gal}}\\
\\ \def\iff{\leftrightarrow}\\
\\ \def\Iff{\Leftrightarrow}\\
\\ \def\land{\wedge}\\
\\ \def\And{\bigwedge}\\
\\ \def\entry{\entry}\\
\\ \def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}\\
\\ \def\Vee{\bigvee}\\
\\ \def\VVee{\d\Vee\mkern-18mu\Vee}\\
\\ \def\imp{\rightarrow}\\
\\ \def\Imp{\Rightarrow}\\
\\ \def\Fi{\Leftarrow}\\
\\ \def\var{\mbox{var}}\\
\\ \def\Th{\mbox{Th}}\\
\\ \def\entry{\entry}\\
\\ \def\sat{\mbox{Sat}}\\
\\ \def\con{\mbox{Con}}\\
\\ \def\iffmodels{\bmodels\models}\\
\\ \def\dbland{\bigwedge \\\\\bigwedge}\\
\\ \def\dom{\mbox{dom}}\\
\\ \def\rng{\mbox{range}}\\
\\ \def\isom{\cong}\\
\\\DeclareMathOperator{\wgt}{wgt}\\
\\ \newcommand{\vtx}$$2$${node$$fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2$${}}\\
\\ \newcommand{\va}$$1$${\vtx{above}{#1}}\\
\\ \newcommand{\vb}$$1$${\vtx{below}{#1}}\\
\\ \newcommand{\vr}$$1$${\vtx{right}{#1}}\\
\\ \newcommand{\vl}$$1$${\vtx{left}{#1}}\\
\\ \renewcommand{\v}{\vtx{above}{}}\\
\\ \def\circleA{(-.5,0) circle (1)}\\
\\ \def\circleAlabel{(-1.5,.6) node$$above$${\$A\$}}\\
\\ \def\circleB{(.5,0) circle (1)}\\
\\ \def\circleBlabel{(1.5,.6) node$$above$${\$B\$}}\\
\\ \def\circleC{(0,-1) circle (1)}\\
\\ \def\circleClabel{(.5,-2) node$$right$${\$C\$}}\\
\\ \def\twosetbox{(-2,-1.4) rectangle (2,1.4)}\\
\\ \def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}\\
\\ \def\ansfilename{practice-answers}\\
\\ \def\shadowprops{ {fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}} }\\
\\ \renewcommand{\bar}{\overline}\\
\\ \newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\ \newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\ \newcommand{\lt}{<}\\
\\ \newcommand{\gt}{>}\\
\\ \newcommand{\amp}{&}\\
\\ \newcommand{\hexbox}$$3$${
\def\x{-cos{30}\*\r\*#1+cos{30}\*#2\*\r\*2}
\def\y{-\r\*#1-sin{30}\*\r\*#1}
\draw (\x,\y) +(90:\r) -- +(30:\r) -- +(-30:\r) -- +(-90:\r) -- +(-150:\r) -- +(150:\r) -- cycle;
\draw (\x,\y) node{#3};
}\\
\\\renewcommand{\bar}{\overline}\\
\\\newcommand{\card}$$1$${\left\| \#1 \right\|}\\
\\\newcommand{\twoline}$$2$${\begin{pmatrix}#1 \\ \#2 \end{pmatrix}}\\
\\\newcommand{\lt}{\<}\\
\\\newcommand{\gt}{\>}\\
\\\newcommand{\amp}{&}\\
1.1: Additive and Multiplicative Principles
1
Your wardrobe consists of 5 shirts, 3 pairs of pants, and 17 bow ties. How many different outfits can you make?
Answer
There are 255 outfits. Use the multiplicative principle.
2
For your college interview, you must wear a tie. You own 3 regular (boring) ties and 5 (cool) bow ties.
1. How many choices do you have for your neck-wear?
2. You realize that the interview is for clown college, so you should probably wear both a regular tie and a bow tie. How many choices do you have now?
3. For the rest of your outfit, you have 5 shirts, 4 skirts, 3 pants, and 7 dresses. You want to select either a shirt to wear with a skirt or pants, or just a dress. How many outfits do you have to choose from?
Answer
1. 8 ties. Use the additive principle.
2. 15 ties. Use the multiplicative principle
3. \\5 \cdot (4+3) + 7 = 42\\ outfits.
3
Your Blu-ray collection consists of 9 comedies and 7 horror movies. Give an example of a question for which the answer is:
1. 16\.
2. 63\.
Answer
1. For example, 16 is the number of choices you have if you want to watch one movie, either a comedy or horror flick.
2. For example, 63 is the number of choices you have if you will watch two movies, first a comedy and then a horror.
4
We usually write numbers in decimal form (or base 10), meaning numbers are composed using 10 different “digits” \\\\0,1,\ldots, 9\\\text{.}\\ Sometimes though it is useful to write numbers hexadecimal or base 16. Now there are 16 distinct digits that can be used to form numbers: \\\\0, 1, \ldots, 9, \mathrm{A, B, C, D, E, F}\\\text{.}\\ So for example, a 3 digit hexadecimal number might be 2B8.
1. How many 2-digit hexadecimals are there in which the first digit is E or F? Explain your answer in terms of the additive principle (using either events or sets).
2. Explain why your answer to the previous part is correct in terms of the multiplicative principle (using either events or sets). Why do both the additive and multiplicative principles give you the same answer?
3. How many 3-digit hexadecimals start with a letter (A-F) and end with a numeral (0-9)? Explain.
4. How many 3-digit hexadecimals start with a letter (A-F) or end with a numeral (0-9) (or both)? Explain.
5
Suppose you have sets \\A\\ and \\B\\ with \\\card{A} = 10\\ and \\\card{B} = 15\text{.}\\
1. What is the largest possible value for \\\card{A \cap B}\text{?}\\
2. What is the smallest possible value for \\\card{A \cap B}\text{?}\\
3. What are the possible values for \\\card{A \cup B}\text{?}\\
Answer
1. To maximize the number of elements in common between \\A\\ and \\B\text{,}\\ make \\A \subset B\text{.}\\ This would give \\\card{A \cap B} = 10\text{.}\\
2. \\A\\ and \\B\\ might have no elements in common, giving \\\card{A\cap B} = 0\text{.}\\
3. \\15 \le \card{A \cup B} \le 25\text{.}\\ In fact, when \\\card{A \cap B} = 0\\ then \\\card{A \cup B} = 25\\ and when \\\card{A \cap B} = 10\\ then \\\card{A \cup B} = 15\text{.}\\
6
If \\\card{A} = 8\\ and \\\card{B} = 5\text{,}\\ what is \\\card{A \cup B} + \card{A \cap B}\text{?}\\
Answer
\\\card{A \cup B} + \card{A \cap B} = 13\text{.}\\ Use PIE: we know \\\card{A \cup B} = 8 + 5 - \card{A \cap B}\text{.}\\
7
A group of college students were asked about their TV watching habits. Of those surveyed, 28 students watch *The Walking Dead*, 19 watch *The Blacklist*, and 24 watch *Game of Thrones*. Additionally, 16 watch *The Walking Dead* and *The Blacklist*, 14 watch *The Walking Dead* and *Game of Thrones*, and 10 watch *The Blacklist* and *Game of Thrones*. There are 8 students who watch all three shows. How many students surveyed watched at least one of the shows?
Answer
39 students. Use PIE or a Venn diagram.
8
In a recent survey, 30 students reported whether they liked their potatoes Mashed, French-fried, or Twice-baked. 15 liked them mashed, 20 liked French fries, and 9 liked twice baked potatoes. Additionally, 12 students liked both mashed and fried potatoes, 5 liked French fries and twice baked potatoes, 6 liked mashed and baked, and 3 liked all three styles. How many students *hate* potatoes? Explain why your answer is correct.
9
For how many \\n \in \\1,2, \ldots, 500\\\\ is \\n\\ a multiple of one or more of 5, 6, or 7?
Hint:
To find out how many numbers are divisible by 6 and 7, for example, take \\500/42\\ and round down.
10
Let \\A\text{,}\\ \\B\text{,}\\ and \\C\\ be sets.
1. Find \\\card{(A \cup C)\setminus B}\\ provided \\\card{A} = 50\text{,}\\ \\\card{B} = 45\text{,}\\ \\\card{C} = 40\text{,}\\ \\\card{A\cap B} = 20\text{,}\\ \\\card{A \cap C} = 15\text{,}\\ \\\card{B \cap C} = 23\text{,}\\ and \\\card{A \cap B \cap C} = 12\text{.}\\
2. Describe a set in terms of \\A\text{,}\\ \\B\text{,}\\ and \\C\\ with cardinality 26.
11
Consider all 5 letter “words” made from the letters \\a\\ through \\h\text{.}\\ (Recall, words are just strings of letters, not necessarily actual English words.)
1. How many of these words are there total?
2. How many of these words contain no repeated letters?
3. How many of these words start with the sub-word “aha”?
4. How many of these words either start with “aha” or end with “bah” or both?
5. How many of the words containing no repeats also do not contain the sub-word “bad”?
Answer
1. \\8^5 = 32768\\ words, since you select from 8 letters 5 times.
2. \\8\cdot 7\cdot 6\cdot 5\cdot 4 = 6720\\ words. After selecting a letter, you have fewer letters to select for the next one.
3. \\8 \cdot 8 =64\\ words: you need to select the 4th and 5th letters.
4. \\64 + 64 - 0 = 128\\ words. There are 64 words which start with “aha” and another 64 words that end with “bah.” Perhaps we over counted the words that both start with “aha” and end with “bah”, but since the words are only 5 letters long, there are no such words.
5. \$8\cdot 7\cdot 6\cdot 5\cdot 4) - 3\cdot (5\cdot 4) = 6660\\ words. All the words minus the bad ones. The taboo word can be in any of three positions (starting with letter 1, 2, or 3) and for each position we must choose the other two letters (from the remaining 5 letters).
12
For how many three digit numbers (100 to 999) is the *sum of the digits* even? (For example, \\343\\ has an even sum of digits: \\3+4+3 = 10\\ which is even.) Find the answer and explain why it is correct in at least two *different* ways.
13
The number 735000 factors as \\2^3 \cdot 3 \cdot 5^4 \cdot 7^2\text{.}\\ How many divisors does it have? Explain your answer using the multiplicative principle.
1.2: Binomial Coefficients
1
Let \\S = \\1, 2, 3, 4, 5, 6\\\\
1. How many subsets are there total?
2. How many subsets have \\\\2,3,5\\\\ as a subset?
3. How many subsets contain at least one odd number?
4. How many subsets contain exactly one even number?
Answer
1. \\2^6 = 64\\ subsets. We need to select yes/no for each of the six elements.
2. \\2^3 = 8\\ subsets. We need to select yes/no for each of the remaining three elements.
3. \\2^6 - 2^3 = 56\\ subsets. There are 8 subsets which do not contain any odd numbers (select yes/no for each even number).
4. \\3\cdot 2^3 = 24\\ subsets. First pick the even number. Then say yes or no to each of the odd numbers.
2
Let \\S = \\1, 2, 3, 4, 5, 6\\\\
1. How many subsets are there of cardinality 4?
2. How many subsets of cardinality 4 have \\\\2,3,5\\\\ as a subset?
3. How many subsets of cardinality 4 contain at least one odd number?
4. How many subsets of cardinality 4 contain exactly one even number?
Answer
1. \\{6\choose 4} = 15\\ subsets.
2. \\{3 \choose 1} = 3\\ subsets. We need to select 1 of the 3 remaining elements to be in the subset.
3. \\{6 \choose 4} = 15\\ subsets. All subsets of cardinality 4 must contain at least one odd number.
4. \\{3 \choose 1} = 3\\ subsets. Select 1 of the 3 even numbers. The remaining three odd numbers of \\S\\ must all be in the set.
3
Let \\A = \\1,2,3,\ldots,9\\\text{.}\\
1. How many subsets of \\A\\ are there? That is, find \\\|\pow(A)\|\text{.}\\ Explain.
2. How many subsets of \\A\\ contain exactly 5 elements? Explain.
3. How many subsets of \\A\\ contain only even numbers? Explain.
4. How many subsets of \\A\\ contain an even number of elements? Explain.
4
How many \\9\\-bit strings (that is, bit strings of length 9) are there which:
1. Start with the sub-string 101? Explain.
2. Have weight 5 (i.e., contain exactly five 1's) and start with the sub-string 101? Explain.
3. Either start with \\101\\ or end with \\11\\ (or both)? Explain.
4. Have weight 5 and either start with 101 or end with 11 (or both)? Explain.
5
You break your piggy-bank to discover lots of pennies and nickels. You start arranging these in rows of 6 coins.
1. You find yourself making rows containing an equal number of pennies and nickels. For fun, you decide to lay out every possible such row. How many coins will you need?
2. How many coins would you need to make all possible rows of 6 coins (not necessarily with equal number of pennies and nickels)?
Answer
1. We can think of each row as a 6-bit string of weight 3 (since of the 6 coins, we require 3 to be pennies). Thus there are \\{6 \choose 3} = 20\\ rows possible. Each row requires 6 coins, so if we want to make all the rows at the same time, we will need 120 coins (60 of each).
2. Now there are \\2^6 = 64\\ rows possible, which is also \\{6 \choose 0} + {6\choose 1} + {6 \choose 2} + {6 \choose 3} + {6 \choose 4} + {6 \choose 5} + {6 \choose 6}\text{,}\\ if you break them up into rows containing 0, 1, 2, etc. pennies. Thus we need \\6 \cdot 64 = 384\\ coins (192 of each).
6
How many 10-bit strings contain 6 or more 1's?
Answer
\\{10 \choose 6} + {10\choose 7} + {10\choose 8} + {10 \choose 9} + {10\choose 10} = 386\\ strings. Count the number of strings with each permissible number of 1's separately, then add them up.
7
How many subsets of \\\\0,1,\ldots, 9\\\\ have cardinality 6 or more?
Hint:
Break the question into five cases.
8
What is the coefficient of \\x^{12}\\ in \$x+2)^{15}\text{?}\\
Answer
To get an \\x^{12}\text{,}\\ we must pick 12 of the 15 factors to contribute an \\x\text{,}\\ leaving the other 3 to contribute a 2. There are \\{15 \choose 12}\\ ways to select these 12 factors. So the term containing an \\x^{12}\\ will be \\{15 \choose 12}x^{12}2^{3}\text{.}\\ In other words, the coefficient of \\x^{12}\\ is \\{15\choose 12}2^3 = 3640\text{.}\\
9
What is the coefficient of \\x^9\\ in the expansion of \$x+1)^{14} + x^3(x+2)^{15}\text{?}\\
10
How many shortest lattice paths start at (3,3) and
1. end at (10,10)?
2. end at (10,10) and pass through (5,7)?
3. end at (10,10) and avoid (5,7)?
Answer
1. \\{14 \choose 7} = 3432\\ paths. The paths all have length 14 (7 steps up and 7 steps right), we just select which 7 of those 14 should be up.
2. \\{6 \choose 2}{8\choose 5} = 840\\ paths. First travel to (5,7), and then continue on to (10,10).
3. \\{14 \choose 7} - {6\choose 2}{8 \choose 5}\\ paths. Remove all the paths that you found in part (b).
11
Gridtown USA, besides having excellent donut shoppes, is known for its precisely laid out grid of streets and avenues. Streets run east-west, and avenues north-south, for the entire stretch of the town, never curving and never interrupted by parks or schools or the like.
Suppose you live on the corner of 1st and 1st and work on the corner of 12th and 12th. Thus you must travel 22 blocks to get to work as quickly as possible.
1. How many different routes can you take to work, assuming you want to get there as quickly as possible?
2. Now suppose you want to stop and get a donut on the way to work, from your favorite donut shoppe on the corner of 8th st and 10th ave. How many routes to work, via the donut shoppe, can you take (again, ensuring the shortest possible route)?
3. Disaster Strikes Gridtown: there is a pothole on 4th avenue between 5th and 6th street. How many routes to work can you take avoiding that unsightly (and dangerous) stretch of road?
4. How many routes are there both avoiding the pothole and visiting the donut shoppe?
12
Suppose you are ordering a large pizza from *D.P. Dough*. You want 3 distinct toppings, chosen from their list of 11 vegetarian toppings.
1. How many choices do you have for your pizza?
2. How many choices do you have for your pizza if you refuse to have pineapple as one of your toppings?
3. How many choices do you have for your pizza if you *insist* on having pineapple as one of your toppings?
4. How do the three questions above relate to each other?
13
Explain why the coefficient of \\x^5y^3\\ the same as the coefficient of \\x^3y^5\\ in the expansion of \$x+y)^8\text{?}\\
1.3: Combinations and Permutations
1
A pizza parlor offers 10 toppings.
1. How many 3-topping pizzas could they put on their menu? Assume double toppings are not allowed.
2. How many total pizzas are possible, with between zero and ten toppings (but not double toppings) allowed?
3. The pizza parlor will list the 10 toppings in two equal-sized columns on their menu. How many ways can they arrange the toppings in the left column?
Answer
1. \\{10 \choose 3} = 120\\ pizzas. We must choose (in no particular order) 3 out of the 10 toppings.
2. \\2^{10} = 1024\\ pizzas. Say yes or no to each topping.
3. \\P(10,5) = 30240\\ ways. Assign each of the 5 spots in the left column to a unique pizza topping.
2
A combination lock consists of a dial with 40 numbers on it. To open the lock, you turn the dial to the right until you reach a first number, then to the left until you get to second number, then to the right again to the third number. The numbers must be distinct. How many different combinations are possible?
Answer
Despite its name, we are not looking for a combination here. The order in which the three numbers appears matters. There are \\P(40,3) = 40\cdot 39 \cdot 38\\ different possibilities for the “combination”. This is assuming you cannot repeat any of the numbers (if you could, the answer would be \\40^3\$.
3
Using the digits 2 through 8, find the number of different 5-digit numbers such that:
1. Digits can be used more than once.
2. Digits cannot be repeated, but can come in any order.
3. Digits cannot be repeated and must be written in increasing order.
4. Which of the above counting questions is a combination and which is a permutation? Explain why this makes sense.
4
How many triangles are there with vertices from the points shown below? Note, we are not allowing degenerate triangles - ones with all three vertices on the same line, but we do allow non-right triangles. Explain why your answer is correct.
\![$$(https://math.libretexts.org/images/triangle-dots.svg)
Hint:
You need exactly two points on either the \\x\\- or \\y\\-axis, but don't over-count the right triangles.
5
How many quadrilaterals can you draw using the dots below as vertices (corners)?
\![$$(https://math.libretexts.org/images/quad-counting.svg)
Answer
\\{7\choose 2}{7\choose 2} = 441\\ quadrilaterals. We must pick two of the seven dots from the top row and two of the seven dots on the bottom row. However, it does not make a difference which of the two (on each row) we pick first because once these four dots are selected, there is exactly one quadrilateral that they determine.
6
How many of the quadrilaterals possible in the previous problem are:
1. Squares?
2. Rectangles?
3. Parallelograms?
4. Trapezoids? 2 Here, as in calculus, a trapezoid is defined as a quadrilateral with *at least* one pair of parallel sides. In particular, parallelograms are trapezoids.
5. Trapezoids that are not parallelograms?
Answer
1. 5 squares. You need to skip exactly one dot on the top and on the bottom to make the side lengths equal. Once you pick a dot on the top, the other three dots are determined.
2. \\{7 \choose 2}\\ rectangles. Once you select the two dots on the top, the bottom two are determined.
3. This is tricky since you need to worry about running out of space. One way to count: break into cases by the location of the top left corner. You get \\{7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) = 91\\ parallelograms.
4. All of them
5. \\{7\choose 2}{7\choose 2} - \left$$ {7 \choose 2} + ({7 \choose 2}-1) + ({7 \choose 2} - 3) + ({7 \choose 2} - 6) + ({7 \choose 2} - 10) + ({7 \choose 2} - 15) \right$$\text{.}\\ All of them, except the parallelograms.
7
An *anagram* of a word is just a rearrangement of its letters. How many different anagrams of “uncopyrightable” are there? (This happens to be the longest common English word without any repeated letters.)
8
How many anagrams are there of the word “assesses” that start with the letter “a”?
Answer
After the first letter (a), we must rearrange the remaining 7 letters. There are only two letters (s and e), so this is really just a bit-string question (think of s as 1 and e as 0). Thus there \\{7 \choose 2} = 21\\ anagrams starting with “a”.
9
How many anagrams are there of “anagram”?
10
On a business retreat, your company of 20 businessmen and businesswomen go golfing.
1. You need to divide up into foursomes (groups of 4 people): a first foursome, a second foursome, and so on. How many ways can you do this?
2. After all your hard work, you realize that in fact, you want each foursome to include one of the five Board members. How many ways can you do this?
Answer
1. \\{20 \choose 4}{16 \choose 4}{12 \choose 4}{8 \choose 4}{4 \choose 4}\\ ways. Pick 4 out of 20 people to be in the first foursome, then 4 of the remaining 16 for the second foursome, and so on (use the multiplicative principle to combine).
2. \\5!{15 \choose 3}{12 \choose 3}{9 \choose 3}{6 \choose 3}{3 \choose 3}\\ ways. First determine the tee time of the 5 board members, then select 3 of the 15 non board members to golf with the first board member, then 3 of the remaining 12 to golf with the second, and so on.
11
How many different seating arrangements are possible for King Arthur and his 9 knights around their round table?
Answer
\\9!\\ (there are 10 people seated around the table, but it does not matter where King Arthur sits, only who sits to his left, two seats to his left, and so on).
12
Consider sets \\A\\ and \\B\\ with \\\|A\| = 10\\ and \\\|B\| = 17\text{.}\\
1. How many functions \\f: A \to B\\ are there?
2. How many functions \\f: A \to B\\ are injective?
Answer
1. \\17^{10}\\ functions. There are 17 choices for the image of each element in the domain.
2. \\P(17, 10)\\ injective functions. There are 17 choices for image of the first element of the domain, then only 16 choices for the second, and so on.
13
Consider functions \\f: \\1,2,3,4\\ \to \\1,2,3,4,5,6\\\text{.}\\
1. How many functions are there total?
2. How many functions are injective?
3. How many of the injective functions are *increasing*? To be increasing means that if \\a \lt b\\ then \\f(a) \lt f(b)\text{,}\\ or in other words, the outputs get larger as the inputs get larger.
14
We have seen that the formula for \\P(n,k)\\ is \\\dfrac{n!}{(n-k)!}\text{.}\\ Your task here is to explain *why* this is the right formula.
1. Suppose you have 12 chips, each a different color. How many different stacks of 5 chips can you make? Explain your answer and why it is the same as using the formula for \\P(12,5)\text{.}\\
2. Using the scenario of the 12 chips again, what does \\12!\\ count? What does \\7!\\ count? Explain.
3. Explain why it makes sense to divide \\12!\\ by \\7!\\ when computing \\P(12,5)\\ (in terms of the chips).
4. Does your explanation work for numbers other than 12 and 5? Explain the formula \\P(n,k) = \frac{n!}{(n-k)!}\\ using the variables \\n\\ and \\k\text{.}\\
1.4: Combinatorial Proofs
1
Prove the identity \\{n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}\\ using a question about subsets.
Answer
Proof
Question: How many subsets of size \\k\\ are there of the set \\\\1,2,\ldots, n\\\text{?}\\
Answer 1: You must choose \\k\\ out of \\n\\ elements to put in the set, which can be done in \\{n \choose k}\\ ways.
Answer 2: First count the number of \\k\\-element subsets of \\\\1,2,\ldots, n\\\\ which contain the number \\n\text{.}\\ We must choose \\k-1\\ of the \\n-1\\ other element to include in this set. Thus there are \\{n-1\choose k-1}\\ such subsets. We have not yet counted all the \\k\\-element subsets of \\\\1,2,\ldots, n\\\\ though. In fact, we have missed exactly those subsets which do NOT contain \\n\text{.}\\ To form one of these subsets, we need to choose \\k\\ of the other \\n-1\\ elements, so this can be done in \\{n-1 \choose k}\\ ways. Thus the answer to the question is \\{n-1 \choose k-1} + {n-1 \choose k}\text{.}\\
Since the two answers are both answers tot eh same question, they are equal, establishing the identity \\{n\choose k} = {n-1 \choose k-1} + {n-1 \choose k}\text{.}\\
\\\square\\
2
Give a combinatorial proof of the identity \\2+2+2 = 3\cdot 2\text{.}\\
Answer
Proof
Question: How many 2-letter words start with *a*, *b*, or *c* and end with either *y* or *z*?
Answer 1: There are two words that start with *a*, two that start with *b*, two that start with *c*, for a total of \\2+2+2\text{.}\\
Answer 2: There are three choices for the first letter and two choices for the second letter, for a total of \\3 \cdot 2\text{.}\\
Since the two answers are both answers to the same question, they are equal. Thus \\2 + 2 + 2 = 3\cdot 2\text{.}\\
\\\square\\
3
Give a combinatorial proof for the identity \\1 + 2 + 3 + \cdots + n = {n+1 \choose 2}\text{.}\\
Answer
Proof
Question: How many subsets of \\A = {1,2,3, \ldots, n+1}\\ contain exactly two elements?
Answer 1: We must choose 2 elements from \\n+1\\ choices, so there are \\{n+1 \choose 2}\\ subsets.
Answer 2: We break this question down into cases, based on what the larger of the two elements in the subset is. The larger element can't be 1, since we need at least one element smaller than it.
Larger element is 2: there is 1 choice for the smaller element.
Larger element is 3: there are 2 choices for the smaller element.
Larger element is 4: there are 3 choices for the smaller element.
And so on. When the larger element is \\n+1\text{,}\\ there are \\n\\ choices for the smaller element. Since each two element subset must be in exactly one of these cases, the total number of two element subsets is \\1 + 2 + 3 + \cdots + n\text{.}\\
Answer 1 and answer 2 are both correct answers to the same question, so they must be equal. Therefore,
\begin{equation\*} 1 + 2 + 3 + \cdots + n = {n+1 \choose 2} \end{equation\*}
\\\square\\
4
A woman is getting married. She has 15 best friends but can only select 6 of them to be her bridesmaids, one of which needs to be her maid of honor. How many ways can she do this?
1. What if she first selects the 6 bridesmaids, and then selects one of them to be the maid of honor?
2. What if she first selects her maid of honor, and then 5 other bridemaids?
3. Explain why \\6 {15 \choose 6} = 15 {14 \choose 5}\text{.}\\
Answer
1. She has \\{15 \choose 6}\\ ways to select the 6 bridesmaids, and then for each way, has 6 choices for the maid of honor. Thus she has \\{15 \choose 6}6\\ choices.
2. She has 15 choices for who will be her maid of honor. Then she needs to select 5 of the remaining 14 friends to be bridesmaids, which she can do in \\{14 \choose 5}\\ ways. Thus she has \\15 {14 \choose 5}\\ choices.
3. We have answered the question (how many wedding parties can the bride choose from) in two ways. The first way gives the left-hand side of the identity and the second way gives the right-hand side of the identity. Therefore the identity holds.
5
Give a combinatorial proof of the identity \\{n \choose 2}{n-2 \choose k-2} = {n\choose k}{k \choose 2}\text{.}\\
Answer
Proof
Question: You have a large container filled with ping-pong balls, all with a different number on them. You must select \\k\\ of the balls, putting two of them in a jar and the others in a box. How many ways can you do this?
Answer 1: First select 2 of the \\n\\ balls to put in the jar. Then select \\k-2\\ of the remaining \\n-2\\ balls to put in the box. The first task can be completed in \\{n \choose 2}\\ different ways, the second task in \\{n-2 \choose k-2}\\ ways. Thus there are \\{n \choose 2}{n-2 \choose k-2}\\ ways to select the balls.
Answer 2: First select \\k\\ balls from the \\n\\ in the container. Then pick 2 of the \\k\\ balls you picked to put in the jar, placing the remaining \\k-2\\ in the box. The first task can be completed in \\{n \choose k}\\ ways, the second task in \\{k \choose 2}\\ ways. Thus there are \\{n \choose k}{k \choose 2}\\ ways to select the balls.
Since both answers count the same thing, they must be equal and the identity is established.
\\\square\\
6
Consider the bit strings in \\\B^6_2\\ (bit strings of length 6 and weight 2).
1. How many of those bit strings start with 1?
2. How many of those bit strings start with 01?
3. How many of those bit strings start with 001?
4. Are there any other strings we have not counted yet? Which ones, and how many are there?
5. How many bit strings are there total in \\\B^6_2\text{?}\\
6. What binomial identity have you just given a combinatorial proof for?
Answer
1. After the 1, we need to find a 5-bit string with one 1. There are \\{5 \choose 1}\\ ways to do this.
2. \\{4 \choose 1}\\ strings (we need to pick 1 of the remaining 4 slots to be the second 1).
3. \\{3 \choose 1}\\ strings.
4. Yes. We still need strings starting with 0001 (there are \\{2 \choose 1}\\ of these) and strings starting 00001 (there is only \\{1 \choose 1} = 1\\ of these).
5. \\{6 \choose 2}\\ strings
6. An example of the Hockey Stick Theorem: \begin{equation\*} {1 \choose 1} + {2 \choose 1} + {3 \choose 1} + {4 \choose 1} + {5 \choose 1} = {6 \choose 2} \end{equation\*}
7
Let's count ternary digit strings, that is, strings in which each digit can be 0, 1, or 2.
1. How many ternary digit strings contain exactly \\n\\ digits?
2. How many ternary digit strings contain exactly \\n\\ digits and \\n\\ 2's.
3. How many ternary digit strings contain exactly \\n\\ digits and \\n-1\\ 2's. (Hint: where can you put the non-2 digit, and then what could it be?)
4. How many ternary digit strings contain exactly \\n\\ digits and \\n-2\\ 2's. (Hint: see previous hint)
5. How many ternary digit strings contain exactly \\n\\ digits and \\n-k\\ 2's.
6. How many ternary digit strings contain exactly \\n\\ digits and no 2's. (Hint: what kind of a string is this?)
7. Use the above parts to give a combinatorial proof for the identity \begin{equation\*} {n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n. \end{equation\*}
Answer
1. \\3^n\\ strings, since there are 3 choices for each of the \\n\\ digits.
2. \\1\\ string, since all the digits need to be 2's. However, we might write this as \\{n \choose 0}\\ strings.
3. There are \\{n \choose 1}\\ places to put the non-2 digit. That digit can be either a 0 or a 1, so there are \\2{n \choose 1}\\ such strings.
4. We must choose two slots to fill with 0's or 1's. There are \\{n \choose 2}\\ ways to do that. Once the slots are picked, we have two choices for the first slot (0 or 1) and two choices for the second slot (0 or 1). So there are a total of \\2^2{n \choose 2}\\ such strings.
5. There are \\{n \choose k}\\ ways to pick which slots don't have the 2's. Then those slots can be filled in \\2^k\\ ways (0 or 1 for each slot). So there are \\2^k{n \choose k}\\ such strings.
6. These strings contain just 0's and 1's, so they are bit strings. There are \\2^n\\ bit strings. But keeping with the pattern above, we might write this as \\2^n {n \choose n}\\ strings.
7. We answer the question of how many length \\n\\ ternary digit strings there are in two ways. First, each digit can be one of three choices, so the total number of strings is \\3^n\text{.}\\ On the other hand, we could break the question down into cases by how many of the digits are 2's. If they are all 2's, then there are \\{n \choose 0}\\ strings. If all but one is a 2, then there are \\2{n \choose 1}\\ strings. If all but 2 of the digits are 2's, then there are \\2^2{n \choose 2}\\ strings. We choose 2 of the \\n\\ digits to be non-2, and then there are 2 choices for each of those digits. And so on for every possible number of 2's in the string. Therefore \\{n \choose 0} + 2{n \choose 1} + 2^2{n \choose 2} + 2^3{n \choose 3} + \cdots + 2^n{n \choose n} = 3^n. \\
8
How many ways are there to rearrange the letters in the word “rearrange”? Answer this question in at least two different ways to establish a binomial identity.
Answer
The word contains 9 letters: 3 “r”s, 2 “a”s and 2 “e”s, along with an “n” and a “g”. We could first select the positions for the “r”s in \\{9 \choose 3}\\ ways, then the “a”s in \\{6 \choose 2}\\ ways, the “e”s in \\{4 \choose 2}\\ ways and then select one of the remaining two spots to put the “n” (placing the “g” in the last spot). This gives the answer
\begin{equation\*} {9 \choose 3}{6 \choose 2}{4 \choose 2}{2\choose 1}{1\choose 1}. \end{equation\*}
Alternatively, we could select the positions of the letters in the opposite order, which would give an answer
\begin{equation\*} {9 \choose 1}{8\choose 1}{7 \choose 2}{5\choose 2}{3\choose 3}. \end{equation\*}
(where the 3 “r”s go in the remaining 3 spots). These two expressions are equal:
9
Give a combinatorial proof for the identity \\P(n,k) = {n \choose k}k!\\
Answer
Proof
Question: How many \\k\\-letter words can you make using \\n\\ different letters without repeating any letter?
Answer 1: There are \\n\\ choices for the first letter, \\n-1\\ choices for the second letter, \\n-2\\ choices for the third letter, and so on until \\n - (k-1)\\ choices for the \\k\\th letter (since \\k-1\\ letters have already been assigned at that point). The product of these numbers can be written \\\frac{n!}{(n-k)!}\\ which is \\P(n,k)\text{.}\\ Therefore there are \\P(n,k)\\ words.
Answer 2: First pick \\k\\ letters to be in the word from the \\n\\ choices. This can be done in \\{n \choose k}\\ ways. Now arrange those letters into a word. There are \\k\\ choices for the first letter, \\k-1\\ choices for the second, and so on, for a total of \\k!\\ arrangements of the \\k\\ letters. Thus the total number of words is \\{n \choose k}k!\text{.}\\
Since the two answers are correct answers to the same question, we have established that \\P(n,k) = {n \choose k}k!\text{.}\\
\\\square\\
10
Establish the identity below using a combinatorial proof.
\begin{equation\*} {2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2} = {n+3 \choose 5}. \end{equation\*}
Answer
Proof
Question: How many 5-element subsets are there of the set \\\\1,2,\ldots, n+3\\\text{.}\\
Answer 1: We choose 5 out of the \\n+3\\ elements, so \\{n+3 \choose 5}\\ subsets.
Answer 2: Break this up into cases by what the “middle” (third smallest) element of the 5 element subset is. The smallest this could be is a 3. In that case, we have \\{2 \choose 2}\\ choices for the numbers below it, and \\{n \choose 2}\\ choices for the numbers above it. Alternatively, the middle number could be a 4. In this case there are \\{3 \choose 2}\\ choices for the bottom two numbers and \\{n-1 \choose 2}\\ choices for the top two numbers. If the middle number is 5, then there are \\{4 \choose 2}\\ choices for the bottom two numbers and \\{n-2 \choose 2}\\ choices for the top two numbers. An so on, all the way up to the largest the middle number could be, which is \\n+1\text{.}\\ In that case there are \\{n \choose 2}\\ choices for the bottom two numbers and \\{2 \choose 2}\\ choices for the top number. Thus the number of 5 element subsets is
\begin{equation\*} {2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2}. \end{equation\*}
Since the two answers correctly answer the same question, we have \begin{equation\*} {2 \choose 2}{n \choose 2} + {3 \choose 2}{n-1 \choose 2} + {4\choose 2}{n-2 \choose 2} + \cdots + {n\choose 2}{2\choose 2} = {n+3 \choose 5}. \end{equation\*}
1.5: Stars and Bars
1
A multiset is a collection of objects, just like a set, but can contain an object more than once (the order of the elements still doesn't matter). For example, \\\\1,1, 2, 5, 5, 7\\\\ is a multiset of size 6.
1. How many *sets* of size 5 can be made using the 10 numeric digits 0 through 9?
2. How many *multi*sets of size 5 can be made using the 10 numeric digits 0 through 9?
Answer
1. \\{10\choose 5}\\ sets. We must select 5 of the 10 digits to put in the set.
2. Use stars and bars: each star represents one of the 5 elements of the set, each bar represents a switch between digits. So there are 5 stars and 9 bars, giving us \\{14 \choose 9}\\ sets.
2
Each of the counting problems below can be solved with stars and bars. For each, say what outcome the diagram
\begin{equation\*} \*\*\*\|\*\|\|\*\*\| \end{equation\*}
represents, if there are the correct number of stars and bars for the problem. Otherwise, say why the diagram does not represent any outcome, and what a correct diagram would look like.
1. How many ways are there to select a handful of 6 jellybeans from a jar that contains 5 different flavors?
2. How many ways can you distribute 5 identical lollipops to 6 kids?
3. How many 6-letter words can you make using the 5 vowels?
4. How many solutions are there to the equation \\x_1 + x_2 + x_3 + x_4 = 6\text{.}\\
Answer
1. You take 3 strawberry, 1 lime, 0 licorice, 2 blueberry and 0 bubblegum.
2. This is backwards. We don't want the stars to represent the kids because the kids are not identical, but the stars are. Instead we should use 5 stars (for the lollipops) and use 5 bars to switch between the 6 kids. For example, \begin{equation\*} \*\*\|\|\*\*\*\|\|\| \end{equation\*} would represent the outcome with the first kid getting 2 lollipops, the third kid getting 3, and the rest of the kids getting none.
3. This is the word AAAEOO.
4. This doesn't represent a solution. Each star should represent one of the 6 units that add up to 6, and the bars should *switch* between the different variables. We have one too many bars. An example of a correct diagram would be \begin{equation\*} \*\|\*\*\|\|\*\*\*, \end{equation\*} representing that \\x_1 = 1\text{,}\\ \\x_2 = 2\text{,}\\ \\x_3 = 0\text{,}\\ and \\x_4 = 3\text{.}\\
3
After gym class you are tasked with putting the 14 identical dodgeballs away into 5 bins.
1. How many ways can you do this if there are no restrictions?
2. How many ways can you do this if each bin must contain at least one dodgeball?
Answer
1. \\{18 \choose 4}\\ ways. Each outcome can be represented by a sequence of 14 stars and 4 bars.
2. \\{13 \choose 4}\\ ways. First put one ball in each bin. This leaves 9 stars and 4 bars.
4
How many integer solutions are there to the equation \\x + y + z = 8\\ for which
1. \\x\text{,}\\ \\y\text{,}\\ and \\z\\ are all positive?
2. \\x\text{,}\\ \\y\text{,}\\ and \\z\\ are all non-negative?
3. \\x\text{,}\\ \\y\text{,}\\ and \\z\\ are all greater than \\-3\text{.}\\
Answer
1. \\{7 \choose 2}\\ solutions. After each variable gets 1 star for free, we are left with 5 stars and 2 bars.
2. \\{10 \choose 2}\\ solutions. We have 8 stars and 2 bars.
3. \\{19 \choose 2}\\ solutions. This problem is equivalent to finding the number of solutions to \\x' + y' + z' = 17\\ where \\x'\text{,}\\ \\y'\\ and \\z'\\ are non-negative. (In fact, we really just do a substitution. Let \\x = x'- 3\text{,}\\ \\y = y' - 3\\ and \\z = z' - 3\$.
5
Using the digits 2 through 8, find the number of different 5-digit numbers such that:
1. Digits cannot be repeated and must be written in increasing order. For example, 23678 is okay, but 32678 is not.
2. Digits *can* be repeated and must be written in *non-decreasing* order. For example, 24448 is okay, but 24484 is not.
Answer
1. There are \\{7 \choose 5}\\ numbers. We simply choose five of the seven digits and once chosen put them in increasing order.
2. This requires stars and bars. Use a star to represent each of the 5 digits in the number, and use their position relative to the bars to say what numeral fills that spot. So we will have 5 stars and 6 bars, giving \\{11 \choose 6}\\ numbers.
6
When playing Yahtzee, you roll five regular 6-sided dice. How many different outcomes are possible from a single roll? The order of the dice does not matter.
7
Your friend tells you she has 7 coins in her hand (just pennies, nickels, dimes and quarters). If you guess how many of each kind of coin she has, she will give them to you. If you guess randomly, what is the probability that you will be correct?
8
How many integer solutions to \\x_1 + x_2 + x_3 + x_4 = 25\\ are there for which \\x_1 \ge 1\text{,}\\ \\x_2 \ge 2\text{,}\\ \\x_3 \ge 3\\ and \\x_4 \ge 4\text{?}\\
9
Solve the three counting problems below. Then say why it makes sense that they all have the same answer. That is, say how you can interpret them as each other.
1. How many ways are there to distribute 8 cookies to 3 kids?
2. How many solutions in non-negative integers are there to \\x+y+z = 8\text{?}\\
3. How many different packs of 8 crayons can you make using crayons that come in red, blue and yellow?
10
Consider functions \\f:\\1,2,3,4,5\\ \to \\0,1,2,\ldots,9\\\text{.}\\
1. How many of these functions are strictly increasing? Explain. (A function is strictly increasing provided if \\a \lt b\text{,}\\ then \\f(a) \lt f(b)\text{.}\$
2. How many of the functions are non-decreasing? Explain. (A function is non-decreasing provided if \\a \lt b\text{,}\\ then \\f(a) \le f(b)\text{.}\$
11
*Conic*, your favorite math themed fast food drive-in offers 20 flavors which can be added to your soda. You have enough money to buy a large soda with 4 added flavors. How many different soda concoctions can you order if:
1. You refuse to use any of the flavors more than once?
2. You refuse repeats but care about the order the flavors are added?
3. You allow yourself multiple shots of the same flavor?
4. You allow yourself multiple shots, and care about the order the flavors are added?
Answer
1. \\{20 \choose 4}\\ sodas (order does not matter and repeats are not allowed).
2. \\P(20, 4) = 20\cdot 19\cdot 18 \cdot 17\\ sodas (order matters and repeats are not allowed).
3. \\{23 \choose 19}\\ sodas (order does not matter and repeats are allowed; 4 stars and 19 bars).
4. \\20^4\\ sodas (order matters and repeats are allowed; 20 choices 4 times).
1.6: Advanced Counting Using PIE
1
The dollar menu at your favorite tax-free fast food restaurant has 7 items. You have \$10 to spend. How many different meals can you buy if you spend all your money and:
1. Purchase at least one of each item.
2. Possibly skip some items.
3. Don't get more than 2 of any particular item.
Answer a
\\9 \choose 6\\ meals.
Answer b
\\16 \choose 6\\ meals.
Answer c
\\{16 \choose 6} - \left$${7 \choose 1}{13 \choose 6} - {7 \choose 2}{10 \choose 6} + {7 \choose 3}{7 \choose 6}\right$$\\ me als. Use PIE to subtract all the meals in which you get 3 or more of a particular item.
2
After a late night of math studying, you and your friends decide to go to your favorite tax-free fast food Mexican restaurant, *Burrito Chime*. You decide to order off of the dollar menu, which has 7 items. Your group has \$16 to spend (and will spend all of it).
1. How many different orders are possible? Explain. (The *order* in which the order is placed does not matter - just which and how many of each item that is ordered.)
2. How many different orders are possible if you want to get at least one of each item? Explain.
3. How many different orders are possible if you don't get more than 4 of any one item? Explain.
3
After another gym class you are tasked with putting the 14 identical dodgeballs away into 5 bins. This time, no bin can hold more than 6 balls. How many ways can you clean up?
Solution
\\{18 \choose 4} - \left$$ {5 \choose 1}{11 \choose 4} - {5 \choose 2}{4 \choose 4}\right$$\text{.}\\ Subtract all the distributions for which one or more bins contain 7 or more balls.
4
Consider the equation \\x_1 + x_2 + x_3 + x_4 = 15\text{.}\\ How many solutions are there with \\2 \le x_i \le 5\\ for all \\i \in \\1,2,3,4\\\text{?}\\
Solution
The easiest way to solve this is to instead count the solutions to \\y_1 + y_2 + y_3 + y_4 = 7\\ with \\0 \le y_i \le 3\text{.}\\ By taking \\x_i = y_i+2\text{,}\\ each solution to this new equation corresponds to exactly one solution to the original equation.
Now all the ways to distribute the 7 units to the four \\y_i\\ variables can be found using stars and bars, specifically 7 stars and 3 bars, so \\{10 \choose 3}\\ ways. But this includes the ways that one or more \\y_i\\ variables can be assigned more than 3 units. So subtract, using PIE. We get
\begin{equation\*} {10 \choose 3} - {4\choose 1} {6 \choose 3}. \end{equation\*}
The \\{4 \choose 1}\\ counts the number of ways to pick one variable to be over-assigned, the \\{6 \choose 3}\\ is the number of ways to assign the remaining 3 units to the 4 variables. Note that this is the final answer because it is not possible to have two variables both get 4 units.
5
Suppose you planned on giving 7 gold stars to some of the 13 star students in your class. Each student can receive at most one star. How many ways can you do this? Use PIE, and also an easier method, and compare your results.
6
Based on the previous question, give a combinatorial proof for the identity:
\begin{equation\*} {n \choose k} = {n+k-1 \choose k} - \sum\_{j=1}^n (-1)^{j+1}{n \choose j}{n+k-(2j+1) \choose k}. \end{equation\*}
7
Illustrate how the counting of derangements works by writing all permutations of \\\\1,2,3,4\\\\ and the crossing out those which are not derangements. Keep track of the permutations you cross out more than once, using PIE.
Solution
The 9 derangements are: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.
8
How many permutations of \\\\1,2,3,4,5\\\\ leave exactly 1 element fixed?
Solution
First pick one of the five elements to be fixed. For each such choice, derange the remaining four, using the standard advanced PIE formula. We get \\{5 \choose 1}\left( 4! - \left$${4 \choose 1}3! - {4 \choose 2}2! + {4 \choose 3} 1! - {4 \choose 4} 0!\right$$ \right)\\ permutations.
9
Ten ladies of a certain age drop off their red hats at the hat check of a museum. As they are leaving, the hat check attendant gives the hats back randomly. In how many ways can exactly six of the ladies receive their own hat (and the other four not)? Explain.
10
The Grinch sneaks into a room with 6 Christmas presents to 6 different people. He proceeds to switch the name-labels on the presents. How many ways could he do this if:
1. No present is allowed to end up with its original label? Explain what each term in your answer represents.
2. Exactly 2 presents keep their original labels? Explain.
3. Exactly 5 presents keep their original labels? Explain.
11
Consider functions \\f: \\1,2,3,4\\ \to \\a,b,c,d,e,f\\\text{.}\\ How many functions have the property that \\f(1) \ne a\\ or \\f(2) \ne b\text{,}\\ or both?
Solution
There are \\5 \cdot 6^3\\ functions for which \\f(1) \ne a\\ and another \\5 \cdot 6^3\\ functions for which \\f(2) \ne b\text{.}\\ There are \\5^2 \cdot 6^2\\ functions for which both \\f(1) \ne a\\ and \\f(2) \ne b\text{.}\\ So the total number of functions for which \\f(1) \ne a\\ or \\f(2) \ne b\\ or both is
\begin{equation\*} 5 \cdot 6^3 + 5 \cdot 6^3 - 5^2 \cdot 6^2 = 1260. \end{equation\*}
12
Consider sets \\A\\ and \\B\\ with \\\|A\| = 10\\ and \\\|B\| = 5\text{.}\\ How many functions \\f: A \to B\\ are surjective?
Solution
\\5^{10} - \left$${5 \choose 1}4^{10} - {5 \choose 2}3^{10} + {5 \choose 3}2^{10} - {5 \choose 4}1^{10}\right$$\\ functions. The \\5^{10}\\ is all the functions from \\A\\ to \\B\text{.}\\ We subtract those that aren't surjective. Pick one of the five elements in \\B\\ to not have in the range (in \\{5 \choose 1}\\ ways) and count all those functions (\\4^{10}\$. But this overcounts the functions where two elements from \\B\\ are excluded from the range, so subtract those. And so on, using PIE.
13
Let \\A = \\1,2,3,4,5\\\text{.}\\ How many injective functions \\f:A \to A\\ have the property that for each \\x \in A\text{,}\\ \\f(x) \ne x\text{?}\\
14
Let \\d_n\\ be the number of derangements of \\n\\ objects. For example, using the techniques of this section, we find
\begin{equation\*} d_3 = 3!-\left({3 \choose 1}2! - {3 \choose 2}1! + {3 \choose 3}0! \right) \end{equation\*}
We can use the formula for \\{n \choose k}\\ to write this all in terms of factorials. After simplifying, for \\d_3\\ we would get
\begin{equation\*} d_3 = 3!\left(1 - \frac{1}{1} + \frac{1}{2} - \frac{1}{6} \right) \end{equation\*}
Generalize this to find a nicer formula for \\d_n\text{.}\\ Bonus: For large \\n\text{,}\\ approximately what fraction of all permutations are derangements? Use your knowledge of Taylor series from calculus.
---
1_S_3A_Counting__Summary_
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/1%3A_Counting/1.S%3A_Counting_(Summary)
Skip to main content
Investigate!
Suppose you have a huge box of animal crackers containing plenty of each of 10 different animals. For the counting questions below, carefully examine their similarities and differences, and then give an answer. The answers are all one of the following:
| | | | |
|-------------------|--------------------------|----------------|---------------------|
| \\P(10,6)\qquad\\ | \\{10 \choose 6}\qquad\\ | \\10^6\qquad\\ | \\{15 \choose 9}.\\ |
1. How many animal parades containing 6 crackers can you line up?
2. How many animal parades of 6 crackers can you line up so that the animals appear in alphabetical order?
3. How many ways could you line up 6 different animals in alphabetical order?
4. How many ways could you line up 6 different animals if they can come in any order?
5. How many ways could you give 6 children one animal cracker each?
6. How many ways could you give 6 children one animal cracker each so that no two kids get the same animal?
7. How many ways could you give out 6 giraffes to 10 kids?
8. Write a question about giving animal crackers to kids that has the answer \\{10\choose 6}\text{.}\\
With all the different counting techniques we have mastered in this last chapter, it might be difficult to know when to apply which technique. Indeed, it is very easy to get mixed up and use the wrong counting method for a given problem. You get better with practice. As you practice you start to notice some trends that can help you distinguish between types of counting problems. Here are some suggestions that you might find helpful when deciding how to tackle a counting problem and checking whether your solution is correct.
- Remember that you are counting the number of items in some *list of outcomes*. Write down part of this list. Write down an element in the middle of the list – how are you deciding whether your element really is in the list. Could you get this element more than once using your proposed answer?
- If generating an element on the list involves selecting something (for example, picking a letter or picking a position to put a letter, etc), can the things you select be repeated? Remember, permutations and combinations select objects from a set *without* repeats.
- Does order matter? Be careful here and be sure you know what your answer really means. We usually say that order matters when you get different outcomes when the same objects are selected in different orders. Combinations and “Stars & Bars” are used when order *does not* matter.
- There are four possibilities when it comes to order and repeats. If order matters and repeats are allowed, the answer will look like \\n^k\text{.}\\ If order matters and repeats are not allowed, we have \\P(n,k)\text{.}\\ If order doesn't matter and repeats are allowed, use stars and bars. If order doesn't matter and repeats are not allowed, use \\{n\choose k}\text{.}\\ But be careful: this only applies when you are selecting things, and you should make sure you know exactly what you are selecting before determining which case you are in.
- Think about how you would represent your counting problem in terms of sets or functions. We know how to count different sorts of sets and different types of functions.
- As we saw with combinatorial proofs, you can often solve a counting problem in more than one way. Do that, and compare your numerical answers. If they don't match, something is amiss.
While we have covered many counting techniques, we have really only scratched the surface of the large subject of *enumerative combinatorics*. There are mathematicians doing original research in this area even as you read this. Counting can be really hard.
In the next chapter, we will approach counting questions from a very different direction, and in doing so, answer infinitely many counting questions at the same time. We will create *sequences* of answers to related questions.
Chapter Review
1
You have 9 presents to give to your 4 kids. How many ways can this be done if:
1. The presents are identical, and each kid gets at least one present?
2. The presents are identical, and some kids might get no presents?
3. The presents are unique, and some kids might get no presents?
4. The presents are unique and each kid gets at least one present?
Answer
1. \\{8 \choose 3}\\ ways, after giving one present to each kid, you are left with 5 presents (stars) which need to be divide among the 4 kids (giving 3 bars).
2. \\{12 \choose 3}\\ ways. You have 9 stars and 3 bars.
3. \\4^9\text{.}\\ You have 4 choices for whom to give each present. This is like making a function from the set of presents to the set of kids.
4. \\4^9 - \left$${4 \choose 1}3^9 - {4\choose 2}2^9 + {4 \choose 3}1^9 \right$$\\ ways. Now the function from the set of presents to the set of kids must be surjective.
2
For each of the following counting problems, say whether the answer is \\{10\choose 4}\text{,}\\ \\P(10,4)\text{,}\\ or neither. If you answer is “neither,” say what the answer should be instead.
1. How many shortest lattice paths are there from \$0,0)\\ to \$10,4)\text{?}\\
2. If you have 10 bow ties, and you want to select 4 of them for next week, how many choices do you have?
3. Suppose you have 10 bow ties and you will wear one on each of the next 4 days. How many choices do you have?
4. If you want to wear 4 of your 10 bow ties next week (Monday through Sunday), how many ways can this be accomplished?
5. Out of a group of 10 classmates, how many ways can you rank your top 4 friends?
6. If 10 students come to their professor's office but only 4 can fit at a time, how different combinations of 4 students can see the prof first?
7. How many 4 letter words can be made from the first 10 letters of the alphabet?
8. How many ways can you make the word “cake” from the first 10 letters of the alphabet?
9. How many ways are there to distribute 10 apples among 4 children?
10. If you have 10 kids (and live in a shoe) and 4 types of cereal, how many ways can your kids eat breakfast?
11. How many ways can you arrange exactly 4 ones in a string of 10 binary digits?
12. You want to select 4 single digit numbers as your lotto picks. How many choices do you have?
13. 10 kids want ice-cream. You have 4 varieties. How many ways are there to give the kids as much ice-cream as they want?
14. How many 1-1 functions are there from \\\\1,2,\ldots, 10\\\\ to \\\\a,b,c,d\\\text{?}\\
15. How many surjective functions are there from \\\\1,2,\ldots, 10\\\\ to \\\\a,b,c,d\\\text{?}\\
16. Each of your 10 bow ties match 4 pairs of suspenders. How many outfits can you make?
17. After the party, the 10 kids each choose one of 4 party-favors. How many outcomes?
18. How many 6-elements subsets are there of the set \\\\1,2,\ldots, 10\\\\
19. How many ways can you split up 11 kids into 5 teams?
20. How many solutions are there to \\x_1 + x_2 + \cdots + x_5 = 6\\ where each \\x_i\\ is non-negative?
21. Your band goes on tour. There are 10 cities within driving distance, but only enough time to play 4 of them. How many choices do you have for the cities on your tour?
22. In how many different ways can you play the 4 cities you choose?
23. Out of the 10 breakfast cereals available, you want to have 4 bowls. How many ways can you do this?
24. There are 10 types of cookies available. You want to make a 4 cookie stack. How many different stacks can you make?
25. From your home at (0,0) you want to go to either the donut shop at (5,4) or the one at (3,6). How many paths could you take?
26. How many 10-digit numbers do not contain a sub-string of 4 repeated digits?
Answer
1. Neither. \\{14 \choose 4}\\ paths.
2. \\{10\choose 4}\\ bow ties. \\P(10,4)\text{,}\\ since order is important.
3. Neither. Assuming you will wear each of the 4 ties on just 4 of the 7 days, without repeats: \\{10\choose 4}P(7,4)\text{.}\\
4. \\P(10,4)\text{.}\\ \\{10\choose 4}\text{.}\\
5. Neither. Since you could repeat letters: \\10^4\text{.}\\ If no repeats are allowed, it would be \\P(10,4)\text{.}\\
6. Neither. Actually, “k” is the 11th letter of the alphabet, so the answer is 0. If “k” was among the first 10 letters, there would only be 1 way - write it down.
7. Neither. Either \\{9\choose 3}\\ (if every kid gets an apple) or \\{13 \choose 3}\\ (if appleless kids are allowed).
8. Neither. Note that this could not be \\{10 \choose 4}\\ since the 10 things and 4 things are from different groups. \\4^{10}\text{.}\\
9. \\{10 \choose 4}\\ - don't be fooled by the “arrange” in there - you are picking 4 out of 10 *spots* to put the 1's. \\{10 \choose 4}\\ (assuming order is irrelevant).
10. Neither. \\16^{10}\\ (each kid chooses yes or no to 4 varieties).
11. Neither. 0.
12. Neither. \\4^{10} - $${4\choose 1}3^{10} - {4\choose 2}2^{10} + {4 \choose 3}1^{10}$$\text{.}\\
13. Neither. \\10\cdot 4\text{.}\\
14. Neither. \\4^{10}\text{.}\\
15. \\{10 \choose 4}\\ (which is the same as \\{10 \choose 6}\$.
16. Neither. If all the kids were identical, and you wanted no empty teams, it would be \\{10 \choose 4}\text{.}\\ Instead, this will be the same as the number of surjective functions from a set of size 11 to a set of size 5.
17. \\{10 \choose 4}\text{.}\\ \\{10 \choose 4}\text{.}\\
18. Neither. \\4!\text{.}\\
19. Neither. It's \\{10 \choose 4}\\ if you won't repeat any choices. If repetition is allowed, then this becomes \\x_1 + x_2 + \cdots +x\_{10} = 4\text{,}\\ which has \\{13 \choose 9}\\ solutions in non-negative integers.
20. Neither. Since repetition of cookie type is allowed, the answer is \\10^4\text{.}\\ Without repetition, you would have \\P(10,4)\text{.}\\
21. \\{10 \choose 4}\\ since that is equal to \\{9 \choose 4} + {9 \choose 3}\text{.}\\
22. Neither. It will be a complicated (possibly PIE) counting problem.
3
Recall, you own 3 regular ties and 5 bow ties. You realize that it would be okay to wear more than two ties to your clown college interview.
1. You must select some of your ties to wear. Everything is okay, from no ties up to all ties. How many choices do you have?
2. If you want to wear at least one regular tie and one bow tie, but are willing to wear up to all your ties, how many choices do you have for which ties to wear?
3. How many choices do you have if you wear exactly 2 of the 3 regular ties and 3 of the 5 bow ties?
4. Once you have selected 2 regular and 3 bow ties, in how many orders could you put the ties on, assuming you must have one of the three bow ties on top?
Answer
1. \\2^8 = 256\\ choices. You have two choices for each tie: wear it or don't.
2. You have 7 choices for regular ties (the 8 choices less the “no regular tie” option) and 31 choices for bow ties (32 total minus the “no bow tie” option). Thus total you have \\7 \cdot 31 = 217\\ choices.
3. \\{3\choose 2}{5\choose 3} = 30\\ choices.
4. Select one of the 3 bow ties to go on top. There are then 4 choices for the next tie, 3 for the tie after that, and so on. Thus \\3\cdot 4! = 72\\ choices.
4
Give a counting question where the answer is \\8\cdot 3 \cdot 3 \cdot 5\text{.}\\ Give another question where the answer is \\8 + 3 + 3 + 5\text{.}\\
Answer
You own 8 purple bow ties, 3 red bow ties, 3 blue bow ties and 5 green bow ties. How many ways can you select one of each color bow tie to take with you on a trip? \\8 \cdot 3 \cdot 3 \cdot 5\\ ways. How many choices do you have for a single bow tie to wear tomorrow? \\8 + 3 + 3 + 5\\ choices.
5
Consider five digit numbers \\\alpha = a_1a_2a_3a_4a_5\text{,}\\ with each digit from the set \\\\1,2,3,4\\\text{.}\\
1. How many such numbers are there?
2. How many such numbers are there for which the *sum* of the digits is even?
3. How many such numbers contain more even digits than odd digits?
Answer
1. \\4^5\\ numbers.
2. \\4^4\cdot 2\\ numbers (choose any digits for the first four digits - then pick either an even or an odd last digit to make the sum even).
3. We need 3 or more even digits. 3 even digits: \\{5 \choose 3}2^3 2^2\text{.}\\ 4 even digits: \\{5 \choose 4}2^4 2\text{.}\\ 5 even digits: \\{5 \choose 5}2^5\text{.}\\ So all together: \\{5 \choose 3}2^3 2^2 + {5 \choose 4}2^4 2 + {5 \choose 5}2^5\\ numbers.
6
In a recent small survey of airline passengers, 25 said they had flown American in the last year, 30 had flown Jet Blue, and 20 had flown Continental. Of those, 10 reported they had flown on American and Jet Blue, 12 had flown on Jet Blue and Continental, and 7 had flown on American and Continental. 5 passengers had flown on all three airlines.
How many passengers were surveyed? (Assume the results above make up the entire survey.)
Answer
51 passengers.
7
Recall, by \\8\\-bit strings, we mean strings of binary digits, of length 8.
1. How many \\8\\-bit strings are there total?
2. How many \\8\\-bit strings have weight 5?
3. How many subsets of the set \\\\a,b,c,d,e,f,g,h\\\\ contain exactly 5 elements?
4. Explain why your answers to parts (b) and (c) are the same. Why are these questions equivalent?
Answer
1. \\2^8\\ strings.
2. \\{8 \choose 5}\\ strings.
3. \\{8 \choose 5}\\ strings.
4. There is a bijection between subsets and bit strings: a 1 means that element in is the subset, a 0 means that element is not in the subset. To get a subset of an 8 element set we have a 8-bit string. To make sure the subset contains exactly 5 elements, there must be 5 1's, so the weight must be 5.
8
What is the coefficient of \\x^{10}\\ in the expansion of \$x+1)^{13} + x^2(x+1)^{17}\text{?}\\
Answer
\\{13 \choose 10} + {17 \choose 8}\text{.}\\
9
How many 8-letter words contain exactly 5 vowels (a,e,i,o,u)? What if repeated letters were not allowed?
Answer
With repeated letters allowed: \\{8 \choose 5}5^5 21^3\\ words. Without repeats: \\{8 \choose 5}5! P(21, 3)\\ words.
10
For each of the following, find the number of shortest lattice paths from \$0,0)\\ to \$8,8)\\ which:
1. pass through the point \$2,3)\text{.}\\
2. avoid (do not pass through) the point \$7,5)\text{.}\\
3. either pass through \$2,3)\\ or \$5,7)\\ (or both).
Answer
1. \\{5 \choose 2}{11 \choose 6}\\ paths.
2. \\{16 \choose 8} - {12 \choose 7}{4 \choose 1}\\ paths.
3. \\{5 \choose 2}{11 \choose 6} + {12 \choose 5}{4 \choose 3} - {5 \choose 2}{7 \choose 3}{4 \choose 3}\\ paths.
11
You live in Grid-Town on the corner of 2nd and 3rd, and work in a building on the corner of 10th and 13th. How many routes are there which take you from home to work and then back home, but by a different route?
Answer
\\{18 \choose 8}\left({18 \choose 8} - 1\right)\\ routes.
12
How many 10-bit strings start with \\111\\ or end with \\101\\ or both?
Answer
\\2^7 + 2^7 - 2^4\\ strings (using PIE).
13
How many 10-bit strings of weight 6 start with \\111\\ or end with \\101\\ or both?
Answer
\\{7 \choose 3} + {7 \choose 4} - {4 \choose 1}\\ strings.
14
How many 6 letter words made from the letters \\a,b,c,d,e,f\\ without repeats do not contain the sub-word “bad” in (a) consecutive letters? or (b) not-necessarily consecutive letters (but in order)?
Answer
$a$ \\6! - 4\cdot 3!\\ words. (b) \\6! - {6 \choose 3}3!\\ words.
15
Explain using lattice paths why \\\sum\_{k=0}^n {n \choose k} = 2^n\text{.}\\
Answer
\\2^n\\ is the number of lattice paths which have length \\n\text{,}\\ since for each step you can go up or right. Such a path would end along the line \\x + y = n\text{.}\\ So you will end at \$0,n)\text{,}\\ or \$1,n-1)\\ or \$2, n-2)\\ or … or \$n,0)\text{.}\\ Counting the paths to each of these points separately, give \\{n \choose 0}\text{,}\\ \\{n \choose 1}\text{,}\\ \\{n \choose 2}\text{,}\\ …, \\{n \choose n}\\ (each time choosing which of the \\n\\ steps to be to the right). These two methods count the same quantity, so are equal.
16
Suppose you have 20 one-dollar bills to give out as prizes to your top 5 discrete math students. How many ways can you do this if:
1. Each of the 5 students gets at least 1 dollar?
2. Some students might get nothing?
3. Each student gets at least 1 dollar but no more than 7 dollars?
Hint
Stars and bars.
Answer
1. \\{19 \choose 4}\\ ways.
2. \\{24 \choose 4}\\ ways.
3. \\{19 \choose 4} - \left$${5 \choose 1}{12 \choose 4} - {5 \choose 2}{5 \choose 4} \right$$\\ ways.
17
How many functions \\f: \\1,2,3,4,5\\ \to \\a,b,c,d,e\\\\ are there satisfying:
1. \\f(1) = a\\ or \\f(2) = b\\ (or both)?
2. \\f(1) \ne a\\ or \\f(2) \ne b\\ (or both)?
3. \\f(1) \ne a\\ *and* \\f(2) \ne b\text{,}\\ and \\f\\ is injective?
4. \\f\\ is surjective, but \\f(1) \ne a\text{,}\\ \\f(2) \ne b\text{,}\\ \\f(3) \ne c\text{,}\\ \\f(4) \ne d\\ and \\f(5) \ne e\text{?}\\
Answer
1. \\5^4 + 5^4 - 5^3\\ functions.
2. \\4\cdot 5^4 + 5 \cdot 4 \cdot 5^3 - 4 \cdot 4 \cdot 5^3\\ functions.
3. \\5! - \left$$ 4! + 4! - 3! \right$$\\ functions. Note we use factorials instead of powers because we are looking for injective functions.
4. Note that being surjective here is the same as being injective, so we can start with all \\5!\\ injective functions and subtract those which have one or more “fixed point”. We get \\5! - \left$${5 \choose 1}4! - {5 \choose 2}3! + {5 \choose 3}2! - {5 \choose 4}1! + {5 \choose 5} 0!\right$$\\ functions.
18
How many functions map \\\\1,2,3,4,5,6\\\\ *onto* \\\\a,b,c,d\\\\ (i.e., how many *surjections* are there)?
Answer
\\4^6 - \left$${4 \choose 1}3^6 - {4 \choose 2}2^6 + {4 \choose 3} 1^6 \right$$\text{.}\\
19
To thank your math professor for doing such an amazing job all semester, you decide to bake Oscar cookies. You know how to make 10 different types of cookies.
1. If you want to give your professor 4 different types of cookies, how many different combinations of cookie type can you select? Explain your answer.
2. To keep things interesting, you decide to make a different number of each type of cookie. If again you want to select 4 cookie types, how many ways can you select the cookie types and decide for which there will be the most, second most, etc. Explain your answer.
3. You change your mind again. This time you decide you will make a total of 12 cookies. Each cookie could be any one of the 10 types of cookies you know how to bake (and it's okay if you leave some types out). How many choices do you have? Explain.
4. You realize that the previous plan did not account for presentation. This time, you once again want to make 12 cookies, each one could be any one of the 10 types of cookies. However, now you plan to shape the cookies into the numerals 1, 2, …, 12 (and probably arrange them to make a giant clock, but you haven't decided on that yet). How many choices do you have for which types of cookies to bake into which numerals? Explain.
5. The only flaw with the last plan is that your professor might not get to sample all 10 different varieties of cookies. How many choices do you have for which types of cookies to make into which numerals, given that each type of cookie should be present at least once? Explain.
Answer
1. \\{10 \choose 4}\\ combinations. You need to choose 4 of the 10 cookie types. Order doesn't matter.
2. \\P(10, 4) = 10 \cdot 9 \cdot 8 \cdot 7\\ ways. You are choosing and arranging 4 out of 10 cookies. Order matters now.
3. \\{21 \choose 9}\\ choices. You must switch between cookie type 9 times as you make your 12 cookies. The cookies are the stars, the switches between cookie types are the bars.
4. \\10^{12}\\ choices. You have 10 choices for the “1” cookie, 10 choices for the “2” cookie, and so on.
5. \\10^{12} - \left$${10 \choose 1}9^{12} - {10 \choose 2}8^{12} + \cdots - {10 \choose 10}0^{12} \right$$\\ choices. We must use PIE to remove all the ways in which one or more cookie type is not selected.
20
For which of the parts of the previous problem (Exercise 1.7.19) does it make sense to interpret the counting question as counting some number of functions? Say what the domain and codomain should be, and whether you are counting all functions, injections, surjections, or something else.
Answer
1. You are giving your professor 4 types of cookies coming from 10 different types of cookies. This does not lend itself well to a function interpretation. We *could* say that the domain contains the 4 types you will give your professor and the codomain contains the 10 you can choose from, but then counting injections would be too much (it doesn't matter if you pick type 3 first and type 2 second, or the other way around, just that you pick those two types).
2. We want to consider injective functions from the set \\\\\\most, second most, second least, least\\\\\\ to the set of 10 cookie types. We want injections because we cannot pick the same type of cookie to give most and least of (for example).
3. This is not a good problem to interpret as a function. The problem is that the domain would have to be the 12 cookies you bake, but these elements are indistinguishable (there is not a first cookie, second cookie, etc.).
4. The domain should be the 12 shapes, the codomain the 10 types of cookies. Since we can use the same type for different shapes, we are interested in counting all functions here.
5. Here we insist that each type of cookie be given at least once, so now we are asking for the number of surjections of those functions counted in the previous part.
---
20_3A_Glossary
> 来源: LibreTexts
> 原页: https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Discrete_Mathematics_(Levin)/zz%3A_Back_Matter/20%3A_Glossary
Skip to main content
| Words (or words that have the same definition) | The definition is case sensitive | (Optional) Image to display with the definition $$Not displayed in Glossary, only in pop-up on pages$$ | (Optional) Caption for Image | (Optional) External or Internal Link | (Optional) Source for Definition |
|------------------------------------------------|---------------------------------------|--------------------------------------------------------------------------------------------------------|------------------------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|----------------------------------|
| (Eg. "Genetic, Hereditary, DNA ...") | (Eg. "Relating to genes or heredity") | \![$$(https://libretexts.org/img/LibreTexts/glyphs/bio.png) | The infamous double helix | https://bio.libretexts.org/ | CC-BY-SA; Delmar Larsen |
Example and Directions
| Word(s) | Definition | Image | Caption | Link | Source |
|---------------|---------------------|-------|---------|------|--------|
| Sample Word 1 | Sample Definition 1 | | | | |
Glossary Entries
---