\documentclass{article}
\input{preamble.tex}
\title{Day 20}
\date{Wednesday June 20, 2012}
\newcommand{\df}{\textbf}
\usepackage{enumerate}
  \def\Display{\@empty}
\newcommand{\Hide}[2]{\ifx \Display\undefined \strut \\ \vspace{#1} \\ \strut  \else {\color{blue} #2} \fi  }
\begin{document}
\maketitle

\section{Combinatorics}


\subsection{Stars and Bars}

A natural question that come up, is how many ways are there to appropriate some number of indistinguishable things over several categories. For instance, you may have $n$ indistinguishable balls, and you wish to place them in $k$ distinguishable bins. Then you can look at the number of balls in the first bin, and that is the allotement of the item to the first category, and the next the second, etc.

How do we cound this? Well, of course all we are interested in is how many balls are in each bin. Therefore, imagine that we had $n$ stars, $*$. These represent the balls, or the identical objects we wish to appropriate. We need only find a way to divide them into $k$ groups. Our idea is to use dividers, or bars, $|$, which will segment our stars into $k$ parts. Notice, that we need $k-1$ dividers to do this; one can see why by realizing there is already one part without any dividers!

How many ways are there to arrange $n$ identical stars and $k-1$ identical bars? Well, one need only line them up, which is $(n+k-1)!$ ways. Then we mod out by the numbers of ways to arrange the stars, as the stars are identical; this is $n!$. And similarly with the bars; this is $(k-1)!$

Alternatively, one could see the string we will get is of length $n+k-1$. To determine what the string is, we need only know where the stars are. So we choose where the stars are in the string; there are $n+k-1 \choose n$ ways to decide where the stars are. 

\begin{eg}
Someone has to accomplish $5$ tasks, and they have $5$ hours to do it. How many ways are there to appropriate time to the tasks if each time appropriated is a multiple of $15$ minutes.

\Hide{1in}{
There are 20 blocks of time we can allocate to each of the 5 tasks. So the answer is ${20+5-1}\choose 20$. 
}
\end{eg}

\begin{eg}
How many ways can 12 apples and 1 orange be distributed amoung 6 children so that each child recieves at least one fruit?

\Hide{1in}{
Well, we are distributing this among the children. There are 13 fruit, one is an orange. Of course there are $6$ ways to decide who gets the orange. Then we need to give each of the students an apple to gaurentee they get a fruit. So we have 7 apples remaining to divide among the 6 children. There are ${6+7-1} \choose 7$
}
\end{eg}

\begin{eg}
Suppose there are 20 identical sticks lined up in 20 distinct places
\[
\mid\mid\mid\mid\mid\mid\mid\mid\mid\mid\mid\mid\mid\mid\mid\mid\mid\mid\mid\mid
\]
How many ways are there to choose 6 of them? How about, choose 6 given that non-consecutive are chosen? How about, choose 6 so that there must be at least two sticks between each pair of chosen sticks?

\Hide{2in}{
Well, chosing $6$ is easy: there are $20\choose 6$ ways to do that.

Non-consecutive sticks is a bit more difficult however. Imagine we saw the blanks, (there are 7 of them) and we wanted to make sure none were cosecutive. Then we would put bars inbetween them so that there is distance. There are 5 inbetween gaps, and 2 at the end. The ends can be empty, but the others cannot be. So we need to commit one stick for every inbetween gap (that's 5), and then we can spread the rest among the rest as we wish. There are ${{20-5} \choose 6}$

For the last, we need to pad two instead of one. So we commit 10 at the beginning instead of 5. So there are ${{20-10}\choose 6}$. 
}
\end{eg}



\begin{exc}
How many ways do five pirates split $50$ gold bars given that the captain gets at least as much as any of his men?
\end{exc}

\subsection{Multinomials}

Another question that seems natural to ask is when the balls are distinguishable. What the the number of ways to put $n$ distinguishable balls into $k$ distinguishable bins?

Well, looked at another way, since the balls are distinguishable there is an order on them. We can say there is a first ball, and a second, etc. For each ball we need to make a ddecision: bin 1, bin 2, \ldots, bin k. There are $k$ different decisions, for each of the $n$ balls, so the number of ways is $k^n$. 

\begin{eg}
The number of subsets of $A$ where $|A|=n$ is $2^n$. To see why, imagine each ball is an element of $A$, and we have two bins, and this seperates elements. Then the number of subsets is exactly the number of ways to put balls in these two bins as we can look at the balls in the first bin, and this makes a subset. So, there are $2^n$ many elements of the powerset of $A$.
\end{eg}

As a subproblem of the above, suppose we knew exactly how many balls we want in bin 1, and bin 2, etc. So, we have numbers $l_1, l_2, \ldots, l_k$ and this number says we want $l_i$ balls in bin $i$. 

How many ways are there to do this? We give notation to this number (suggestive from combinations). The number of ways is ${n \choose {l_1,l_2,\ldots,l_k}}$. Let's count this number. Well, there are two ways to count it. 

First, we can just do it one at a time:

\begin{tabular}{>{\bfseries}r p{3in} l}
Step 1& Choose balls for first bin & $n\choose l_1$ ways \\
Step 2& Choose balls for second bin & $n-l_1 \choose l_2$ ways\\
&$\vdots$ & $\vdots$
\end{tabular}

This gives the total as: \[ {n\choose l_1} {n-l_1 \choose l_2} \cdots { l_k \choose l_k} \]

Alternatively, we can just arrange the objects, of which there are $n!$ ways. Then we can view the first $l_1$ block as the first bin, the next $l_2$ block as the second, etc. But we need to mod out by placement in the bin, as things in a bin are unordered. This gives $\frac{n!}{l_1\cdot l_2 \cdot \cdots \cdot l_k}$, which is the same as the above.

\begin{eg}
There are three dorms, 1, 2, and 3, and one hundred students. The first dorm can house 25 while the second houses 35 and the third 40. How many ways are there to fill the dormitory? What is there are fifty men and women and 1 is all men, 2 is all female, 3 is coed?

\Hide{2in}{
Notice there are just enough spots to place people. So, we just make a ball for each person, and we want $25$ in first, $35$ in next, and $40$ in the last. So this makes the total $100 \choose {25, 35, 40}$ 

For the other part, we need to divide up the men into two groups of $25$, the first will live in the all male dorm, and the second will live in the coed dorm. This is $50\choose {25, 25}$. Then we need to do the same for the women, which is $50\choose {35,15}$. So the total is the product of these two thing: ${50\choose{25,25}}\cdot{50\choose{35,15}}$
}
\end{eg}

\begin{eg}
A group of $m\cdot n$ people arrange into $m$ teams, each with $n$ members. How many ways can they do this if the teams have names? What if the teams don't have names?

\Hide{1.5in}{
Well, if the teams have names this is just putting $m\cdot n$ balls into $m$ bins, each bin is a team and each ball a player. The bins all have size $n$. This is clearly $\frac{(mn)!}{(n!)^m}$. 

If the teams don't have names then the order of the teams also didn't matter in the above, so we need to mod out by that. Then we get $\frac{(mn)!}{(n!)^m m!}$
}
\end{eg}

\begin{eg}
How many ways can you permutate the letters of MISSISSIPPI?

\Hide{1in}{
Each ball is a position of the word (there are 11 positions, so 11 balls). And the bins represent the letters. We need 1 ball in M, 4 in S, 2 in P, and 4 in I. So the answer is ${11 \choose {1,4,2,4}}$
}
\end{eg}

\subsection{Binomial and Multinomial Theorem}

\begin{thm}
We have that 
\[
(x+y)^n = {n\choose n} x^n + {n\choose n-1} x^{n-1} y + {n\choose n-2} x^{n-2}y^{2} + \cdots + {n\choose 2} x^2 y^{n-2} + {n\choose 1} x y^{n-1} + {n\choose 0} y^n
\]
\end{thm}
\begin{proof}
Consider the process of multiplying this term
\[
\underbrace{(x+y)(x+y)\cdot (x+y)}_{n-\mbox{many}}
\]
We ask what the coefficent of $x^ky^{n-k}$ is. Well, when distributing, getting this amounts to chosing the $x$ term in $k$ of the binomials, and $y$ in the others. There are $n\choose k$ number of ways to do this. 
\end{proof}

\begin{eg}
With this we can do some simple expansions.
\[
(x-y)^4 = x^4 + 4(-y)x^3 + {4\choose 2}(-y)^2x^2 + 4(-y)^3x + (-y)^4
\]
One can check ${4\choose 2} = 6$. So the above is $x^4 - 4yx^3+ 6x^2y^2 - 4y^3x + y^4$. 
\end{eg}

\begin{thm}
Consider the expansion of the multinomial $(x_1+x_2+\cdots +x_k)^n$. Then the coefficent of $x_1^{l_1} x_2^{l_2} \cdots x_k^{l_k}$ is
\[
n \choose {l_1 , l_2 , \ldots , l_k}
\]
\end{thm}
\begin{proof}
Similar as the binomial
\end{proof}

\end{document}
