\documentclass[11pt,twoside]{article}
\usepackage{macros-course-lectures}

%\newcommand{\Ex}{\text{Ex}}
\newcommand{\ball}{$\ \circ \ $}
\newcommand{\str}{$\ \star \ $}

\begin{document}

\onlystudents

\lecture{notes16}{Lecture Notes}{April 4 2000}

\begin{outline}

The last two lectures concerned the number of ways to choose elements
from a finite set.  In particular, we considered the number of ways to
choose $r$ distinct elements where order does not matter
($r$-combinations) and where order does matter ($r$-permutations).  We
introduced binomial coefficients to count combinations.

In this lecture we consider some of the many identities that help us
to work with binomial coefficients.  Then we generalize our notion of
combinations.  We count the number of ways to choose $r$ elements from
a finite set where we are allowed to choose the same element
repeatedly.  Again, we look at both the case where order does not
matter ($r$-combinations with repetition) and where order does matter
($r$-permutations with repetition).


\section{Basic Properties of Binomial Coefficients}

Let's review binomial coefficients.
\begin{definition}
Let $n$ and $r$ be naturals, $0
\leq r \leq n$.  Then
\[
\binom{n}{r} = \frac{n!}{r!(n-r)!}.
\]
\end{definition}
\begin{nooutline}
Special cases: 
\begin{align*}
{n \choose 1} &= n\\
{n \choose 0} &= 1\\
\intertext{%
This last case uses the convention that $0! = 1$, and also coincides
with the permutation model---there is just 1 permutation of no items.
}\\
{n \choose n} &= 1 &\text{(note symmetry with previous)} \\
{n \choose n-1} &= n &\text{(more symmetry).}
\end{align*}
\end{nooutline}

There are   infinitely many interesting  identities involving binomial
coefficients.  You can't  learn them all, but  you can learn the basic
ones and look others up/derive them as  needed.  You can prove them by
algebra, or by  ``thought experiments'' that establish a combinatorial
meaning  for the left  hand side of the  equation (LHS) and right hand
side (RHS) and argue that they are the same.

These identities are important because of how often binomial
coefficients arise in analysis of algorithms (6.046) and probability
(next week).


\begin{theorem}
Suppose $0 \leq r \leq n$. 
Then 
$${n \choose r} = {n \choose n-r}.$$
\end{theorem}

\begin{proof}
\begin{description}
\item[Algebraic:]
$$\frac{n!}{r!(n-r)!} = \frac{n!}{(n-r)!(n-(n-r))!}.$$
\item[Combinatorial thought experiment:] The LHS is the number of ways
  to choose $r$ from $n$.  The RHS is the number of ways to choose
  $n-r$.  Choosing a set of $r$ is equivalent to choosing a set of
  $n-r$ (in other words, there is a bijection between sets of $r$
  elements and sets of $n-r$ elements given by set-complement).  So
  there are just as many ways to choose either.
\end{description}
\end{proof}

The next theorem gives the ratio between successive binomial
coefficients (same $n$, successive $r$):

\begin{theorem}
\label{bin-coeff-2}
Suppose $1 \leq r \leq n$. 
Then 
$${n \choose r} / {n \choose r-1} = (n-r+1)/r.$$
\end{theorem}

\begin{proof}
\begin{align*}
\binom{n}{r} &=
\frac{n!}{r!(n-r)!} \times \frac{(r-1)!(n-(r-1))!}{n!} \\
&= (n-r+1)/r.
\end{align*}
\end{proof}

Note that this ratio is $> 1$, which means the successive coefficients
are increasing, as long as $r < \frac{n+1}{2}$.  Also, the ratio is
$<1$, which means the coefficient are decreasing, when $r >
\frac{n+1}{2}$.  This says that the coefficients increase, then
decrease, \ie, they are {\em unimodal}.  Form a bell-shaped curve:

\begin{nooutline}
\begin{figure}[htbp]
\centerline{\includegraphics[height=2in]{figures/bell}}
\caption{Bell Curve}
\label{fig:bell}
\end{figure}
\end{nooutline}

In fact, the binomial coefficients form a real {\em bell curve}.
These arise on examinations in a natural way.  Suppose that an SAT
test has $n$ questions.  Then the bell curve describes, for every $r$,
the number of ways the student can get exactly $r$ of the questions
right, namely
\[
{n \choose r}.
\]
If we suppose that each student taking the test is doing random
guessing, so equally likely to get each of the $n$ questions right or
wrong, then these coefficients turn out to be proportional to the
number of students that get those numbers of questions right.  (We'll
see this when we do probability.)

Another identity: 

\begin{theorem} 
Suppose $1 \leq r \leq n$. 
Then 
$${n \choose r} = \frac{n}{r} {n-1 \choose r-1}.$$
\end{theorem}

\begin{proof} 
\begin{description}
\item[Algebraic proof:]
\forstudents{
\begin{eqnarray*}
{n \choose r} &= &\frac{n!}{r!(n-r)!}\\
&= &\frac{n}{r}\frac{(n-1)!}{(r-1)!(n-r)!}\\
&= &\frac{n}{r}\frac{(n-1)!}{(r-1)!((n-1)-(r-1))!}\\
&= &\frac{n}{r}{n-1 \choose r-1}
\end{eqnarray*}
}
\item[Combinatorial proof:]
Consider choosing a committee of size $r$ and a leader, from $n$
people. 
One way is to pick the leader first ($n$ ways), then pick the other
$r-1$ committee members from the remainder (${n-1 \choose r-1}$ ways). 
Another way is to pick the $r$ committee members first 
(${n \choose r}$ ways) and then pick a leader from among them ($r$
ways). 
This implies (by product rule) that:
\[
n{n-1 \choose r-1} = {n \choose r} r.
\]
Now divide both sides by $r$.
\end{description}
\end{proof}

Now an important theorem due to Pascal:

\begin{theorem}[Pascal]
Suppose $1 \leq r \leq n-1$. 
Then 
$${n \choose r} = {n-1 \choose r} + {n-1 \choose r-1}.$$
\end{theorem}

This is probably our most important identity, since gives a kind of
recurrence for binomial coefficients.  {\bf Memorize it!}


\begin{proof}
\begin{description}

