% This is a simple LaTex sample document that gives a submission format
%   for IEEE PAMI-TC conference submissions.  Use at your own risk.

% Make two column format for LaTex 2e.


\documentclass[11pt]{article} %
\usepackage[dvips]{graphicx,graphics,color}
\usepackage{times,amsmath,amsfonts}

\setlength{\textheight}{10in} \setlength{\textwidth}{6.875in}
\setlength{\columnsep}{0.3125in} \setlength{\topmargin}{-0.5in}
\setlength{\headheight}{0in} \setlength{\headsep}{0in}
\setlength{\parindent}{1pc}
\setlength{\oddsidemargin}{-.2in}  % Centers text.
\setlength{\evensidemargin}{-.2in}

% Add the period after section numbers.  Adjust spacing.
\newcommand{\Section}[1]{\vspace{-8pt}\section{\hskip -1em.~~#1}\vspace{-3pt}}
\newcommand{\SubSection}[1]{\vspace{-3pt}\subsection{\hskip -1em.~~#1}
        \vspace{-3pt}}
\newcommand{\bqn}{\begin{eqnarray}}
\newcommand{\eqn}{\end{eqnarray}}
\newcommand {\diff}[1] {\frac{\partial}{\partial #1}}
\newcommand{\jacob}[3]{\frac{\partial^2 #3}{\partial #1 \partial #2}}
\newcommand{\der}[2]{\frac{\partial #2}{\partial #1}}
\begin{document}

% Don't want date printed
\date{January 25, 2005}

% Make title bold and 14 pt font (Latex default is non-bold, 16pt)
\title{Stat 324: Lecture 03\\
Combinatorics}

% For single author (just remove % characters)
\author{Moo K. Chung\\
mchung@stat.wisc.edu}

% For two authors (default example)
\maketitle \thispagestyle{empty}
\begin{enumerate}

\item Given $n$ distinguishable objects $x_1,\cdots,x_n$,
{\em permutation} is a rearrangement of the $n$ objects. There are
$n!$ different rearrangements. {\em Combination} is a way to choose
$k$ distinct objects out of the $n$ objects. There are ${n \choose
k}$ different combinations. The notation is called {\em n choose k}.

\item {\em Binomial identity} $\sum_{k=0}^n {n \choose k} = 2^n$.


\item {\em Problem.} A fair coin is tossed independently $n$ times($n > 3$).
Find the probability that we get 2 heads and $n-2$ tails.\\


\item {\em Problem.} A fair coin is tossed independently $n$ times ($n > 3$).
Find the probability at least three of tosses yield heads.\\
{\it Solution.} Let $X$ be the number of heads.
\bqn P(X \geq 3) = 1 - P(X <3) &=&1-P(X=0)-P(X=1)-P(X=2)\\
&=&1- \frac{1}{2^n}-{n \choose 1}\frac{1}{2^n} - {n \choose
2}\frac{1}{2^n}. \eqn


\item If $n$ identical balls are placed at random into $n$ distinct boxes, find
the probability that exactly one box remains empty.\\
{\it Solution.} Let A be the empty box, B the box containg two balls
and C's $n-2$ boxes containing one ball. There are $2{n \choose 2}$
ways of arranging the letter sequence $ABC\dots C$. The size of the
sample space is ${n+n-1 \choose n}$ since it is equavalent to the
number of ways of placing  $n$ 0's and $n-1$ 1's in order. So the
probability is $\frac{n(n-1)}{{2n-1 \choose n}}$.


\item If $n$ identical balls are placed into $n-1$ distinct boxes
so that each distinguishable arrangement is equally likely.
Find the probability that no box remains empty.\\
{\em Solution.} Let $A$ be the box containing two balls and $B$'s
$n-2$ boxes containing one ball. There are $n-1$ ways of arranging
the letter sequence $AB \cdots B$. The size of the sample space is
${{n + n-2} \choose n}$ since it is equivalent to the number of ways
of placing $n$ 0's and $n-2$ 1's in order. We expect the equal
probability for each sample point. So the probability is
$\frac{n-1}{{2n-2 \choose n}}$.


\end{enumerate}

{\bf Assigned Problems}

\end{document}