Most of the permutation and combination problems we have seen count choices made without repetition, as when we asked how many rolls of three dice are there in which each die has a different value. The exception was the simplest problem, asking for the total number of outcomes when two or three dice are rolled, a simple application of the multiplication principle. Typical permutation and combination problems can be interpreted in terms of drawing balls from a box, and implicitly or explicitly the rule is that a ball drawn from the box stays out of the box. If instead each ball is returned to the box after recording the draw, we get a problem essentially identical to the general dice problem. For example, if there are six balls, numbered 1–6, and we draw three balls with replacement, the number of possible outcomes is $6^3$. Another version of the problem does not replace the ball after each draw, but allows multiple "identical'' balls to be in the box. For example, if a box contains 18 balls numbered 1–6, three with each number, then the possible outcomes when three balls are drawn and not returned to the box is again $6^3$. If four balls are drawn, however, the problem becomes different.
Another, perhaps more mathematical, way to phrase such problems is to introduce the idea of a multiset. A multiset is like a set, except that elements may appear more than once. If $\{a,b\}$ and $\{b,c\}$ are ordinary sets, we say that the union $\{a,b\}\cup\{b,c\}$ is $\{a,b,c\}$, not $\{a,b,b,c\}$. If we interpret these as multisets, however, we do write $\{a,b,b,c\}$ and consider this to be different than $\{a,b,c\}$. To distinguish multisets from sets, and to shorten the expression in most cases, we use a repetition number with each element. For example, we will write $\{a,b,b,c\}$ as $\{1\cdot a,2\cdot b,1\cdot c\}$. By writing $\{1\cdot a,1\cdot b,1\cdot c\}$ we emphasize that this is a multiset, even though no element appears more than once. We also allow elements to be included an infinite number of times, indicated with $\infty$ for the repetition number, like $\{\infty\cdot a, 5\cdot b, 3\cdot c\}$.
Generally speaking, problems in which repetition numbers are infinite are easier than those involving finite repetition numbers. Given a multiset $A=\{\infty\cdot a_1,\infty\cdot a_2,\ldots,\infty\cdot a_n\}$, how many permutations of the elements of length $k$ are there? That is, how many sequences $x_1,x_2,\ldots,x_k$ can be formed? This is easy: the answer is $n^k$.
Now consider combinations of a multiset, that is, submultisets: Given a multiset, how many submultisets of a given size does it have? We say that a multiset $A$ is a submultiset of $B$ if the repetition number of every element of $A$ is less than or equal to its repetition number in $B$. For example, $\{20\cdot a, 5\cdot b, 1\cdot c\}$ is a submultiset of $\{\infty\cdot a, 5\cdot b, 3\cdot c\}$. A multiset is finite if it contains only a finite number of distinct elements, and the repetition numbers are all finite. Suppose again that $A=\{\infty\cdot a_1,\infty\cdot a_2,\ldots,\infty\cdot a_n\}$; how many finite submultisets does it have of size $k$? This at first seems quite difficult, but put in the proper form it turns out to be a familiar problem. Imagine that we have $k+n-1$ "blank spaces'', like this:
Now we place $n-1$ markers in some of these spots:
This uniquely identifies a submultiset: fill all blanks up to the first $\land$ with $a_1$, up to the second with $a_2$, and so on:
So this pattern corresponds to the multiset $\{1\cdot a_2,3\cdot a_3,\ldots, 1\cdot a_n\}$. Filling in the markers $\land$ in all possible ways produces all possible submultisets of size $k$, so there are $k+n-1\choose n-1$ such submultisets. Note that this is the same as $k+n-1\choose k$; the hard part in practice is remembering that the $-1$ goes with the $n$, not the $k$.
$$\bullet\quad\bullet\quad\bullet$$
Summarizing the high points so far: The number of permutations of $n$ things taken $k$ at a time without replacement is $\ds P(n,k)=n!/(n-k)!$; the number of permutations of $n$ things taken $k$ at a time with replacement is $\ds n^k$. The number of combinations of $n$ things taken $k$ at a time without replacement is ${n\choose k}$; the number of combinations of $n$ things taken $k$ at a time with replacement is ${k+n-1 \choose k}$.
$$\bullet\quad\bullet\quad\bullet$$
If $A=\{m_1\cdot a_1, m_2\cdot a_2,\ldots,m_n\cdot a_n\}$, similar questions can be quite hard. Here is an easier special case: How many permutations of the multiset $A$ are there? That is, how many sequences consist of $m_1$ copies of $a_1$, $m_1$ copies of $a_2$, and so on? This problem succumbs to overcounting: suppose to begin with that we can distinguish among the different copies of each $a_i$; they might be colored differently for example: a red $a_1$, a blue $a_1$, and so on. Then we have an ordinary set with $M=\sum_{i=1}^n m_i$ elements and $M!$ permutations. Now if we ignore the colors, so that all copies of $a_i$ look the same, we find that we have overcounted the desired permutations. Permutations with, say, the $a_1$ items in the same positions all look the same once we ignore the colors of the $a_1$s. How many of the original permutations have this property? $m_1!$ permutations will appear identical once we ignore the colors of the $a_1$ items, since there are $m_1!$ permutations of the colored $a_1$s in a given $m_1$ positions. So after throwing out duplicates, the number of remaining permutations is $M!/m_1!$ (assuming the other $a_i$ are still distinguishable). Then the same argument applies to the $a_2$s: there are $m_2!$ copies of each permutation once we ignore the colors of the $a_2$s, so there are $\ds {M!\over m_1!\,m_2!}$ distinct permutations. Continuing in this way, we see that the number of distinct permutations once all colors are ignored is $${M!\over m_1!\,m_2!\cdots m_n!}.$$ This is frequently written $${M\choose m_1\;\;m_2\;\ldots\; m_n},$$ called a multinomial coefficient. Here the second row has $n$ separate entries, not a single product entry. Note that if $n=2$ this is
This is easy to see combinatorially: given $\{m_1\cdot a_1, m_2\cdot a_2\}$ we can form a permutation by choosing the $m_1$ places that will be occupied by $a_1$, filling in the remaining $m_2$ places with $a_2$. The number of permutations is the number of ways to choose the $m_1$ locations, which is $M\choose m_1$.
Example 1.5.1 How many solutions does $\ds x_1+x_2+x_3+x_4=20$ have in non-negative integers? That is, how many 4-tuples $(m_1,m_2,m_3,m_4)$ of non-negative integers are solutions to the equation? We have actually solved this problem: How many submultisets of size 20 are there of the multiset $\{\infty\cdot a_1,\infty\cdot a_2,\infty\cdot a_3,\infty\cdot a_4\}$? A submultiset of size 20 is of the form $\{m_1\cdot a_1,m_2\cdot a_2,m_3\cdot a_3,m_4\cdot a_4\}$ where $\sum m_i=20$, and these are in 1–1 correspondence with the set of 4-tuples $(m_1,m_2,m_3,m_4)$ of non-negative integers such that $\sum m_i=20$. Thus, the number of solutions is $20+4-1\choose 20$. This reasoning applies in general: the number of solutions to $$\sum_{i=1}^n x_i = k$$ is $${k+n-1\choose k}.$$ $\square$
This immediately suggests some generalizations: instead of the total number of solutions, we might want the number of solutions with the variables $x_i$ in certain ranges, that is, we might require that $m_i\le x_i\le M_i$ for some lower and upper bounds $m_i$ and $M_i$.
Finite upper bounds can be difficult to deal with; if we require that $0\le x_i\le M_i$, this is the same as counting the submultisets of $\{M_1\cdot a_1,M_2\cdot a_2,\ldots,M_n\cdot a_n\}$. Lower bounds are easier to deal with.
Example 1.5.2 Find the number of solutions to $\ds x_1+x_2+x_3+x_4=20$ with $x_1\ge 0$, $x_2\ge 1$, $x_3\ge 2$, $x_4\ge -1$.
We can transform this to the initial problem in which all lower bounds are 0. The solutions we seek to count are the solutions of this altered equation: $$ x_1+(x_2-1)+(x_3-2)+(x_4+1)=18.$$ If we set $y_1=x_1$, $y_2=x_2-1$, $y_3=x_3-2$, and $y_4=x_4+1$, then $(x_1,x_2,x_3,x_4)$ is a solution to this equation if and only if $(y_1,y_2,y_3,y_4)$ is a solution to $$ y_1+y_2+y_3+y_4=18,$$ and moreover the bounds on the $x_i$ are satisfied if and only if $y_i\ge 0$. Since the number of solutions to the last equation is $18+4-1\choose 18$, this is also the number of solutions to the original equation. $\square$
Exercises 1.5
Ex 1.5.1 Suppose a box contains 18 balls numbered 1–6, three balls with each number. When 4 balls are drawn without replacement, how many outcomes are possible? Do this in two ways: assuming that the order in which the balls are drawn matters, and then assuming that order does not matter.
Ex 1.5.2 How many permutations are there of the letters in Mississippi?
Ex 1.5.3 How many permutations are there of the multiset $\ds\{1\cdot a_1,1\cdot a_2,\ldots,1\cdot a_n\}$?
Ex 1.5.4 Let $M=\sum_{i=1}^n m_i$. If $k_i< 0$ for some $i$, let's say $$ {M\choose k_1\;k_2\;\ldots\; k_n}=0. $$ Prove that $${M\choose m_1\;m_2\;\ldots\; m_n}= \sum_{i=1}^n {M-1\choose m_1\;m_2\;\ldots\;(m_i-1)\;\ldots\; m_n}. $$ Note that when $n=2$ this becomes $${M\choose m_1\;m_2}= {M-1\choose (m_1-1)\;m_2}+{M-1\choose m_1\;(m_2-1)}. $$ As noted above in equation 1.5.1, when $n=2$ we are really seeing ordinary binomial coefficients, and this can be rewritten as $$ {M\choose m_1}={M-1\choose m_1-1}+{M-1\choose m_1}, $$ which of course we already know.
Ex 1.5.5 The Binomial Theorem (1.3.1) can be written $$(x+y)^n=\sum_{i+j=n} {n\choose i\;j}x^i\,y^j,$$ where the sum is over all non-negative integers $i$ and $j$ that sum to $n$. Prove that for $m\ge 2$, $$ (x_1+x_2+\cdots+x_m)^n= \sum {n\choose i_1\;i_2\;\ldots\;i_m}x_1^{i_1}\,x_2^{i_2}\ldots x_m^{i_m}. $$ where the sum is over all $i_1,\ldots,i_m$ such that $i_1+\cdots+i_m=n$.
Ex 1.5.6 Find the number of integer solutions to $$x_1+x_2+x_3+x_4+x_5=50, x_1\ge -3, x_2\ge 0, x_3\ge 4, x_4\ge 2, x_5\ge 12.$$
Ex 1.5.7 You and your spouse each take two gummy vitamins every day. You share a single bottle of 60 vitamins, 30 of one flavor and 30 of another. You each prefer a different flavor, but it seems childish to fish out two of each type (but not to take gummy vitamins). So you just take the first four that fall out and then divide them up according to your preferences. For example, if there are two of each flavor, you and your spouse get the vitamins you prefer, but if three of your preferred flavor come out, you get two of the ones you like and your spouse gets one of each. Of course, you start a new bottle every 15 days. On average, over a 15 day period, how many of the vitamins you take are the flavor you prefer? (From fivethirtyeight.com.)