\item[Algebraic:]
\forstudents{
\begin{eqnarray*}
{n-1 \choose r} + {n-1 \choose r-1} & = & \frac{(n-1)!}{r!(n-1-r)!} +
 \frac{(n-1)!}{(r-1)!(n-r)!} \\
&= &(n-r)\frac{(n-1)!}{r!(n-r)!} + r\frac{(n-1)!}{r!(n-r)!}\\
&= &n\frac{(n-1)!}{r!(n-r)!}\\
&= &\frac{n!}{r!(n-r)!}\\
&= &{n \choose r}
\end{eqnarray*}
}
\item[Combinatorial:]   We use case analysis (a tree diagram) and the
  sum rule.
Let $S = \set{1,\ldots,n}$. 
Let $A$ be the set of $r$-element subsets of $S$. 
Let $B$ be the set of $r$-element subsets of $S$ that contain $1$. 
Let $C$ be the set of $r$-element subsets of $S$ that don't contain $1$. 

Then $A = B \cup C$, and $B$ and $C$ are disjoint. 
So $|A| = |B| + |C|$, by the sum rule. 
But now we can get expressions for $|A|$, $|B|$ and $|C|$ as numbers of
combinations:
\begin{itemize}
\item 
$|A| = {n \choose r}$. 
\item 
$|B| = {n-1 \choose r-1}$. 
This is because $r-1$ other elements must be chosen from the 
$n-1$ elements excluding item 1.
\item 
$|C| = {n-1 \choose r}$. 
This is because $r$ elements must be chosen from the $n-1$ elements
exluding item 1. 
\end{itemize}
So  (by the sum rule)
\[{n \choose r} = |A| = |B| + |C| = {n-1 \choose r-1} + {n-1 \choose
  r}.
\]
\end{description}
\end{proof}

