\documentclass[12pt]{article}
\input{macros-course}

\askaboutsolutions

\begin{document}

\ifshowsolutions
  \psetsol{9}{November 7, 2001}{\stamp}
\else
  \pset{9}{October 29, 2001}{Monday 11/5, beginning of lecture}{\stamp}
  \collaborationnote
\fi

\reading \href{http://theory.lcs.mit.edu/classes/6.042/fall01/lectures/l9.pdf}
{Week 9 Notes}.  Rosen \S 4.3, 4.6, 5.6.

In all the following problems where you are asked how many possibilities
there are, it is ok to answer with a simple expression involving
factorials and binomial or multinomial coefficients instead of an actual
number.

\begin{problems}

%source: spring00 ps7
% ps7 : f95 : 2
\problem On a set of $n$ elements how many of the following are there:
\bparts

\ppart binary relations? 

\solnospace{$2^{n^2}$ since there are this many
  different 0-1-matrices of order $n$.}

\ppart symmetric binary relations?
 
\solnospace{The matrix associated with
  a symmetric relation is symmetric.  Since there are
\[
2^{n+\binom{n}{2}}
\]
  different symmetric matrices there are an equal number of symmetric
  relations.}

\ppart reflexive binary relations?
 
\solnospace{The matrix associated with a
  reflexive relation has $1$'s along the main diagonal . Hence the
  number of such matrices, and therefore reflexive relations, is
\[
2^{n^2 - n}.
\]}

\ppart symmetric and reflexive binary relations? 

\solnospace{The matrix
  associated with a symmetric and reflexive relation is symmetric and
  has $1$'s along the main diagonal.  Hence the number of such
  relations is
\[
2^{\binom{n}{2} }.
\]}

\ppart symmetric or reflexive binary relations?

\solnospace{The number of symmetric or reflexive relations equals the
number of reflexive relations plus the number of symmetric relations,
minus the number of reflexive and symmetric relations:
\[
2^{n^2 - n} + 2^{n+\binom{n}{2}} - 2^{\binom{n}{2}}.
\]
}

\eparts

%source: spring00 ps7-5
% source: spring95 ps7
% topic: basic combinatorics, stars and bars
\problem A pizza house is having a promotional sale. Their commercial
reads:
\begin{quotation}\noindent
Buy $2$ large pizzas at the regular price, and get up to $11$ different
toppings for each pizza absolutely free.  That's $4,194,304$ different
ways to design your order!
\end{quotation}

\iffalse
 $\displaystyle \left( \sum_{k=0}^{11}\binom{11}{k} \right)^2
= \displaystyle \left(2048 \right)^2 = 4,194,304$\fi

The ad writer was a former MIT student who had figured out that
$(2^{11})^2 = 4,194,304$.  Unfortunately, this was a student who got a
\textbf{B-} in 6.042, and the number $(2^{11})^2$ is actually wrong.  In
how many can you really choose toppings for the two pizzas?

\solnospace{The number of ways to choose different toppings for one pizza
is the number of subsets of the set of 11 toppings, which is $2^{11}$.
However, when the student says that there are $(2^{11})^2$ different ways
to choose toppings for two pizzas, he is making the mistake of counting
the combination ``one mushroom and anchovy pizza, and one green-pepper
pizza" as different from the combination ``one green-pepper pizza and one
mushroom and anchovy pizza ."  (At least he knew enough not to count a
mushroom and anchovy pizza as different from an anchovy and mushroom
pizza---that's why he got a \textbf{B-} and not a \textbf{C}.)

The right solution is
\[
2^{11}+\binom{2^{11}}{2} = 2,098,176,
\]
namely, the number of ways to choose the same toppings for both pizzas
plus the number of ways to choose $2$ pizzas with different sets of
toppings.}

\iffalse
%source: spring00 ps7-5
% source: spring95, ps7
% topic: basic combinatorics
\problem 
\bparts
\ppart How many ways can $2n$ people be divided into $n$ pairs?

\solnospace{
\[
\frac{(2n)!}{n! 2^n}.
\]

Consider all the ways of ordering the $2n$ people in a line. There are
$(2n)!$ ways of doing this. Now group them into pairs based on the
linear order, i.e. group the first and second persons, group the third
and fourth persons,..., group the $(2n-1)$th and $2n$th persons. Thus
each linear order gives us a unique grouping into pairs. But observe
that two different linear orders could give rise to the same grouping
into pairs. So let us now count the number of linear orders that give
rise to the same grouping into pairs. Given a grouping into pairs, to
generate a linear order we need to order each pair (there are $2^n$
ways to do this) and then order the $n$ pairs (there are $n!$ ways to
do this). Hence $n! 2^n$ linear orders give the same grouping into
pairs. Thus the total number of ways $2n$ people can be divided into
$n$ pairs is $ (2n)!/ n! 2^n$.

\iffalse
First we pick $n$ leaders from the $2n$ people. 
There are $\binom{2n}{n}$ ways to do this. 
Then we pair the remaining $n$ people with the $n$ leaders. That gives
us $n!$ different ways for each choice of leaders. However,
$\binom{2n}{n}n!$ will be overcounting, since for any fixed pairing,
we count each pair twice depending on who is the leader.
 So for any valid pairing, we counted it $2^n$ times.
Therefore, the answer should be
 $\displaystyle \binom{2n}{n} n! /2^n$.

\fi
}

\ppart How many ways can you choose $n$ out of $2n$ objects, given that
$n$ of the $2n $ objects are identical?

\solnospace{
The answer is $2^n$, since you can pick any subset from the $n$
nonidentical objects, and make up the rest with the identical ones. And the
number of subsets of $n$ different objects is $2^n$. 
}

\eparts
\fi

\problem  An adequately-prepared 6.042 student has
the following texts:

\begin{itemize}
\item 5 copies of Velleman
\item 2 copies of Rosen, 3rd edition
\item 6 copies of Rosen, 4th edition
\item 4 copies of the Spring '10 Lecture Notes
\end{itemize}

Copies of the same text are indistinguishable.  The student also has
a bookshelf with four distinguishable shelves.  In how many different
ways can the student arrange his texts on his bookshelf?  Assume that
each shelf has enough space to hold all of the texts and that two
arrangements are different if the texts appear in a different order on
a shelf.

\solnospace{Each arrangement of the texts on the bookshelf corresponds to
a sequence of the texts together with three ``dividers''.  The texts on
the first shelf appear in the sequence before the first divider, the texts
on the second shelf appear between the first and second dividers, etc.
Thus, the number of different arrangements is $\displaystyle
\binom{20}{5,2,6,4,3}$.
}

%spring 99 Quiz2 Prob 5

\problem Let $A=\{a_1,a_2,...,a_n\}$ be some set of $n$ items.  Remember
that the number of permutations \emph{with repetition} of the elements of
$A$, where each element $a_i$ is repeated exactly $r_i$ times, is
\[
\binom{r_1+r_2+...+r_n}{r_1, \ r_2, \ ..., \ r_n} ::=
 \frac{(r_1+r_2+...+r_n)!}{r_1!  r_2!  ...  r_n!}
\]

\bparts

\ppart Give a simple algebraic proof that
\[
\binom{a+b+c+d}{a} \binom{b+c+d}{b,c,d} 
 = \binom{a+b+c+d}{d} \binom{a+b+c}{c} \binom{a+b}{b}.
\]

\solnospace{
\begin{eqnarray*}
\binom{a+b+c+d}{a} \binom{b+c+d}{b,c,d} & = &
   \frac{(a+b+c+d)!}{a!\, (b+c+d)!} \frac{(b+c+d)!}{b!\, c!\, d!}\\
& = & \frac{(a+b+c+d)!}{a!} \frac{1}{b!\, c!\, d!}\\
& = & \frac{(a+b+c+d)!}{a!\, b!\, c!\, d!}\\
& = & \binom{a+b+c+d}{a, b, c, d}.
\end{eqnarray*}

Also
\begin{eqnarray*}
\binom{a+b+c+d}{d} \binom{a+b+c}{c} \binom{a+b}{b} & = &
  \frac{(a+b+c+d)!}{d!\, (a+b+c)!} \frac{(a+b+c)!}{c!\, (a+b)!}
  \frac{(a+b)!}{b!\, a!}\\
& = &   \frac{(a+b+c+d)!}{d!} \frac{1}{c!} \frac{1}{b!\, a!}\\
& = & \frac{(a+b+c+d)!}{a!\, b!\, c!\, d!}\\
& = & \binom{a+b+c+d}{a, b, c, d}.
\end{eqnarray*}
}

\ppart Now give a \emph{combinatorial argument} proving this equation.
That is, describe two different procedures for counting the same things,
where the lefthand side of the equation clearly describes the number of
outcomes of the first procedure, and the righthand side the number of
outcomes of the second procedure.

\solnospace{Both expressions equal
\[
\binom{a+b+c+d}{a,b,c,d}
\]
and correspond to choosing a permutation of four kinds of items in
quantities $a,b,c$ and $d$, respectively.  Now the LHS corresponds to
first choosing positions in the permutation for $a$ items of the first
kind, then for $b,c$, and $d$ of the remaining three kinds.  The RHS
corresponds to first choosing $d$ of the fourth kind, then $c$ of the
third kind, and then $b$ of the second kind.}

\eparts


%Spring 99 Quiz2 Prob 6
\problem The \emph{king positioning} in an
arrangement of a deck of 52 playing cards is the sequence of numerical
positions in the deck, from one to 52, of the four successive kings.  For
example, the king positioning $(1,2,3,4)$ means all the kings come at the
beginning of the deck.  The king positioning $(1,18,35,52)$ describes the
situation in which the kings are spaced uniformly---with exactly 16 cards
between successive kings.

\bparts
\ppart How many king positionings are there?

\solnospace{$\dbinom{52}{4}$.}

\ppart How many king positionings are there in which \emph{no two
kings are adjacent}?

\solnospace{Think of kings as bars and the remaining 48 cards as stars.
Place one star between each two adjacent kings (bars).  This requires
three stars and leaves 45 stars that can be placed anywhere; there are
$\dbinom{45+4}{4}$ ways to do this.}

\ppart Of the $52!$ possible arrangements of the deck, how many
have no two kings adjacent?

\solnospace{Now in each of the previous patterns of stars and bars, the
kings can be permuted in $4!$ ways and the remaining cards can be permuted
in $48!$ ways, so the total number of desired arrangements is
\[
\binom{45+4}{4} 48!\, 4! = 49!\, 48!/45! = 48!\, P(49,4).
\]

\iffalse
The form of the RHS suggests that there is another way to do this count,
but I haven't had time to figure what it is.
\fi
}

\eparts

\iffalse

%Fall 99 Final exam Prob 4
\problem 
A juggler plans to juggle 11 rings for his finale.  In his bag are 20
identical red rings, 30 identical blue rings, and 40 identical white
rings.  He must select at least one of each color to be patriotic.  An
example of a patriotic choice of 11 rings would be: 3 red, 2 white, and 6
blue.  How many different patriotic choices are there for the 11 rings?

\solnospace{
This is the same as asking how many ways there are to arrange 11 stars and
two bars such that there is at least one star in each of the three groups
delimited by the bars.  Reserving three stars for this purpose leaves 8
stars and 2 bars, so there are
\[
\binom{8+2}{2} = \binom{10}{2}.
\]
Note that the initial number of red, white, and blue rings available to
the juggler is irrelevant as long as there are at least nine of each.
}
\fi

\iffalse
\problem Find the number of 5-card hands

\begin{problemparts}

\problempart \dots with consecutive values, \eg $8\clubsuit \ 9\heartsuit \
10\diamondsuit \ J\diamondsuit \ Q\spadesuit$.  (An Ace can both precede a
2 (called a ``deuce''), and can also follow a King.  However
``wrap-arounds'' like $J\clubsuit \ Q\heartsuit \ K\diamondsuit \
A\diamondsuit \ 2\spadesuit$ are not allowed.)

\solnospace{There are 9 possible sequences of five consecutive values.
For each sequence, there are $4^5$ hands, since each value can be
represented by one of four different suits.  Therefore, there are a
total of $9 \cdot 4^5$ such hands.}

\problempart \dots with exactly three aces.

\solnospace{ We can choose the three aces in $\binom{4}{3}$ ways, and
we can choose the remaining two cards in $\binom{48}{2}$ ways.  Thus,
there are $\binom{4}{3} \binom{48}{2}$ such hands.}

\problempart \dots in which every suit appears at most twice.

\solnospace{There are two cases.  Either one suit appears twice or else
two suits appear twice.  The number of hands in which one suit appears
twice is $\binom{13}{2} \cdot 13^3 \cdot 4$.  The number of hands in
which two suits appear twice is $\binom{13}{2}^2 \cdot 13 \cdot 12$.
Therefore, there are a total of
\[
\binom{13}{2} \cdot 13^3 \cdot 4 + \binom{13}{2}^2 \cdot 13 \cdot 12
\]
such hands.}

\end{problemparts}
\fi

% a new problem from Zhang Lizhao at Dept of Math Oct 22, 2001

% revised by ARM 10/24/01

\problem There are $n$ students attending their first 6.042 tutorial.  The
TA starts things off by asking everybody to shake hands with everybody
else in the tutorial, including herself.  The TA makes a peculiar
observation: the number of boy-boy handshakes, plus the number of
girl-girl handshakes, happens to equal the number of boy-girl handshakes.
She also also notices that $n+1$ is a perfect square.  Having thoroughly
mastered the 6.042 curriculum, she realizes that $n+1$ must be a perfect
square whenever the numbers of boy-boy, girl-girl, and boy-girl handshakes
are related in this way.  Explain how the TA could have reached this
conclusion.

\solnospace{Let $b$ be the number of boys, and $g$ the number of girls
(including the TA), so $b+g=n+1$.  The condition says
\begin{align*}
\binom{b}{2} + \binom{g}{2}& = bg, & \text{so}\\
b(b-1) + g(g-1)& = 2bg\\
b^2 -b +g^2 -g& = 2bg\\
b^2 -2bg +g^2& = b+g\\
(b-g)^2& = n+1.
\end{align*}
So indeed, $n+1$ is a perfect square.
} 


\problem Let $\set{\mathtt{0},\mathtt{1}}^n$ be the set on length-$n$
binary strings, where $n>1$.  Let $A_i$ be the set of length-$n$ strings
that have a \texttt{1} in their $i^{th}$ position.

\begin{problemparts}

\problempart What is the cardinal of the intersection of $k$ of the sets
$A_1,A_2,\dots$?

\solnospace{$2^{n-k}$, namely, the number of length-$n$ strings that have
a \texttt{1} in $k$ designated positions.}

\problempart Using the inclusion-exclusion principle, prove that 
\begin{equation}\label{iesum}
\sum_{k=1}^{n} \frac{(-1)^{k+1}\binom{n}{k}}{2^k} = 1 - \frac{1}{2^n}
\end{equation}

\solnospace{
The inclusion-exclusion principle gives:
\begin{eqnarray*}
2^n - 1 &=& \card{\lgunion_{j=1}^{n} A_{i}}\\
	&=& \sum_{\emptyset \neq S \subseteq \set{1,\dots,n}} (-1)^{\card{S}+1}
				\card{\bigcap_{i \in S} A_{i}} \\
        &=& \sum_{\emptyset \neq S \subseteq \set{1,\dots,n}} (-1)^{\card{S}+1} 2^{n-\card{S}}\\
	&=& \sum_{k=1}^{n} (-1)^{k+1} \binom{n}{k} \frac{2^n}{2^k},\\
\end{eqnarray*}
and now equation~(\ref{iesum}) follows by dividing the expressions above
by $2^n$.}

\end{problemparts}


\iffalse

%source: spring00 ps7
\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?

\solnospace{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: $ \binom{14}{1} \binom{8}{5}$\\
2 hackers, 4 theoreticians: $ \binom{ 14}{2} \binom{8}{4}$\\
3 hackers, 3 theoreticians: $ \binom{ 14}{3} \binom{8}{3}$\\
4 hackers, 2 theoreticians: $ \binom{ 14}{4} \binom{8}{2}$\\
5 hackers, 1 theoretician: $ \binom{ 14}{5} \binom{8}{1}$\\
6 hackers, 0 theoreticians: $ \binom{ 14}{6} \binom{8}{0}$\\

So there are
\[
\binom{14}{1} \binom{8}{5} + \binom{14}{2} \binom{8}{4} + \binom{14}{3}
\binom{8}{3} + \binom{ 14}{4} \binom{8 }{2} + \binom{ 14}{5} \binom{8}{1}
+ \binom{14}{6} \binom{8}{9}
\]
different possibilities for committees.

Another way to solve this problem is to say that there are
$\binom{22}{6}$ different committees, and $\binom{8}{6}$ committees
of just theoreticians.  So there are $\binom{22}{6} - \binom{8}{6}$
different possibilities for committees.  }
\fi


\end{problems}

\end{document}
