\documentclass[12pt]{6042}
\usepackage{eepic}

%\documentstyle[12pt,twoside,amsfonts,amstex,psfig]{article}

%\raggedbottom

% \input{macros-course}

\newcommand{\recn}[3]
{\setcounter{problemsetnum}{#1}
\handout{rec#1}{Notes for Recitation #1 (#2/98)}{#3}
}

\newcommand{\numb}[1]{\#\text{#1}}

\begin{document}

\recn{9}{4/10}{April 10, 1998}


\section{Multinomial Coefficients}
The following theorem was proved in lecture using the Division Theorem.

\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.


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 following generalization of the
Binomial Theorem.

\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{An Apparently Complicated Counting Problem}

Here is an absurd counting problem.  In how many ways can we fill a
bag with $n$ fruits subject to the following constraints?

\begin{itemize}
\item The number of apples must be even.
\item The number of bananas must be a multiple of 5.
\item There can be at most four oranges.
\item There can be at most one pear.
\end{itemize}

For example, there are 7 ways to form a bag with 6 fruits:

\[
\begin{array}{c|ccccccc}
\mbox{Apples}  & 6 & 4 & 4 & 2 & 2 & 0 & 0 \\
\mbox{Bananas} & 0 & 0 & 0 & 0 & 0 & 5 & 5 \\
\mbox{Oranges} & 0 & 2 & 1 & 4 & 3 & 1 & 0 \\
\mbox{Pears}   & 0 & 0 & 1 & 0 & 1 & 0 & 1
\end{array}
\]

This problem appears complicated and without much hope for a closed form
solution for selecting $n$ fruits.  But we can actually use generating
functions to find an answer.

First, we need a generating function for the number of fruit bags.
Initially, we can consider each fruit separately.  That is, we can
count the number of fruit bags with just apples, then just bananas,
pears, \emph{etc}.  For example, the number of fruit bags with 0 apples is one (the
empty bag), the number of bags with 1 apple is zero (the number of
apples must be even), the number of bags with 2 apples is one (the bag
with two apples), etc.  The generating functions for the four types of
fruit are worked out below.

\[\begin{array}{rclcl}
A(x)& = & 1 + x^2 + x^4 + x^6 + \ldots & = & 1/(1-x^2), \\
B(x) &= & 1 + x^5 + x^{10} + x^{15} + \ldots & = &1/(1-x^5), \\
O(x) &= & 1 + x + x^2 + x^3 + x^4 & = & (1-x^5)/(1-x), \\
P(x) &= & 1 + x.
\end{array}\]

Now from lecture, we know
\begin{theorem}
Let $A(x)$ and $B(x)$ be ordinary generating functions for the number of
ways to choose items, subject to given constraints, from disjoint sets
${\cal A}$ and ${\cal B}$, respectively.  The generating function for the
number of ways to choose objects from the union ${\cal A} \cup {\cal B}$
subject to the same constraints is the product $A(x) \cdot B(x)$.
\end{theorem}

So the generating function for the number of ways to pick $n$ fruits
subject to the constraints above is the product of $A, B, O$ and $P$:
\begin{eqnarray*}
\mbox{OGF for fruit bags} & = & A(x) \cdot B(x) \cdot O(x) \cdot P(x)\\
& = & \frac{1}{1-x^2} \frac{1}{1-x^5} \frac{1-x^5}{1-x} (1 + x) \\
& = & \frac{1}{(1-x)^2} \\
& = & 1 + 2x + 3x^2 + 4 x^3 + \ldots
\end{eqnarray*}

The coefficient of $x^n$ is simply $n+1$; that is, the number of ways
to form a bag of $n$ fruits is just $n+1$.  This is consistent with
the example we worked out, since there were 7 fruit bags with 6
fruits.  Amazing!


\section{Paths and Matching Parentheses}
In Recitation 2 we examined the well-matched strings of parentheses.  For
example, \texttt{(()((())()))} is well-matched.  On the other hand, no
string that begins with a left parenthesis or ends with a right
parenthesis can be well-matched; neither can any proper prefix of a
well-matched string be well-matched.

We want to compute the number, $S_n$, of such well-matched parenthesis
strings of length $2n$.  It's easy to check that $S_1=1$, $S_2=1$,
$S_3=2$.  With a little case analysis, the only well-matched strings of 8
parentheses are
\[\texttt{(()(())),\ (()()()),\ ((())()),\ (((()))),\ ((()()))},\]
so $S_4=5$.

The team problem develops an ingenious combinatorial approach to arrive at
a simple formula for $S_n$.  Here we show an alternative derivation of the
formula by manipulating generating functions.

It is not hard to write up a recurrence for $S_n$.  For $n>0$, a well
matched string of $2n$ parentheses must start with a left parenthesis and
end with a right parenthesis.  Also, for $n>1$, there must be a $k \in
\nats$ and a
well-matched string of $2k$ parentheses immediately after the initial left
parenthesis where $0 < k < n$.  This substring
must be followed by a \emph{sequence} of well-matched strings of total
length $2n-2k-2$:
\[\texttt{(}\quad \texttt{(}_1\dots \texttt{)}_{2k}\quad \texttt{(}_1\texttt{)}_2
\texttt{(}_3\dots \texttt{)}_{2n-2k-2}\quad \texttt{)}\]

Since we can turn a sequence of well-matched strings
into a single string by enclosing it in parentheses, the number of such
sequences of well-matched strings is the same as the number of
well-matched strings of length $2n-2k$.  So there are $S_{n-k}$ such
sequences of well-matched strings.  Since there are, by definition, $S_k$
well-matched initial strings of $2k$ parentheses, we have altogether
\[S_n=\sum_{k=1}^{n-1} S_k S_{n-k}\]
for $n>1$.

This is a messy, nonlinear recurrence and might seem hard to solve.  But
the sum above looks exactly like the \emph{convolution} of $(S_0,\dots
,S_n)$ with itself --- except that the sum goes from 1 to $n-1$ instead of
0 to $n$.  Let's fix it so the sum goes from 0 to $n$:
\[S_n=\paren{\sum_{k=0}^{n} S_k S_{n-k}} - S_0S_n - S_nS_0.\]

We'll agree that by convention there is exactly one \emph{empty} string,
and it is well-matched, so $S_0=1$ by convention.  So we conclude that
\[S_n=\paren{\sum_{k=0}^{n} S_k S_{n-k}}/3\]
for $n>1$.  Now we really do have the convolution, and this suggests
trying to fiddle with the \emph{square} of the generating function for the
$S_n$'s.

That is, let
\[S(x) ::= \sum_{n=0}^\infty S_n x^n.\]
So
\begin{eqnarray*}
S(x) & = & S_0+xS_1+ \sum_{n=2}^\infty (\sum_{k=0}^{n} S_k S_{n-k}/3)x^n\\
& = & 1 + x + \sum_{n=2}^\infty \paren{\sum_{k=0}^{n} S_k S_{n-k}}x^n/3\\
& = & 1 + x + \paren{-S_0^2 - (S_0S_1+S_1S_0)x + \sum_{n=0}^\infty \sum_{k=0}^{n} S_k S_{n-k}x^n}/3\\
&= & 1 + x + (-1 - 2x + S(x)^2)/3.
\end{eqnarray*}
Therefore
\[S^2/3 -S + x/3 + 2/3 = 0,\]
and finally
\[S^2 -3S + x + 2 = 0.\]

At this point we can solve for a closed form for $S$:
\[S(x) = \frac{3 \pm \sqrt{9 - 4(x+2)}}{2} =  \frac{3}{2} \pm
\frac{\sqrt{1 - 4x}}{2}.\]
Since $S(0)= S_0 = 1$, we need the negative root, namely:
\[S(x) =  \frac{3}{2} - \frac{(1 - 4x)^{1/2}}{2}.\]

To get the coefficients $S_n$, we need to expand this quantity in a Taylor
series.  That is, we know that $S_n = S^{(n)}(0)/n!$ where $S^{(n)}$ is
the $n$th derivative of $S$.  For example,
\begin{eqnarray*}
S^{(1)}(x) & = & \frac{-(1/2)(1-4x)^{(1/2)-1}(-4)}{2},\\
S^{(2)}(x) & = & \frac{-(1/2)((1/2)-1)(1-4x)^{(1/2)-2}(-4)^2}{2},\\
S^{(n)}(x) & = & \frac{-(1/2)((1/2)-1)((1/2)-2)\cdots(1/2 - (n -1))(1-4x)^{(1/2)-n}(-4)^n}{2}.
\end{eqnarray*}
So for $n>0$,
\[S_n= \frac{S^{(n)}(0)}{n!} = \frac{((1/2)-1)((1/2)-2)\cdots(1/2 - (n -1))(-4)^{n-1}}{n!}.\]
So we have a formula for $S_n$, as desired.  But this formula has dots and
looks messy, so let's work on simplifying it:
\begin{eqnarray*}
S_n &= &\frac{[(-1)(1/2)(2-1)][(-1)(1/2)(4-1)]\cdots[(-1)(1/2)(2(n -1) -1)](-4)^{n-1}}{n!}\\
&=& \frac{(-1)^{n-1}(1/2)^{n-1}1\cdot 3\cdot 5\cdots(2(n -1) -1)(-4)^{n-1}}{n!}\\
&=& \frac{1\cdot 3\cdot 5\cdots(2(n -1) -1)}{n!} \cdot 2^{n-1}\\
&= &\frac{1 \cdot 3 \cdot 5\cdots (2(n-1)-1)}{n!}
       \cdot 2^{n-1} \cdot \frac{2 \cdot 4
       \cdot 6 \cdots 2(n-1)}{2^{n-1} (n-1)!}\\
&= &\frac{1\cdot 2\cdot 3 \cdots (2(n-1))}{n! (n-1)!}\\
&= &\frac{(2(n-1))!}{n(n-1)! (n-1)!}\\
&= &\frac{1}{n} \binom{2n-2}{n-1} \mbox{ --- hey, that's not bad}.
\end{eqnarray*}

The number 
\[S_{n+1} = \frac{1}{n+1} \binom{2n}{n}\]
is called the $n^{th}$ \emph{Catalan number}.

So generating functions let us find this answer without much insight into
the problem.  We just did a lot of formal manipulation with derivatives
and factorials.

\section{Team Problem}
Now we consider another ingenious approach to counting well-matched
parenthesis strings.  Our approach will involve considering \emph{paths}
in the plane from a point $(x_1,y_1)$ to $(x_2,y_2)$ for $x_i,y_i \in
\ints$, where each step in the path is at a $\pm 45$ degree angle,
increasing the x-coordinate by 1 and the y-coordinate by $\pm 1$.  For
example, a path might start at $(1,1)$ and make seven steps to the
successive points $(2,0)$, $(3,-1)$, $(4,0)$, $(5,1)$, $(6,2)$,
$(7,1)$, $(8,0)$ as  in Figure~\ref{fig:path}.

\begin{figure}
\begin{center}
\begin{picture}(345,195)(-45,-45)

\put(0,-45){\line(0,1){195}}
\put(-45,0){\line(1,0){345}}

\put(-30,-2.5){\line(0,1){5}}
\put(30,-2.5){\line(0,1){5}}
\put(60,-2.5){\line(0,1){5}}
\put(90,-2.5){\line(0,1){5}}
\put(120,-2.5){\line(0,1){5}}
\put(150,-2.5){\line(0,1){5}}
\put(180,-2.5){\line(0,1){5}}
\put(210,-2.5){\line(0,1){5}}
\put(240,-2.5){\line(0,1){5}}
\put(270,-2.5){\line(0,1){5}}

\put(-2.5,-30){\line(1,0){5}}
\put(-2.5,30){\line(1,0){5}}
\put(-2.5,60){\line(1,0){5}}
\put(-2.5,90){\line(1,0){5}}
\put(-2.5,120){\line(1,0){5}}

\put(30,30){\circle*{3}}
\put(32,32){\makebox(0,0)[bl]{$(x_1, y_1)$}}

\path(30,30)(60,0)(90,-30)(120,0)(150,30)(180,60)(210,30)(240,0)

\put(60,0){\circle*{3}}
\put(90,-30){\circle*{3}}
\put(120,0){\circle*{3}}
\put(150,30){\circle*{3}}
\put(180,60){\circle*{3}}
\put(210,30){\circle*{3}}

\put(240,0){\circle*{3}}
\put(242,2){\makebox(0,0)[bl]{$(x_2, y_2)$}}

\end{picture}
\end{center}

\caption{\em A path from $(1,1)$ to $(8,0)$.}

\label{fig:path}

\end{figure}


\begin{problems}

\problem
\bparts

\ppart
Explain why the number of well-matched parenthesized strings of
length $2n$ is the same as the number of paths from $(0,0)$ to $(2n,0)$
which only touch the x-axis at their endpoints.  (That is, if $0<i<2n$ and
$(i,j)$ is a point on the path, then $j>0$.)

\textbf{Solution:} Interpret left paren as a ``move up'' step and right
paren as a ``move down'' step.  Then every string of $k$ parens
corresponds to a path of length $k$ from the origin and \emph{vice-versa}
--- a bijection.  Remember in Recitation 2 Team Problem 2, we showed that
the well-matched strings were the same as the well-counting strings.
Well-counting strings correspond exactly to paths from the origin back to
the x axis which don't touch the x-axis in between endpoints.

\ppart
How many paths are there from $(x_1,y_1)$ to $(x_2,y_2)$?  (Express the
answer as a binomial coefficient.)

\textbf{Solution}:
\begin{align*}
\numb{moves}
    & = x_2 - x_1 \\
\numb{up moves} - \numb{down moves}
    & = y_2 - y_1 \\
\numb{up moves} + \numb{down moves}
    & = \numb{moves} = x_2 - x_1 \\
\numb{up moves}
    & = \frac{(x_2 + y_2) - (x_1 + y_1)}{2} ::= u \\
\numb{down moves}
    & = \frac{(x_2 - y_2) - (x_1 - y_1)}{2} ::= d \\
\numb{paths}
    & = \binom{u+d}{u} = \binom{u+d}{d}
\end{align*}

\ppart For $y_1,y_2 > 0$, show that the number of paths from $(x_1,y_1)$
to $(x_2,y_2)$ which touch or cross the x-axis is equal to the number
of paths from $(x_1,-y_1)$ to $(x_2,y_2)$.

\textbf{Solution:} See Figure~\ref{fig:reflect}.

\begin{figure}

\begin{center}
\begin{picture}(345,205)(-45,-55)

\put(0,-45){\line(0,1){195}}
\put(-45,0){\line(1,0){345}}

\put(-30,-2.5){\line(0,1){5}}
\put(30,-2.5){\line(0,1){5}}
\put(60,-2.5){\line(0,1){5}}
\put(90,-2.5){\line(0,1){5}}
\put(120,-2.5){\line(0,1){5}}
\put(150,-2.5){\line(0,1){5}}
\put(180,-2.5){\line(0,1){5}}
\put(210,-2.5){\line(0,1){5}}
\put(240,-2.5){\line(0,1){5}}
\put(270,-2.5){\line(0,1){5}}

\put(-2.5,-30){\line(1,0){5}}
\put(-2.5,30){\line(1,0){5}}
\put(-2.5,60){\line(1,0){5}}
\put(-2.5,90){\line(1,0){5}}
\put(-2.5,120){\line(1,0){5}}

\put(30,30){\circle*{3}}
\put(32,32){\makebox(0,0)[bl]{$(x_1, y_1)$}}

\put(30,-30){\circle*{3}}
\put(32,-32){\makebox(0,0)[tl]{$(x_1, -y_1)$}}

\dottedline{2}(30,-30)(60,0)

\path(30,30)(60,0)(90,-30)(120,0)(150,30)(180,60)(210,30)(240,0)

\put(60,0){\circle*{3}}
\put(90,-30){\circle*{3}}
\put(120,0){\circle*{3}}
\put(150,30){\circle*{3}}
\put(180,60){\circle*{3}}
\put(210,30){\circle*{3}}

\put(240,0){\circle*{3}}
\put(242,2){\makebox(0,0)[bl]{$(x_2, y_2)$}}

\end{picture}
\end{center}

\caption{\em Reflection of the initial part of a path.}

\label{fig:reflect}

\end{figure}

\ppart Conclude that the number of well-matched strings of $2n$ parentheses
equals the $n-1$st Catalan number
\[\frac{1}{n} \binom{2n-2}{n-1}.\]

\textbf{Solution:}

\begin{equation*}
\numb{paths}\bigl( (1, 1) \to (2n-1, 1) \bigr)
        = \binom{2n-2}{n-1}
\end{equation*}
because
\begin{align*}
    u   &= \frac{2n-2}{2}     = n-1 \\
    d   &= \frac{(2n-2)-0}{2} = n-1
\end{align*}

\begin{align*}
\numb{paths}\bigl( (1, 1) \to (2n-1, 1) \text{ touching
    x-axis}\bigr)
    &= \numb{paths}\bigl( (1, -1) \to (2n-1, 1) \bigr) \\
    &= \binom{2n-2}{n} = \binom{2n-2}{n-2}
\end{align*}
because
\begin{align*}
    u &= \frac{2n - 0}{2} = n\\
    d &= \frac{(2n - 2) - 2}{2} = n - 2
\end{align*}

\begin{align*}
\lefteqn{\numb{paths}\bigl( (1, 1) \to (2n-1, 1) \text{ above x-axis}\bigr)} \qquad&\\
    &= \numb{paths}\bigl( (1, 1) \to (2n-1, 1) \bigr)
        - \numb{paths}\bigl( (1, 1) \to (2n-1, 1) \text{ touching} \bigr)\\
    &= \binom{2n-2}{n-1} - \binom{2n-2}{n}\\
    &= \binom{2n-2}{n-1}
        - \frac{(2n-2)!}{n! \, (n-2)!}\\
    &= \binom{2n-2}{n-1}
        - \frac{(2n-2)!(n-1)}{n(n-1)! \, (n-1)!}\\
    &= \binom{2n-2}{n-1} - \frac{n-1}{n}\binom{2n-2}{n-1}\\
    &= \binom{2n-2}{n-1} \cdot \frac{1}{n}
\end{align*}

\eparts
\end{problems}

\iffalse

\section{Optional Topic: Data Compression}
\textbf{I do not expect there to be time to cover this section.  It's here
for backup.}

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]$.  We know 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.
\fi


\end{document}