Pascal's theorem has a nice pictorial representation: The row
represents $n$, starting with $0$ in the top row.  Successive elements
in the row represent $r$, starting with $0$ at the left.
\begin{nooutline}
\begin{figure}[htbp]
\centerline{\includegraphics[height=2in]{figures/pascal}}
\caption{Pascal's triangle.}
\label{fig:pascal}
\end{figure}
\end{nooutline}

This triangle has lots of nice properties.  
Experiment with it. 
\Eg, what happens if we add the coefficients in one row?
\begin{theorem}
  Suppose $n$ is any natural number.  Then
\[
\sum_{r=0}^n {n \choose r} = 2^n.
\]
\end{theorem}

\begin{proof} 
\begin{description}

\item[Algebraic:] \forstudent{ This proof demonstrates an induction
    and Pascal's identity.  The proof is by induction on $n$.  Let
    $P(n)$ be:
\[
\sum_{r=0}^n {n \choose r} = 2^n
\]
BASE: $n=0$.
\[
\sum_{r=0}^0 {0 \choose r} = {0 \choose 0} = 1 =  2^0
\]
INDUCTIVE STEP: Assume $P(n)$, show $P(n+1)$, where $n \geq 0$.
\begin{align*}
\sum_{r=0}^{n+1} {n+1 \choose r} & = {n+1 \choose 0} + \sum_{r=1}^{n}{n+1 \choose r} + {n+1 \choose n+1} \\
&= 2 + \sum_{r=1}^n{n+1 \choose r} \\
&= 2 + \sum_{r=1}^n \left({n \choose r} + {n \choose r-1}\right) & \text{ by
Pascal's identity} \\
&= 2 + 2 \sum_{r=1}^{n-1} {n \choose r} + {n \choose 0} + {n \choose n} \\
&= 2 \sum_{r=0}^{n} {n \choose r} \\
&= 2 \cdot 2^n & \text{ by inductive hypothesis}, \\
&= 2^{n+1}.
\end{align*}
}
\item[Combinatorial:] Again, we use case analaysis and the sum rule
  for disjoint unions.  There are $2^n$ different subsets of a set of
  $n$ elements.  Decompose this collection based on the sizes of the
  subsets.  That is, let $A_r$ be the collection of subsets of size
  $r$.  Then the set of all subsets is the disjoint union $\cup_r
  A_r$.  There are ${n\choose r}$ subsets of size $r$, for
  $r=0,1,\ldots,n$.  Hence the theorem follows.
\end{description}
\end{proof}

\begin{theorem}[Vandermonde]
Suppose $0 \leq r \leq m,n$. 
Then 
\[
{m+n \choose r} = \sum_{k=0}^r {m \choose r-k}{n\choose k}
\]
\end{theorem}

This theorem is a bit worrisome: perhaps $r<m+n$ (so the right hand
side makes sense) but $r > m$ (so the left hand side doesn't).  To
avoid this kind of problem, it is useful to generalize the notion of
binomial coefficient a little bit. 
\begin{definition}
If $r > n$, define ${n \choose r}$
to be $0$.  
\end{definition}
This makes some kind of sense informally, because there aren't any
ways to choose more elements than there are in a set!

We can observe that most of the binomial identities are still correct
with this extension.  For example, Pascal's theorem is still true if
$r > n$ (it reduces trivially).  So we will prove Vandermonde's
theorem without the restriction $r \leq m,n$.  This means that some of
the terms in the statement of the theorem could be trivial terms, \eg,
${n \choose k}$ could occur, where $k > n$.  Bit these terms have
value 0, so don't really matter.

\begin{proof}
\begin{description}
\item[Combinatorial:] Again we use case analysis with the sum and
  product rules.  Suppose there are $m$ red balls and $n$ blue balls,
  all distinct.  There are ${m+n \choose r}$ ways to choose $r$ balls
  from the two sets combined.  That's the LHS.  Now decompose this
  collection of choices based on how many of the chosen balls are
  blue.  For any $k$, $0 \leq k \leq r$, there are ${m \choose r-k}$
  ways to choose $r-k$ red balls, and ${n \choose k}$ ways to choose
  $k$ blue balls.  By the product rule, that makes ${m \choose r-k}
  {n\choose k}$ ways to choose $r$ balls such that $k$ of them are
  blue.  Adding up these numbers for all $k$ gives the RHS.
\item[Algebraic:]
Induction using Pascal's identity: 
\forstudents{
Let $P(n)$ be 
\[
\forall m, r, {m+n \choose r} = \sum_{k=0}^r {m \choose r-k}{n\choose k}
\]
BASE: $n =0$.  Then
\[
{m+0 \choose r} = {m \choose r} = \sum_{k=0}^r {m \choose r-k}{0\choose k}.
\]
This latter equation is true because the only value of $k$ for which
the last factor isn't $0$ is $k = 0$. 
Hence $P(0)$ is true.

INDUCTIVE STEP: Assume $P(n)$ is true, show $P(n+1)$.
We have:
\begin{align*}
{m+(n+1) \choose r} & = {m+n \choose r} + {m+n \choose r-1} \quad
\lefteqn{\text{ by Pascal's identity (with new generalization)}} \\
& = \sum_{k=0}^r {m \choose r-k}{n\choose k} 
  + \sum_{k=0}^{r-1} {m \choose r-1-k}{n\choose k} & \text{ by the
inductive hypothesis}\\
& = \sum_{k=0}^r {m \choose r-k}{n\choose k} 
  + \sum_{k=1}^r {m \choose r-k}{n\choose k-1}  &\text{ by change of vars}\\
& =  {m \choose r}{n\choose0} + \sum_{k=1}^r {m \choose r-k}({n\choose k} + {n\choose k-1})  \\
& =  {m \choose r}{n\choose 0} 
  + \sum_{k=1}^r {m \choose r-k}{n+1\choose k}  
& \mbox{ by Pascal's identity}\\ 
& =  {m \choose r}{n+1\choose 0} 
  + \sum_{k=1}^r {m \choose r-k}{n+1\choose k} \\ 
& = \sum_{k=0}^r {m \choose r-k}{n+1\choose k} 
\end{align*}
Hence, $P(n+1)$ is true. So $P(n)$ is true for all $n$.
}
\end{description}
\end{proof}

\section{The Binomial Theorem}

An important theorem gives the coefficients in the expansion of powers
of binomial expressions.  It turns out they are binomial
coefficients---thus the name!  

\subsection{The Theorem}

\begin{theorem}
Suppose $n \in \naturals$. 
Then
$$ (x+y)^n = \sum_{k=0}^n \binom{n}{k}x^ky^{n-k} .$$
\end{theorem}

\begin{example}
$(x+y)^4 = 1x^4+4x^3y+6x^2y^2+4xy^3+1y^4$
\end{example}

\begin{proof}
\begin{description}
\item[Algebraic:] By induction, using Pascal's identity.
\item[Combinatorial:]
Consider the product
\[
(x+y)^n = (x+y)(x+y)(x+y)(x+y)\ldots
\]
This product has $n$ factors.  To expand this product, we generate
individual terms of the sums by selecting (in all possible ways) one
of the two two variables inside each factor to get an $n$-variable
product.  If we select $k$ ``$x$'' variables and $n-k$ ``$y$''
variables, we get a term of the form $x^ky^{n-k}$.  Then we gather all
those terms together.  So how many ways do we get such a term?  Each
$x^ky^{n-k}$ term selects $x$ from $k$ of the factors and $y$ from the
other $n-k$.  So there are $\binom{n}{k}$ ways of choosing which
factors have $x$.
\end{description}
\end{proof}

\subsection{Identities via Binomial Theorem }

The binomial theorem can be used to give slick proofs of some binomial
identities, \eg: 

\begin{theorem}
$$\sum_{k=0}^n \binom{n}{k} = 2^n.$$
\end{theorem}

\begin{proof}
Plug $x = 1$, $y = 1$ into binomial theorem.
\end{proof}

\begin{theorem}
\label{bin-coeff-3}
$$\sum_{k=0}^n (-1)^k\binom{n}{k} = 0.$$
\end{theorem}

\begin{proof}
Plug $x = -1$, $y=1$ into binomial theorem.
\end{proof}

The combinatorial interpretation is as follows: the number of ways of
selecting an even number of elements from a set of $n$ equals the
number of ways of selecting an odd number.  This works for both even
and odd $n$!

\begin{example}
  Consider $n = 5$.  We can choose an odd-size set ${5 \choose 1} + {5
    \choose 3} + {5 \choose 5} = 5 + 10 + 1 = 16$ ways.  We can chooce
  an even-size set ${5 \choose 0} + {5 \choose 2} + {5 \choose 4} = 1
  + 10 + 5 = 16$ ways.
\end{example}

\begin{example}
$n = 6$: 
There are $6 + 20 + 6 = 32$ odd sets. 
There are $1 + 15 + 15 + 1 = 32$ even sets.
\end{example}

For odd $n$, this is intuitive (choosing an even set leaves an odd
set).  For even $n$, it may be somewhat surprising---there is no
obvious bijection between the even and odd sets.

\begin{theorem}
$$\sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} = 2^{n-1}.$$
\end{theorem}

\begin{proof}
\begin{description}
\item[Algebraic:] Add the equations in the two previous theorems.  We
  get
\begin{align*}
\sum_{k=0}^n \left(\binom{n}{k} + (-1)^k\binom{n}{k}\right) &= 2^n.
\intertext{%
The terms with $k$ odd cancel out, while the even terms double, so we
get:}
2 \sum_{k=0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} &= 2^n.
\end{align*}
Then divide by 2.
\item[Combinatorial:] The LHS represents the number of ways to pick an
  even number of elements from a set of $n$ elements.  The number of
  ways to pick an even number is equal to the number of ways to pick
  an odd number of elements.  Since the total number of ways is $2^n$,
  the number of ways to pick even is half this, or $2^{n-1}$.
\end{description}
\end{proof}

This also provides a new proof of Pascal's identity:

\begin{proof}
  We know that $(x+y)^n = x(x+y)^{n-1} + y(x+y)^{n-1}$.  Consider the
  coefficient of $x^r y^{n-r}$.  On the LHS this coefficient ${n
    \choose r}$ by the binomial theorem. On the RHS this coefficient
  is obtained by adding coefficient of $x^{r-1} y^{n-r}$ in the first
  term, plus the coefficient of $x^r y^{n-1-r}$ in the second term.
  These are ${n-1 \choose r-1}$ and ${n-1 \choose r}$, respectively
  (again by the binomial theorem).
\end{proof}

It also gives a new proof of Vandermonde's identity:

\begin{proof}
  We know $(1+t)^{m+n} = (1+t)^m(1+t)^n$.  Consider the coefficient of
  $t^r$.  On the LHS this is ${m+n \choose r}$ by the binomial
  theorem.  On the RHS, it is obtained by adding up, for all $k$, the
  product of the coefficient of $t^k$ in the second factor and the
  coefficient of $t^{r-k}$ in the first factor.  This is
\[
\Sigma_{k=0}^r {n \choose k} {m \choose r-k}.
\]
\end{proof}

Both of these new proofs are examples of a new technique called
``generating functions'' that make it easy to manipulate series and
recurrences.    They package an entire sequence (in this case, the
sequence of binomial coefficients) inside the taylor expantion of a
single function (in this case, $(x+y)^n$).

\forstudents{
\subsection{The General Binomial Theorem}

We can generalize binomial coefficients once again, allowing the first
argument to be any real number:

\begin{defin}
  {\bf The Generalized binomial coefficient} $\binom{\alpha}{k}$ for
  $\alpha \in \reals$ and $k\in \naturals$:
  \begin{eqnarray*}
    \binom{\alpha}{k} &= &\frac{1}{k!}\prod_{j=0}^{k-1}(\alpha-j)\\ 
    & =    &\frac{\alpha(\alpha-1)\cdots(\alpha-k+1)}{k!} \\
    \binom{\alpha}{0} &= &1
  \end{eqnarray*}
\end{defin}

This doesn't have the same kinds of combinatorial meaning as
before---for example, some of the terms in the product can now be
negative if $k>\alpha$---but it works out nice mathematically.  In
particular, a version of the binomial theorem holds:

\begin{theorem}
Let $\alpha \in \reals$ and $\left| \frac{x}{y} \right| <1$. Then
$$(x+y)^\alpha=\sum_{k=0}^\infty \binom{\alpha}{k}x^ky^{\alpha - k}$$
\end{theorem}

\begin{proof}
Calculus.
\end{proof}

\begin{example}
Approximate $\sqrt{2}$ using binomial theorem. 
$$\sqrt{2} = (x+y)^{\frac{1}{2}}, \; \mbox{where} \; x=1,y=1$$
However, we can't use the binomial theorem directly, because
$$\left| \frac{x}{y} \right| \not < 1$$.
\\
However,
$$ \sqrt{2} =
2\frac{\sqrt{2}}{2}=2\sqrt{\frac12}=2(1-\frac12)^{\frac12}=2(x+y)^{\frac12},
  \; \mbox{where} \; x=1, y=-\frac12 $$ \\
  $$(1-\frac12)^{\frac12} = \sum_{k=0}^\infty \binom{\frac12}k
  \left(-\frac12 \right)^k $$
    $$ \binom{\frac12}0=1, \binom{\frac12}1=\frac12,
    \binom{\frac12}2=\frac{\left( \frac12 \right)\left(-\frac12
    \right)}{2!}=-\frac18, \binom{\frac12}3=\frac{\left( \frac12
  \right)\left(-\frac12\right)\left(-\frac32\right)}{3!}=\frac1{16},
etc. $$
\begin{eqnarray*}
  \sqrt{2} &= 2\left(
  1+\frac12\left(-\frac12\right)+\left(-\frac18\right)
  \left(\frac14\right)+\left(\frac1{16}\right)
    \left(-\frac18\right)+\cdots\right) \\
&= 2\left(1-\frac14-\frac1{32}-\frac{1}{128}-\cdots\right) \\
&\approx 2(.7109375) = 1.421875
\end{eqnarray*} 
\end{example}
}

\section{Principle of Inclusion and Exclusion}

Now we return to the principle of inclusion-exclusion from last
lecture.  Our binomial coefficient identities give us a way to prove
this theorem, via our alternating sum identity (proved by binomial
theorem).  Recall the Inclusion-Exclusion theorem:

\begin{theorem}
\[|\cup_i A_i| = 
\Sigma_i |A_i| 
- \Sigma_{i,j \mbox{ distinct }} |A_i \cup A_j|
+ \Sigma_{i,j,k \mbox{ distinct }} |A_i \cup A_j \cup A_k| - \cdots
\]
\end{theorem}

The theorem can be proved by induction on the number of sets, but this
approach is messy, so LTTR.  Instead we will give a combinatorial
proof using binomial coefficients.

\begin{proof}
Each term in the summation counts certain elements in $\cup_i A_i$. 
We prove that every element of this union is counted exactly once. 
So, consider any particular element $a$, and suppose it is in exactly
$r$ of the sets $A_i$. 
We see how many times $a$ is counted by each term. 

In the first term, $a$ is counted $r = {r \choose 1}$ times, once for
each of the sets that contains it. 
In the second term, $a$ is counted ${r \choose 2}$ times, once for
each of the pairs of sets that contain it. 
In the third term, $a$ is counted ${r \choose 3}$ times, $\ldots$,
and in the $r$th term, $a$ is counted ${r \choose r} = 1$ times. 
The terms alternate signs, so the total number of times $a$ is counted
is: 
$${r \choose 1} - {r \choose 2} + {r \choose 3} - \ldots - (-1)^r{r
\choose r}.$$ 
But Theorem \ref{bin-coeff-3} implies that 
$$\sum_{k=0}^r (-1)^k\binom{n}{k} = 0.$$ 
This implies that the sum above is equal to ${r \choose 0} = 1$. 
That is, $a$ is counted exactly once, as needed.
\end{proof}

\section{$r$-Permutations with Repetition}

We now turn permutations and combinations where elements are allowed
to repeat.  An {\em $r$-permutation with repetition} of a set $S$ is
the number of ways to choose $r$ elements from $S$ with repetition
allowed and where order matters.  For example, there are nine
2-permutations with repetition of the set $S = \{A, B, C \}$, which
are listed below.

\[
\begin{array}{ccc}
(A, A) & (A, B) & (A, C) \\
(B, A) & (B, B) & (B, C) \\
(C, A) & (C, B) & (C, C)
\end{array}
\]

\subsection{Counting $r$-Permutations with Repetition}

Fortunately, $r$-permutations with repetition are easy to count.

\begin{theorem}
The number of $r$-permutations with repetition of an $n$-element set
is $n^r$.
\end{theorem}

For example, the theorem says that the number of 2-permutations with
repetition of the 3-element set $S = \{A, B, C \}$ is $3^2 = 9$, which
checks with our previous answer.

\begin{proof}
Let $S$ be a set with $n$ elements.  The $r$-permutations with
repetition of $S$ are precisely the elements of:

\[
\underbrace{S \times S \times \ldots \times S}_{\text{$r$ terms}}
\]

By the Product Rule, this set has cardinality $|S|^r = n^r$.
\end{proof}

\subsection{Permutations with Limited Repetition}

We might want to count the number of $r$-permutations where each
element can be repeated a limited number of times.  In general, this
leads to some hairy analysis and no closed-form answer.  Therefore, we
will consider only a special case, the number of $r$-permutations
where each element is repeated a precisely specified number of times.

For example, in how many ways can we arrange the letters in the word
$PEPPER$?  This is equal to the number of 6-permutations of the set
$\{ P, E, R \}$ where $P$ is repeated 3 times, $E$ is repeated 2
times, and $R$ is repeated 1 time.  (Since the total number of
repetitions defines $r$, we will use the term ``permutations'' in
place of ``$r$-permutations'' for the remainder of the section.)

Initially, suppose that we make all the letters distinct by adding
subscripts.  That is, we want the number of ways to arrange the
letters $P_1E_1P_2P_3E_2R$.  In this case, there are $6! = 720$
arrangements because there are six choices for the first letter, five
choices for the second letter, etc.

Next, suppose that we erase the subscripts on the $E$'s.  This maps
each arrangement of the letters $P_1E_1P_2P_3E_2R$ to an arrangement of
the letters $P_1EP_2P_3ER$.  Since $E_1$ and $E_2$ could be ordered in
$2!$ ways before the erasure, the mapping is 2!-to-1.  For example, we
have:

\begin{eqnarray*}
P_1E_1P_2P_3E_2R & \rightarrow & P_1EP_2P_3ER \\
                 & \text{and}  & \\
P_1E_2P_2P_3E_1R & \rightarrow & P_1EP_2P_3ER
\end{eqnarray*}

Therefore, by the Division Rule there are $\frac{6!}{2!} = 360$
arrangement of the letters in $P_1EP_2P_3ER$.

Finally, suppose that we erase the subscripts on the $P$'s.  This maps
each arrangement of the letters $P_1EP_2P_3ER$ to an arrangement of
the letters $PEPPER$.  Since $P_1$, $P_2$, and $P_3$ could be ordered
in $3!$ ways before the erasure, this mapping is 3!-to-1.  Therefore,
by the Division Rule, the number of arrangements of the letters
$PEPPER$ is $\frac{6!}{2!\ 3!} = 60$.

We can prove a general theorem using the same argument as in the
$PEPPER$ problem.

\begin{theorem}
\label{th:multinomial}
Let $A$ be the set $\{ a_1, a_2, \ldots, a_n \}$, and let $r_1, r_2,
\ldots, r_n$ be non-negative integers.  The number of permutations of the
set $A$ where each element $a_i$ is repeated exactly $r_i$ times is:

\[
\frac{(r_1 + r_2 + \ldots + r_n)!}{r_1! \ r_2! \ \ldots \ r_n!}
\]
\end{theorem}

For example, the theorem says that the number of permutations of $\{
P, E, R \}$ where $P$ is repeated 3 times, $E$ is repeated 2 times,
and $R$ is repeated 1 time is $\frac{(3 + 2 + 1)!}{3!\ 2!\ 1!} = 60$.
This is the answer we found before.

\begin{proof} {\em (Sketch.) }
We initially make $r_i$ distinct copies of each element $a_i$.  Then
the number of permutations where each element is repeated exactly once
is $(r_1 + r_2 + \ldots + r_n)!$.  We then ``erase the subscripts'' on
the distinct copies of element $a_1$.  This defines an $r_1!$-to-1
mapping from old permutations to permutations where $a_1$ is
repeated $r_1$ times and all other elements are repeated once.
Therefore the number of new permutations is $\frac{(r_1 + r_2 + \ldots
+ r_n)!}{r_1!}$.  Continuing this way with $a_2, a_3, \ldots$, we we
find that the number of permutations where each element $a_i$ is
repeated exactly $r_i$ times is $\frac{(r_1 + r_2 + \ldots +
r_n)!}{r_1!\ r_2! \ \ldots \ r_n!}$.
\end{proof}

\subsection{Multinomial Coefficients}

What is the number of permutations of the set $A = \{a_1, a_2\}$ where
$a_1$ is repeated $r_1$ times and $a_2$ is repeated $r_2$ times?
According to Theorem~\ref{th:multinomial}, the answer is:

\[
\frac{(r_1 + r_1)!}{r_1!\ r_2!} = \binom{r_1 + r_2}{r_1}
\]

We can restate the question as follows.  How many strings contain $r_1$
copies of the symbol $a_1$ and $r_2$ copies of the symbol $a_2$?  This
is equal to the number of ways to choose $r_1$ distinct positions for
the $a_1$'s from the set of all $r_1 + r_2$ positions, which is
$\binom{r_1 + r_2}{r_1}$.  This is the same as the previous answer.

By shifting from ``permutations'' to ``strings'' in this way, we can
give an alternate proof of Theorem~\ref{th:multinomial}.

\begin{proof} {\em (Alternate proof of Theorem~\ref{th:multinomial}.)}
There is a bijection between permutations of the set $A = \{ a_1, a_2,
\ldots, a_n \}$ where each element $a_i$ appears exactly $r_i$ times
and strings where each symbol $a_i$ appears exactly $r_i$ times.
Therefore, we can count permutations by counting strings as follows.

The number of ways to choose $r_1$ distinct positions for the $a_1$'s
from the set of all $r_1 + r_2 + \ldots + r_n$ positions is
$\binom{r_1 + r_2 + \ldots + r_n}{r_1}$.  Then the number of ways to
choose $r_2$ distinct positions for the $a_2$'s from the set of all
$r_2 + \ldots + r_n$ remaining positions is $\binom{r_2 +
\ldots + r_n}{r_2}$, and so forth.  The total number of strings is
therefore:

\begin{eqnarray*}
&   &   \binom{r_1 + r_2 + \ldots + r_n}{r_1} \cdot
        \binom{r_2 + \ldots + r_n}{r_2} \cdot
        \binom{r_3 + \ldots + r_n}{r_3} \cdot
        \cdots
        \binom{r_n}{r_n} \\*[2ex]
& = &   \frac{(r_1 + r_2 + \ldots + r_n)!}{r_1!\ (r_2 + \ldots + r_n)!} \cdot
        \frac{(r_2 + \ldots + r_n)!}{r_2!\ (r_3 + \ldots + r_n)!} \cdot
        \frac{(r_3 + \ldots + r_n)!}{r_3!\ (r_4 + \ldots + r_n)!} \cdot
        \cdots
        \frac{r_n!}{r_n!\ 0!} \\*[2ex]
& = &   \frac{(r_1 + r_2 + \ldots + r_n)!}{r_1!\ r_2!\ \ldots\ r_n!}
\end{eqnarray*}

The first equality uses the definition of binomial coefficients, and
the second follows by cancelling terms.
\end{proof}

The quantity $\frac{(r_1 + r_2 + \ldots + r_n)!}{r_1!\ r_2!\ \ldots\
r_n!}$ is called a {\em multinomial coefficient} and is denoted
$\binom{r_1 + r_2 + \ldots + r_n}{r_1, r_2, \ldots, r_n}$.  Given a
set with $r_1 + r_2 + \ldots + r_n$ elements, the multinomial
coefficient $\binom{r_1 + r_2 + \ldots + r_n}{r_1, r_2, \ldots, r_n}$
represents the number of ways to choose $r_1$ elements, then $r_2$ of
the remaining elements, and so forth.

Multinomial coefficients also arise in the Multinomial Theorem, a
generalization of the Binomial Theorem.  The result is stated below,
but not proved.

\begin{theorem}[Multinomial Theorem]
\[
(x_1 + x_2 + \ldots + x_n)^r =
        \sum^{r_1 + r_2 + \ldots + r_n = r} \binom{r}{r_1, r_2, \ldots, r_n}
        x^{r_1} x^{r_2} \ldots x^{r_n}
\]
\end{theorem}

\section{Combinations with Repetition}

Now we move from permutations with repetition to combinations with
repetition.  Let $S$ be the set $\{ A, B, C \}$.  As we saw in the
previous lecture, this set has three 2-combinations.  That is, there
are three ways to choose two distinct elements of $S$ where order does
not matter.  The three 2-combinations of $S$ are shown below.

\[
\{ A, B \} \quad \{ A, C \} \quad \{ B, C \}
\]

Suppose that we are not required to choose distinct elements of $S$,
but rather can choose the same element repeatedly.  The resulting sets
are called the {\em $r$-combinations with repetition} of the set $S$.
Listed below are the six $2$-combinations with repetition of $S$.

\[
\{ A, B \} \quad \{ A, C \} \quad \{ B, C \} \quad
\{ A, A \} \quad \{ B, B \} \quad \{ C, C \}
\]

Strictly speaking, these are multisets, not sets, since an element may
appear multiple times.

\subsection{Counting $r$-Combinations with Repetition}

The following theorem gives a nice formula for the number of
$r$-combinations with repetition of an $n$-element set.

\begin{theorem}
\label{th:comb-rep}
The number of $r$-combinations with repetition of an $n$-element set
is

\[
\binom{n + r - 1}{r}.
\]
\end{theorem}

In the example above, we found six ways to choose two elements from
the set $S = \{ A, B, C \}$ with repetition allowed.  Sure enough, the
theorem says that the number of 2-combinations of a 3-element set is
$\binom{3 + 2 - 1}{2} = 6$.

For comparison, recall that the number of ordinary $r$-combinations of
an $n$-element set is $\binom{n}{r}$.  Every ordinary $r$-combination
is also a valid $r$-combination with repetition.  So, as one would
expect, the number of $r$-combinations with repetition is greater if
$r > 1$.

The proof of this theorem uses an important trick calls ``stars and
bars''.

\begin{proof}
Let $S$ be a set with $n$ elements that are ordered in some way.  We
will establish a bijection between $r$-combinations with repetition of
the set $S$ and strings of stars and bars.

Let $R$ be a particular $r$-combination with repetition of $S$.  Write
down $n-1$ bars.  These $n-1$ bars divide the line into $n$ regions.

\[
\underbrace{\quad \mid \quad \quad \mid \quad \quad \mid \quad \quad
        \ldots \quad \quad \mid \quad}_{\text{$n-1$ bars define $n$ regions}}
\]

Put one star in the $i$-th region for each time that the $i$-th
element of $S$ appears in $R$.  This procedure maps each
$r$-combination with repetition to a string with $r$ stars and $n-1$
bars.

(For example, let $S$ be the set $\{ A, B, C, D, E \}$, with elements
ordered alphabetically.  Let $R$ be the $7$-combination with
repetition $\{ A, B, B, B, D, E, E \}$.  The stars-and-bars string
corresponding to $R$ is shown below.

\[
\underbrace{\star}_{A} \ \mid \
\underbrace{\star \ \star \ \star}_{B, B, B} \ \mid \ \ \mid \ 
\underbrace{\star}_{D} \ \mid \ 
\underbrace{\star \ \star}_{E, E}
\]

The two bars with no stars between indicate that element $C$ never
appears in $R$.)

This mapping is a bijection because it has an inverse.  That is, given
any stars-and-bars string, we can construct the corresponding
$r$-combination with repetition.  The number of stars in the first
region determines the number of times that the first element of $S$
appears in the $r$-combination, the stars in the second region
determine the number of times that the second element appears, etc.

Since the mapping is a bijection, the number of $r$-combinations with
repetition of an $n$-element set is equal to the number of strings
containing $n-1$ bars and $r$ stars.  The number of such strings is
equal to the number of ways to choose $r$ distinct positions for the
stars in a string of $n + r - 1$ stars and bars.  This is the number
of ordinary $r$-combinations of a set with $n + r -1$ elements, which
is $\binom{n + r - 1}{r}$.
\end{proof}

\subsection{Triple-Scoop Ice Cream Cones}

Baskin-Robbins is an ice cream store that has 31 different flavors.
How many different triple-scoop ice cream cones are possible at
Baskin-Robbins?  Two ice cream cones are considered the same if one
can be obtained from the other by reordering the scoops.  Of course,
we are permitted to have two or even three scoops of the same flavor.

Of course, the best solution to this problem is to go to the
Baskin-Robbins in Harvard Square and explicitly construct all possible
combinations.  This is called the {\em consumption method}.  However,
there is also a purely mathematical approach.

The number of triple-scoop ice cream cones is precisely the number of
3-combinations with repetition of the set of 31 flavors.  Therefore,
we can count the number of ice creams cones with the formula in
Theorem~\ref{th:comb-rep} where $n=31$ and $r=3$.  This gives:

\[
\binom{31 + 3 - 1}{3} = \binom{33}{3} =
\frac{33 \cdot 32 \cdot 31}{3 \cdot 2 \cdot 1} = 5456
\]

On Thursdays the Harvard Square Baskin-Robbins is run by an irritating
woman who refuses to serve a cone with two or three scoops of the same
flavor.  How many different triple-scoop ice cream cones are possible
on Thursday?

Now we must select an ice cream cone by choosing 3 {\em distinct}
flavors from the complete set of 31.  Therefore, the number of
different cones is the number of ordinary 3-combinations of a
31-element set.  This is:

\[
\binom{31}{3} = \frac{31 \cdot 30 \cdot 29}{3 \cdot 2 \cdot 1} = 4495
\]

As we would expect, the number of combinations with repetition is
greater than number number of combinations without repetition.
Permitting scoops of the same flavor gives an extra $5456 - 4495 =
961$ options.

\subsection{Dozens of Dunkin Donuts}

Suppose we next stagger down to the Dunkin Donuts in Central Square.
We want a box of a dozen doughnuts and there are 21 varieties
available.  How many options do we have?

We select our box of doughnuts by pointing out 12 varieties from the
complete set of 21 where repetition is allowed.  Therefore, the number
of options is the number of 12-combinations with repetition of a 21
element set.  Applying Theorem~\ref{th:comb-rep} with $n=21$ and
$r=12$, we find that number of different boxes of doughnuts is:

\[
\binom{21 + 12 - 1}{12} = \binom{32}{12} = 225,792,840
\]

\subsection{Balls and Bins}

Suppose that we have $r$ identical balls and $n$ distinct bins.  In
how many ways can we arrange the balls in the bins?  There are six
possibilities for the case of two balls and three bins, as shown
below.

\[
\begin{array}{c}
\begin{array}{|p{3em}|p{3em}|p{3em}|} \ball \ball & & \\ \hline \end{array}
\\*[2ex]
\begin{array}{|p{3em}|p{3em}|p{3em}|} & \ball \ball & \\ \hline \end{array}
\\*[2ex]
\begin{array}{|p{3em}|p{3em}|p{3em}|} & & \ball \ball \\ \hline \end{array}
\\*[2ex]
\begin{array}{|p{3em}|p{3em}|p{3em}|} \ball & \ball & \\ \hline \end{array}
\\*[2ex]
\begin{array}{|p{3em}|p{3em}|p{3em}|} \ball & & \ball \\ \hline \end{array}
\\*[2ex]
\begin{array}{|p{3em}|p{3em}|p{3em}|} & \ball & \ball \\ \hline \end{array}
\end{array}
\]

\begin{claim}
\label{clm:balls}
There are $\binom{n + r - 1}{r}$ ways to arrange $r$ identical balls
in $n$ distinct bins.
\end{claim}

\begin{proof}
Each arrangement of the $r$ balls corresponds to an $r$-combination
with repetition of the set of $n$ bins.  Specifically, if the $i$-th
bin contains $a_i$ balls, then the corresponding $r$-combination with
repetition contains the $i$-th bin $a_i$ times.  Therefore, the number
of arrangement of balls is equal to the number of $r$-combinations of
an $n$ element set, which is $\binom{n + r - 1}{r}$ by
Theorem~\ref{th:comb-rep}.
\end{proof}

There is another way to prove the claim that uses a cute bijection
between balls-and-bins arrangements and stars-and-bars strings.  The
six arrangements in the preceding example are redrawn below with some
lines erased and the balls replaced by stars.

\[
\begin{array}{c}
\begin{array}{p{3em}|p{3em}|p{3em}} \str \str & & \end{array} \\*[2ex]
\begin{array}{p{3em}|p{3em}|p{3em}} & \str \str & \end{array} \\*[2ex]
\begin{array}{p{3em}|p{3em}|p{3em}} & & \str \str \end{array} \\*[2ex]
\begin{array}{p{3em}|p{3em}|p{3em}} \str & \str & \end{array} \\*[2ex]
\begin{array}{p{3em}|p{3em}|p{3em}} \str & & \str \end{array} \\*[2ex]
\begin{array}{p{3em}|p{3em}|p{3em}} & \str & \str \end{array}
\end{array}
\]

Now each balls-and-bin diagram has become a stars-and-bars string.
The number of ways to place $r$ balls in $n$ bins is therefore equal
to the number of strings with $r$ stars and $n-1$ bars, which is
$\binom{n + r - 1}{r}$.

\subsection{Data Compression}

Stars and bars can help solve a data compression problem.  How many
bits are needed to specify a set of $N$ arbitrary integers in the
range $[0, 2N]$?  For example, how much disk space do we need to store
one million numbers in the range zero to two million?

\subsubsection*{A Simple Scheme}

One simple scheme is store each number in binary.  With this approach,
storing each number requires $\left\lceil \log_2(2N +1) \right\rceil$
bits.  Storing all $N$ numbers requires $N \left\lceil \log_2(2N +1)
\right\rceil$ bits.  In the case of a million numbers, we need 21 bits
to store each number and therefore 21 million bits to store all of the
numbers.

\subsubsection*{A Better Approach Using Stars and Bars}

There is a more clever scheme that uses stars and bars.  We can regard
the set of numbers that we want to store as an $N$-combination with
repetition of the $(2N+1)$-element set $[0,2N]$.  The proof of
Theorem~\ref{th:comb-rep} shows that such $N$-combinations with
repetition correspond to strings of $N$ stars and $2N$ bars.  If we
represent a star with a 0 and a bar with a 1, then we can store such a
stars-and-bars string using $N + 2N = 3N$ bits.

To make the scheme clear, suppose that we are storing a set of $N = 5$
numbers in the range $[0, 10]$.  In particular, suppose that the
numbers are $\{ 2, 4, 4, 6, 7 \}$.  We can represent this multiset as
a stars-and-bars string and then with $3N = 15$ bits as follows.

\begin{eqnarray*}
\{ 2, 4, 4, 6, 7 \}     & \rightarrow &
        \mid \ \ \mid \ \star \ \mid \ \ \mid \ \star \ \star \ \mid \ \ 
        \mid \ \star \ \mid \ \star \ \mid \ \ \mid \ \ \mid \\
        & \rightarrow & 1\ 1\ 0\ 1\ 1\ 0\ 0\ 1\ 1\ 0\ 1\ 0\ 1\ 1\ 1
\end{eqnarray*}

As another example, we could store a million numbers in the range zero
to two million using only 3 million bits, a factor of 7 improvement
over the simple scheme.  It is rather surprising that we need only 3
bits per number on average, no matter how large $N$ becomes!

\subsubsection*{An Optimal Scheme}

The stars-and-bars approach is simple and efficient, but not quite
optimal.

In any scheme, we must associate every set of $N$ numbers with a
distinct binary string.  From the stars-and-bars interpretation, we
know that there are $\binom{3N}{N}$ possible sets of $N$ numbers.
Therefore, we must be prepared to store any one of $\binom{3N}{N}$
distinct binary strings.  Using $k$ bits, we can store at most $2^k$
different binary strings.  This means that we need at least $k$ bits
where $2^k \geq \binom{3N}{N}$.  This inequality is satisfied provided
$k \geq \left\lceil \log_2 \binom{3N}{N} \right\rceil$.  Therefore, as
a lower bound, we need at least $\left\lceil \log_2 \binom{3N}{N}
\right\rceil$ bits.

How far from optimal is the stars-and-bars scheme?  To answer this
question, we must rewrite the lower bound in a more familiar form.  To
this end, we can use Stirling's Formula to approximate $\binom{3N}{N}$
as follows.

\begin{eqnarray*}
\binom{3N}{N}
        & = & \frac{(3N)!}{(2N)! \ N!} \\
        & \sim & \frac{\sqrt{2 \pi (3N)} \left( \frac{3N}{e} \right)^{3N}}
                   {\sqrt{2 \pi (2N)} \left( \frac{2N}{e} \right)^{2N}
                    \sqrt{2 \pi N}    \left( \frac{ N}{e} \right)^{ N}} \\
        & = & \sqrt{\frac{3}{4 \pi N}} \left( \frac{3^{3N}}{2^{2N}} \right)\\
        & = & \sqrt{\frac{3}{4 \pi N}} \left( \frac{27}{4} \right)^N \\
\end{eqnarray*}

With this formula, we can approximate the lower bound.

\begin{eqnarray*}
\left\lceil \log_2 \binom{3N}{N} \right\rceil
        & \sim & N \log_2 \frac{27}{4} -
                \underbrace{\frac{1}{2} \log_2{\frac{4 \pi N}{3}}}_{
                \text{low-order term}} \\
        & \sim & 2.755\ldots \cdot N
\end{eqnarray*}

The stars-and-bars approach uses $3N$ bits, which is slightly more
than the lower bound of about $2.755N$ bits.

This lower bound is actually not hard to achieve, though we will not
cover the details.  The idea is to order all of the multisets of $N$
numbers in the range $[0,2N]$ and then index them $0, 1, 2, \ldots$.
We then store a multiset by storing its index.  The index is a number
in the range $0$ to $\binom{3N}{N} - 1$, which we can store in exactly
$\left\lceil \log_2 \binom{3N}{N} \right\rceil$ bits.  Of course, the
hard part is efficiently mapping a multiset to an index and vice
versa.  Nevertheless, we can store a million numbers in the range zero
to two million with only 2.755 million bits.

\subsection{$r$-Combinations with at Least One of Each Item}

Suppose that Kaybee Toys carries balls in three delightful colors:
red, blue, and green.\footnote{I bet you're wondering if the 6.042
staff has discovered a lucrative scam involving product promotion in
lecture notes.  No comment.} In how many ways can we choose five balls
so that we get at least one ball of each color?

We might as well start by choosing one ball of each color.  Then we
can choose the last two balls however we like.  Remember that we are
counting combinations, so the order in which we choose the balls does
not matter.

Under this interpretation, the number of options is equal to the number
of ways to choose two balls from the set of three colors with
repetition allowed.  Therefore, by Theorem~\ref{th:comb-rep} there are
$\binom{3 + 2 - 1}{2} = 6$ possibilities.  Here they are:

\[
\begin{array}{ccc}
\{R,G,B,\ R,R\} & \{R,G,B,\ R,G\} & \{R,G,B,\ R,B\} \\
\{R,G,B,\ G,G\} & \{R,G,B,\ G,B\} & \{R,G,B,\ B,B\}
\end{array}
\]

This argument generalizes to give the theorem below.

\begin{theorem}
\label{th:comb-rep-min}
The number of $r$-combinations with repetition of an $n$-element set
that contain every element in the set at least once is:

\[
\binom{r - 1}{n - 1}
\]
\end{theorem}

For example, in the colored balls problem, we have $r = 5$ and $n =
3$.  The theorem says that there are $\binom{5 - 1}{3 - 1} = 6$
possibilities, which is consistent with out previous answer.

\begin{proof}
Every such $r$-combination consists of the entire $n$-element set
together with an $(r-n)$-combination with repetition of the
$n$-element set.  By Theorem~\ref{th:comb-rep} the number of such
combinations is:

\[
\binom{n + (r-n) - 1}{r-n} = \binom{r - 1}{r - n} = \binom{r-1}{n-1}
\]

The last equality uses the identity $\binom{m}{k} = \binom{m}{m-k}$.
\end{proof}

How many $n$-combinations with repetition of an $n$-element set are
there that contain every element in the set?  In this case,
Theorem~\ref{th:comb-rep-min} gives $\binom{n-1}{n-1} = 1$.  This
makes sense; the only such combination is the set $S$ itself!

In how many ways can we arrange $r$ identical balls in $n$ distinct
bins so that no bin is empty?  If we first put one ball in each bin,
then we can arrange the remaining $r-n$ balls in $\binom{n + (r-n) -
1}{r-n} = \binom{n-1}{r-1}$ ways.

\subsection{$r$-Combinations with Limited Repetition}

Suppose that we want to count $r$-combinations where an element can be
repeated only a limited number of times.  For example, in how many
ways can we arrange 10 identical balls in 4 distinct bins such no bin
gets more than 7 balls?  A good way to solve such problems is first to
count the number of arrangements without a limit on repetition and
then to subtract off the illegal arrangements.

The number of ways to arrange 10 identical balls in 4 distinct bins
without a limit on repetition is $\binom{4 + 10 - 1}{10} = 286$.

Now we must count the illegal arrangements; that is, arrangements in
which some bin contains 8 or more balls.  Since there are only 10
balls in total, at most one bin can be overloaded with 8 or more
balls.  We can count the number of ways to overload the first bin by
putting 8 balls into the first bin and then observing that the last
two balls can be placed in $\binom{4 + 2 - 1}{2} = 10$ ways.  Since
any one of the four bins could be overloaded, the total number of
illegal arrangement is $4 \cdot 10 = 40$.

Overall, there are $286 - 40 = 246$ ways to arrange 10 balls in 4 bins
so that no bin gets more than 7 balls.

Sometimes when there are limits on repetition, the number of illegal
arrangements can itself be difficult to compute.  In such cases, a
messy inclusion-exclusion calculation may be necessary.

\section{Summary}

The table below summarizes the basic results from our lectures about
choosing $r$ elements from an $n$-element set:

\begin{eqnarray*}
\text{$r$-combinations without repetition} & = & \binom{n}{r} \\*[3ex]
\text{$r$-permutations without repetition} & = & \frac{n!}{(n-r)!} \\*[3ex]
\text{$r$-combinations with repetition} & = & \binom{n+r-1}{r} \\*[3ex]
\text{$r$-permutations with repetition} & = & n^r
\end{eqnarray*}

\end{outline}

\end{document}
