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

%\hidesolutions         
%\showsolutions

\begin{document}
\inclassproblems{8M}

\begin{verbatim}
MONDAY LECTURE:
=================
topics: division rule, combinations

- motivation (learned how to count many complex things already, but
still many things we can not count with the tools we have so far. List
examples)

- road map for the week

- describe combinations.
- use it to count a poker hand (or compare two)
- EXERCISE: false proof

- talk more about combinations, especially as related to permutations
(emphasize the close relationship between the two, for example P(A) is
equal to 2^n but also can count with combinations, results in an
identity.

- empahisize intuition behind it: (n choose n) (n choose 1)...simple
  cases.

- possible problems
* false counting
* engish vowels (combinations and product rule)
* pig paths (division rule, also rosen 4.3.55 bijection with strings)
* rotations
* possibly hard problem on 3-colorability
%%-------------------------------------------------------%%

WEDNESDAY LECTURE:
====================
15 minutes MAGIC TRICK
10 minutes explain the trick
10 minutes work on 2,9 generalization (?)
10 minutes explain why can't do it with 4 cards, Halls theorem
---
45 minutes already...
---

q3 problem?

Permutations with Repetition (Product Rule, Multinomial Coefficients)
Combinations with Repetition (Stars-n-Bars)
- what is wrong with n^r/r! (why can't we solve stars n bars just as
we solved permutations...not a r! mapping, can not use the division rule)

-Possible problems
* BOOKEEPER / MISSISSIPPI follow up question.
%%-------------------------------------------------------%%

FRIDAY  LECTURE:
=================
Binomial Theorem and Identities

Overall picture:
- Sets (Sum rule, inclusion exclusion)
- Product Rule 
- Permutations (rearrangements, r-permutations)
- Combinations (binomial coefficients, subsets of size r)
- Permutations with limited repetition (multinomial coefficients)
- Combinations with repetition (Stars-n-Bars)
- Trees

Balls n Bins table. 
Balls n Bins tutorial example.
%%-------------------------------------------------------%%

\end{verbatim}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage
{\bf MONDAY LECTURE}

% false proof (cards from notes).

% Simple listing A ={a,b,c}
% how many 2 letter strings (list them)
% how many 2 letter permutations (list them)
% how many 2 letter combinations (list them)

% english vowels (combinations and product)
% select a committee (simple, but combinations, women,en or hackers)

% pig walk (pset 9 fall01), division rule.
% my 3-colorability question? (division rule..)
% also pizza counting false proof, with starsnbars extra piece.

\begin{problem}
ADD PROBLEM: FALSE PROOF
\end{problem}

% source: spring00 ps7
% topic: combinations
\begin{problem}
Fourteen hackers and eight theoreticians are on the faculty of a
school's EECS department.  The individuals are distinguishable.  How
many ways are there to select a committee of six members if at least 1
hacker must be on the committee?  You may express this in terms of
binomial coefficients.
  
\solution{We need to count all possible combinations of people such
    that there is at least one hacker in every combination, but we must
    remember not to count any combinations multiple times.
    
    We can have committees with
    
    1 hacker, 5 theoreticians: $ { 14 \choose 1} {8 \choose 5}$\\
    2 hackers, 4 theoreticians: $ { 14 \choose 2} {8 \choose 4}$\\
    3 hackers, 3 theoreticians: $ { 14 \choose 3} {8 \choose 3}$\\
    4 hackers, 2 theoreticians: $ { 14 \choose 4} {8 \choose 2}$\\
    5 hackers, 1 theoretician: $ { 14 \choose 5} {8 \choose 1}$\\
    6 hackers, 0 theoreticians: $ { 14 \choose 6} {8 \choose 0}$\\
    
    So there are $ { 14 \choose 1} {8 \choose 5} + { 14 \choose 2} {8
      \choose 4} + { 14 \choose 3} {8 \choose 3} + { 14 \choose 4} {8
      \choose 2} + { 14 \choose 5} {8 \choose 1} + { 14 \choose 6} {8
      \choose 9}$ different possibilities for committees.
    
    Another way to solve this problem is to say that there are ${22
      \choose 6}$ different committees, and ${8 \choose 6}$ committees
    of just theoreticians.  So there are ${22 \choose 6} - {8 \choose
      6}$ different possibilities for committees.
}
\end{problem}

% source: old
% last used: fall 01 pset (similar version, but not same)
% topics: division rule, bijections
\begin{problem}
\begin{problemparts}
\problempart Suppose that Theory Pig starts at position $(0, 0)$.  At
any time, he can step north (incrementing the first coordinate) or
step east (incrementing the second coordinate).  In how many different
ways can he reach position $(n, n)$, where $n$ is a non-negative
integer?

\solution{Theory Pig must take $2n$ steps in total.  Of these, he must
choose a subset of $N$ to be north steps.  This gives $\binom{2n}{n}$
different ways to reach $(n, n)$.}

\problempart How many different ways are there to list the numbers $1,
2, \ldots, 2n$ such that the even numbers appear in increasing order
and the odd numbers appear in decreasing order?

\solution{ There are $(2n)!$ ways to list the numbers $1, 2, \ldots,
n$.  We can define a $n!$-to-1 mapping that takes an arbitrary listing
to a listing in which the even numbers are sorted in increasing order
and the odd numbers remain as before.  Thus, by the quotient rule
there are $(2n)!/n!$ listings in which the even numbers appear in
increasing order.  Similarly, we can define an $n!$-to-1 mapping that
takes a listing in which the even numbers appear in increasing order
and the odd numbers are in an arbitrary order to a listing in which
the even numbers appear in increasing order (as before) and the odd
numbers appear in decreasing order.  Therefore, there are

\begin{eqnarray*}
\frac{(2n)!}{n! \ n!} & = & \binom{2n}{n}
\end{eqnarray*}

listings in which the even numbers are increasing and the odd numbers
are decreasing.
}

\problempart Describe a bijection that maps each one of Theory Pig's
paths to a listing of the numbers $1, 2, \ldots 2n$ with even numbers
increasing and odd numbers decreasing.

\solution{Each time Theory Pig take a step north, write down an even
number, starting with 2 and working up.  Each time Theory Pig takes a
step east, write an odd number, starting with $2n-1$ and working down.}
\end{problemparts}
\end{problem}


% new: RAD
\begin{problem}
A possible algorithm for checking if a graph is 3-colorable is to
enumerate all possible 3 color assignments to the nodes of the graph
and then test each assignment to see if it is a valid coloring
(reminder a valid coloring is one where no two adjacent vertices have
the same color).

Let $G$ be a $n$ node graph with vertices labelled $v_1$ through
$v_n$. Let the set of colors $C=\{R,G,B\}$.

\begin{problemparts}
\problempart In how many different ways can you assign colors from $C$
to the nodes of $G$?

\solution{$3^n$}

\problempart Enumerate all the possible color assignments for a 3-node
graph with vertices $v1,v2,v3$ using the colors $C$.

\problempart There are much easier ways to check if a graph can be
colored with one color or two colors. Therefore we are really only
interested in color assignments that use {\em exactly} 3 colors. How
many such color assignments are there?

\solution{Need to substract $\leq 2$ color assignments from the total
number of $\leq 3$ color assignments from part (a). There are three
sets of two colors RG, RB, BG. For any set, the number of possible
color assignments is $2^n$. So the total number of assignments that
use exactly 3 colors is $3^n - 3.2^n$. VERIFY}

%% BETTER IDEA: easy to check 1 colors and 2 colorability therefore I
%% am actually only interested in color assignments with exactly 3
%% colors. How many color assignments are there that use exactly three
%% colors?

%% Then remove the redundant colors...but only for the three case
%% (division rule)

\noindent A valid 3-coloring of a graph is a assignment of three
colors to the nodes such that no two adjacent nodes have the same
color. One algorithm for determining whether the graph $G$ can be
colored with 3 colors is to test all possible 3 color
assignments. However several of the assignments from above are
redundant. For example, for a 4-node graph with nodes $v_1, v_2, v_3,
v_4$, the color assignment $RRRR$ is the same as the color assignment
$GGGG$ or $BBBB$. Similarly the color assignment $RGRG$ is the same as
assigning the nodes the colors $GRGR$, $BRBR$, $RBRB$, $GBBG$,
$BGGB$. By the ``same'' we mean that if one assignment is not valid,
the other ones are guaranteed to fail. In general a color assignment
is redundant, if we already checked another assignment than can be
acheived by swapping the names of the colors.


\problempart For a 3-node graph with vertices $v1,v2,v3$ , list all
possible color assignments. List only the non redundant color
assignments

\problempart (*\footnote{I do not know the solution to this
problem. It actually looks quite hard. But that's just my first
assesment, I may be wrong...} Count the number of different ways can
you assign colors from $C$ to the nodes of $G$, after removing all
redundant mappings as described above?

\solution{
Still in the works...
}

\problempart Test your answer to part (b) for a three node graph. (In
other words, list the number of non-redundant RGB colorings and see if
your answer from above yields the same number. This is a good strategy
for checking parameterized answers.)

\solution{
}
\end{problemparts}
\end{problem}

% source: spring00 ps7-5
% source: spring95 ps7
% topic: basic combinatorics, stars and bars
\begin{problem}
REPLACE WITH FALL01 PSET VERSION?  A pizza house is having a
promotional sale. Their commercial reads: ``\ldots buy $2$ large
pizzas at regular price, get up to $11$ different toppings for each
pizza absolutely free. That's $4,194,304$ different ways to design
your order! \ldots''
\newline
\emph{Note:} $\displaystyle \left( \sum_{k=0}^{11}{11 \choose k} \right)^2
= \displaystyle \left(2048 \right)^2 = 4,194,304$

\begin{problemparts}

\problempart Show that $4,194,304$ is actually wrong and give the
right answer for the number of ways that you can choose toppings for
the two pizzas.

\solution{ The number of ways to choose different toppings for one
pizza is clearly $A \equiv \displaystyle \sum_{k=0}^{11}{11 \choose k}
= 2^{11} = 2,048$.  However, when they say there are $A^2$ different
ways to choose toppings for two pizzas, they are making the mistake of
counting the combination ``one mushroom pizza, and one cheese pizza''
as different from the combination ``one cheese pizza, and one mushroom
pizza.''

The right solution is $ \displaystyle A+{A \choose 2} = \frac{1}{2}
(A^2+A) = 2,098,176 $, where $A$ is the number of ways to choose $2$
pizzas with the same toppings, and ${A \choose 2} $ is the number of
ways to choose $2$ different pizzas.  }

%To clarify, a valid choice of 2 pizzas
%does not allow multiple copies of the same topping on the same pizza, and does
%not require that the two pizzas themselves be distinct.
%comment on the fact that ordering of the 2 pizzas obviously doesn't matter???
%\solution{
%The problem double counts some pairs of pizzas, as ordering does not matter.
%For instance, a ``pepperoni pizza and a mushroom pizza'' is counted 
%differently from a ``mushroom pizza and a pepperoni pizza.''
%\newline
%Once you have your total number of possible single pizza types, you must 
%choose any two of them, allowing repition.
%\newline
%The correct formula is $\displaystyle { {\left( \sum_{k=0}^{11}{11 \choose k} 
%\right) + 2 - 1} \choose 2}$, which gives \bf{NEED TO FILL IN} combinations.
%}

\problempart  Now assume that you can choose any number of the same 
topping as long as the total number of toppings is no more than $11$.
(That is, you can have $2$ meatball, $4$ ham and $5$ sausage toppings if 
you are truly a meat lover.) How many different ways can you now choose
toppings for your two pizzas?

\solution{ For a single pizza, this is the ``stars and bars'' problem
in disguised form.  If $k$ is the total number of toppings you want on
a pizza then the number of ways of throwing $k$ identical balls into
$11$ bins is identical to choosing a total of $k$ toppings out a total
of $11$ different topping-possibilities.

Hence the number of ways to order one pizza is $B \equiv \displaystyle
\sum_{k=0}^{11}{10+k \choose k} = {22 \choose 11} = 705,432$.  Using
the same argument as in part (a), we see that the number of ways to
order two pizzas is $\displaystyle B+ {B \choose 2}=\frac{B^2+B}{2} =
248,817,506,028$.  }

\end{problemparts}
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
{\bf WEDNESDAY LECTURE}

% Magic Trick with 9?
% q3 hall's theorem?

% MISSISSIPI Reading Problem (full) (prprob 9 fall01), 
% (permutations w repetitions)
% one more problem with combinations with repetition
% donuts, pizza ??

\begin{problem}
ADD PROBLEM: MAGIC TRICK, guessing 2 cards out of nine (fall 99)
\end{problem}

\begin{problem}
ADD PROBLEM: Q3 Problem on Hall's Theorem (calculate maximum size deck)
\end{problem}

\begin{problem}
ADD PROBLEM: PRPROB 9 FALL 01 How many different ways are there to
reaarnge MISSISSIPI, select a general formula.
\end{problem}

% Topics: Stars and Bars
% last used Fall 01 tutorial 9
% pset7 problem8 spring98, exercise $4.6-42$ of Rosen.
\begin{problem}
A shelf holds 13 books in a row. How many ways are there to choose
five books so that no two adjacent books are chosen?

\solution{There are 5 bars (chosen books), and therefore there are 6
places where the 8 stars (non-chosen books) can fit (before the first
bar, between the first and second bars,..., after the fifth bar).
Each of the second through fifth of these slots must have at least one
star in it, so that adjacent books are not chosen. Once we have placed
these 4 stars, there are 4 stars left to be placed in 6 slots. The
number of ways to do this is therefore ${{6+4-1}\choose{4}}={9\choose
4}=126$.}
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
{\bf FRIDAY LECTURE}

% From fall 01:
% Balls and Urns example. OVERALL
% Binomial Identity (Harvard CFO)

% other combinations with repetitions (donuts, pizza)?
% assign the polynomial example

% hard question: out of 2n people how many n pairs are possible, how
% to choose n from 2n if n things are identical.

%%----------------------------------------------------------

% Last Used Fall 01 tutorial 9
% pset7 problem4 spring98, from M&R, # 4.7.5
% balls n urns (all types)
\begin{problem}
How many ways can 4 balls be placed in 4 urns if 

\begin{problemparts}
\problempart both the balls and the urns are distinguishable;

\solution{
$4\cdot 4\cdot 4\cdot 4 =256$.
}

\problempart the balls are distinguishable but the urns are not;

\solution{ 15.  We can put either all 4 balls in one urn; or 3 in one,
1 in another; or 2 in one, 2 in another; or 2 in one, 1 in one and 1
in another; or 1 ball in each urn.  The balls are distinguishable, so
there are $4\choose 3$ ways of putting 3 in one urn.  There are
$4\choose 2$ ways of putting 2 in one and 1 in each of the other two.
There are ${4\choose 2}/2$ ways of putting 2 in one and 2 in
another. Since the urns are indistinguishable, the case where all the
balls are placed in the same urn and the case where each ball is
places in a different urn are unique.  So the total number of ways is
\[
1 + {4\choose 3} + \frac{1}{2}{4\choose 2} + {4\choose 2} + 1 = 15.
\]
}

\problempart the urns are distinguishable but the balls are not;

\solution{35. This is a stars and bars problem with the balls being
stars and the urns bars.  The answer is ${4+4-1 \choose 4} = {7
\choose 4} = 35$.}

\problempart neither the balls nor the urns are distinguishable.

\solution{5.
This is the number of ways to partition a multiset $\{1,1,1,1\}$
of 4 indistinguishable objects into 4 (possibly empty) subsets.
We can either put
$\{1,1,1,1,\}, \emptyset, \emptyset, \emptyset$ or
$\{1,1,1\}, \{1\}, \emptyset,\emptyset$, or
$\{1,1\}, \{1,1\},\emptyset,\emptyset$, or
$\{1,1\}, \{1\}, \{1\}, \emptyset$, or
$\{1\},\{1\},\{1\},\{1\}$.
The ordering in which we list the subsets doesn't matter because
the urns are indistinguishable.
}

\end{problemparts}
\end{problem}

\begin{problem}
ADD PROBLEM FROM TUTORIAL 9 FALL 01, ON THE IDENTITY
(n m) (m k) = (n k) (n-k m-k)
\end{problem}

\begin{problem}
ADD PROBLEM: king positioning (pset9 fall01, old tutorial),
combinations, but also startsnbars [WHY IS THIS NOT IN COUNTING?]
\end{problem}


\begin{problem} Solve the following counting problems, and
explain your answers.

\begin{problemparts}
\problempart Determine the number of solutions to the equation $x_1 +
x_2 + \ldots + x_n = r$, where all variables are non-negative
integers.

\solution{Each solution to the equation corresponds to a string of $r$
stars and $n-1$ bars.  The correspondence is illustrated by the
example below, where $n = 4$ and $r = 6$.

\[
\begin{array}{ccccccccc}
\star \star \star & \mid & \star & \mid & & \mid & \star \star \\
3 & + & 1 & + & 0 & + & 2 & = & 6
\end{array}
\]

Therefore, the number of solutions is
\[
\binom{n + r - 1}{r}.
\]
}

\problempart Determine the number of sequences of $k$ integers in the
range $0$ to $n$ that are {\em increasing}; that is, each integer in
the sequence is greater than or equal to the one before.

\solution{Each sequence corresponds to a string of $n$ stars and $k$
bars.  The correspondence is illustrated below, where $k = 4$ and $n =
7$.

\[
\begin{array}{ccccccccc}
\star \star \star & \mid & \star & \mid & & \mid & \star \star & \mid & \star\\
3 &,& 4 &,& 4 &,& 6
\end{array}
\]

As the example illustrates, the $k$-th number in the sequence is equal
to the total number of stars preceding the $k$-th bar.  Therefore, the
number of sequences is
\[
\binom{n + k}{k}.
\]
}

\end{problemparts}
\end{problem}



\begin{problem}
% STAS: change of exercise 23 from Rosen 4.3 to r-permutations

The English alphabet contains $21$ consonants and five vowels.
Suppose that all strings of six English alphabet characters with no
repetitions were English words.  How many such words contain:

\begin{problemparts}

\problempart exactly $1$ vowel?
\problempart exactly $2$ vowels?
\problempart at least $1$ vowel?
\problempart at least $2$ vowels?

\end{problemparts}

\solution{
\begin{enumerate}
\item[{\bf (a):\ }]

$P(21,5)\cdot5\cdot6=(21\cdot20\cdot19\cdot18\cdot17)\cdot30=73,256,400$:
A choice of $5$ consonants with no repetition, a choice of a vowel,
and a choice of vowel's position.

\item[{\bf (b):\ }]
 
$P(21,4)\cdot(5\cdot4)\cdot(6\cdot5/2)=
(21\cdot20\cdot19\cdot18)\cdot20\cdot15=
43,092,000$: A choice of $5$ consonants with no repetition, a choice
of $2$ vowels, and a choice of the vowels' positions.

\item[{\bf (c):\ }]

$P(21+5,6)-P(21,6)=21\cdot6,033,120=126,695,520$: All words minus
words with no vowels.

\item[{\bf (d):\ }]

$P(21+5,6)-P(21,6)-P(21,5)\cdot5\cdot6=
126,695,520-73,256,400=53,439,120$: As above minus part (a).

\end{enumerate}
}
\end{problem}


\end{document}



