% 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,twocolumn]{article} %
\usepackage[dvips]{graphicx,graphics,color}
\usepackage{times,amsmath,amsfonts}
%\usepackage{pancyhdr}
\setlength{\textheight}{10.5in} \setlength{\textwidth}{7in}
\setlength{\columnsep}{0.3in} \setlength{\topmargin}{-0.5in}
\setlength{\headheight}{-0.2in} \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{\bq}{\begin{eqnarray*}}
\newcommand{\eq}{\end{eqnarray*}}


\begin{document}

% Don't want date printed
% Make title bold and 14 pt font (Latex default is non-bold, 16pt)

\title{Stat 311-Lecture 02, Combinatorics}
% For single author (just remove % characters)
%\author{\Large Probability}
\vspace{-2cm}
\date{ }
% For two authors (default example)
\maketitle \thispagestyle{empty}

Sept 13, 2005


\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$ objects out of the $n$
distinct objects. There are ${n \choose k}$ different combinations.
The notation is called {\em n choose k}.

\item {\em Binomial identities}

$$\sum_{k=0}^n {n \choose k} = 2^n.$$
$$\sum_{k=0}^n n{n \choose k} = n2^{n-1}.$$


\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.}
\bq & & P(\mbox{ at least 3 H's}) =1 - P(\mbox{ at most 2 H's})\\
&=&1- \frac{1}{2^n}-{n \choose 1}\frac{1}{2^n} - {n \choose
2}\frac{1}{2^n}. \eq


\item If $n$ identical balls are placed at random into $n$ distinct boxes, find
the probability that exactly one box remains empty.\\
{\it Solution.}  The size of the sample space is ${n+n-1 \choose n}$
since it is equivalent to the number of ways of arranging  $n$ 0's
and $n-1$ 1's.


Let A be the empty box, B the box containg two balls and C's $n-2$
boxes containing one ball. There are $n!/(n-2)!$ ways of arranging
the letter sequence $ABC\dots C$. 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.} The size of the sample space is ${{n + n-2} \choose
n}$ since it is equivalent to the number of ways of arranging $n$
0's and $n-2$ 1's.

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$. So the probability is $\frac{n-1}{{2n-2
\choose n}}$.

\end{enumerate}

{\bf Homework 1.} Due date Sept 20 8:00am. Since most of problems
has the answers in the textbook, the homework will be graded based
on the correctness of your derivation rather than the correctness of
your answer. Solve the following 8 problems. Chapter 1, Problem 16.,
17., 20.  Theoretical Exercise 5; Chapter 2, Problem 2., 8., 45.,
Theoretical Exercise 19.

\end{document}