\documentclass[11pt,twoside]{article}
\usepackage{epsf}
\input{macros-course}


\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}

\askaboutsolutions

\begin{document}
\pset{8}{October 31, 2000}{2:35PM in lecture, Tuesday, November 7, 2000}
\textbf{Be sure to indicate your TA's name clearly on the solutions
your turn in}.

-----------------------------------------------------------------------------\\

\textbf{Self-study}
%[[[George:  I couldn't think of any new basic material they should
%review this week.  So, I just put in simple stuff on the product
%rule.]]]

Read: Rosen Section 4.1
Self-study problems (not to be handed in): Exercises 1, 3, 5, 7, 9,
11, 15, 17

%[[[Miniquiz: 15]]]

-----------------------------------------------------------------------------\\

\textbf{Reading:}
Lecture notes;  Rosen 4.1, 5,3, 5.5, 5.6

\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should
 mention their names on top of the problem set. If you did not
 collaborate with anyone, you should explicitly say so. As a reminder,
 the write-up of your solutions should be entirely your own.
 
\medskip
\begin{problems}
\problem %(5 points)
% Inclusion-exclusion

In a survey of 270 college students, it is found that:
\begin{itemize}
\item 64 like brussels sprouts
\item 94 like broccoli
\item 58 like cauliflower
\item 26 like both brussels sprouts and broccoli
\item 28 like both brussels sprouts and cauliflower
\item 22 like both broccoli and cauliflower
\item 14 like all three vegetables
\end{itemize}

How many students do not like ANY of the aforementioned vegetables?

\solution{
\medskip
\textbf{Solution:}
\medskip
By the direct application of the Principle of Inclusion-Exclusion, the union of sprouts-lovers, cauliflower-lovers, and broccoli-lovers will be of size:
$64+94+58-26-28-22+14=154$
Therefore, the remaining $270-154=116$ students don't like any of the three vegetables.
}

\problem %(15 points)
% Inclusion-exclusion
% Modified from Rosen 5.6, number 17 and the preceding problems on
% derangements.

\ppart
In how many ways can the natural numbers $0,1,2,3,4,5,6,7,8,9,10,11$
be arranged in a sequence so that no number is in its original position?

\solution{
\medskip
\textbf{Solution:}
\medskip

We need to determine the number of \textbf{derangements} of a set of 12 elements. 
\smallskip
\[
\displaystyle 
D_{12}=12! \left[ 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}+\frac{1}{6!}-\frac{1}{7!}+\frac{1}{8!}-\frac{1}{9!}+\frac{1}{10!}-\frac{1}{11!}+\frac{1}{12!} \right]=176,214,841
\]

}


\ppart
In how many ways can the natural numbers $0,1,2,3,4,5,6,7,8,9,10,11$
be arranged in a sequence so that no \emph{even} number is in its original
position?

\solution{
\medskip
\textbf{Solution:}
\medskip

We can derive this answer by mimicking the derivation of the formula for the number of derangements, but worrying only about the even numbers. What we want is the size of the union of all those undesirable permutations that keep one or more of the even numbers in their place, so that we can subtract it from the sum of all permutations.


There are $12!$ permutations altogether. Let $e$ be one of the 6 even numbers. The number of permutations in which $e$ is in its original position is $11!$ (since $e$ remains in its place while the other $11$ numbers are free to move around however they like.)
\medskip

So, there are $11!\binom{6}{1}$ permutations which force $1$ of the even numbers stays in its place. Similarly, there are $10!\binom{6}{2}$ permutations which keep $2$ of the even numbers in their original positions, $9!\binom{6}{3}$ permutations that force $3$ of them to remain where they were,  $8!\binom{6}{4}$ permutations that keep $4$ even numbers fixed, $7!\binom{6}{5}$ permutations that guarantee that $5$ even numbers will stay put, and finally $6!\binom{6}{6}$, that is $6!$ permutations in which all $6$ even numbers will remain where they were.
\medskip

We want to know how many permutations there are where \textbf{at least} one number remains in its place. The inclusion-exclusion principle comes to our rescue, and says that the size of the union of these undesirable permutations is:
\[
\displaystyle
11!\binom{6}{1}-10!\binom{6}{2}+9!\binom{6}{3}-8!\binom{6}{4}+7!\binom{6}{5}-6!\binom{6}{6} = 191,751,120
\]

There are $12!$ permutations in total, $191,751,120$ of which are undesirable, which leaves us with $12!-191,751,120=287,250,480$ permutations where no number appears in its original position.
}


\problem %(10 points)
% Product rule, trees

How many bit strings of length 10 contain either five consecutive $0$s
or five consecutive $1$s?

\solution{
\medskip
\textbf{Solution:}
\medskip

There are $2^{10}$ bit strings of length 10. First, let's see how many of those contain five consecutive $0$'s. The sequence of the 5 $0$'s can start at position $1,2,3,4,5$ or $6$. In each case, the remaining $5$ bits are allowed to be anything, so, as a "first approximation", we can say that there are $6*2^5$ different strings of consecutive $0$'s. \par However, if we do this, we are \emph{overcounting} since, for example, the string that has its first $8$ bits equal to $0$ and the last $2$ equal to $1$ (that is, $0000000011$) will be counted as a valid string \emph{four times} by our method:  \underline{00000}00011, 0\underline{00000}0011, 00\underline{00000}011 and 000\underline{00000}11. We need to eliminate these duplicates, which occur whenever we are dealing with strings that have more than 5 consecutive $0$'s. \par

We can do this by calculating the number of strings with $6$ or more consecutive $0$'s using the same method as above. This will give us $5*2^4$ such strings, and for each sequence of $0$'s, we will be overcounting exactly one time less than we overcounted above: for example, going back to the string of $8$ consecutive $0$'s that was counted 4 times above, we see that this method will count it exactly $3$ times \underline{000000}0011, 0\underline{000000}011, 00\underline{000000}11.  The same will hold for all strings of length $\geq 6$ because the number of allowed starting positions for a sequence of $6$ $0$'s is exactly one less than the number of allowed starting positions for a sequence of $5$ consecutive $0$'s. Thus, it suffices to subtract this number from  the number we got before to get rid of duplicates. Therefore, the number of strings containing 5 or more consecutive $0$'s is  
\[
6*2^5-5*2^4=112\]
By symmetry, there are another 112 strings which contain five consecutive $1$'s. The question was to determine the number of strings that have either 5 $0$'s or 5 $1$'s. So, we are looking for the size of the union of those two sets (the bit strings with 5 $0$'s and the bit strings with 5 $1$'s). The intersection of the 2 sets (i.e, sequences that contain \emph{both} 5 $0$'s and 5 $1$'s) contains 2 elements: $0000011111$ and $1111100000$. Therefore, by the inclusion-exclusion principle, the size of the union of the two sets is $112+112-2=222$

}

\problem %(20 points)
% Binomial coefficient calculations, playing with the definition.
% Also Fibonacci numbers, induction

\ppart %(5 points)
Recall the double induction example from Lecture 3, which involved a
function $f: \nat \times \nat \Rightarrow \nat$ defined by:  $f(n,0) =
1$ for all $n$, $f(0,k) = 1$ for all $k$, and $f(n+1,k+1) = f(n+1,k) +
f(n,k+1)$ for all $n$ and $k$.
We proved by double induction that $f(n,k) = \frac{(n+k)!}{n!k!}$
for all $n$ and $k$. \\
Recall the definition of binomial coefficients: $\binom{a}{b}=\frac{a!}{(a-b)!b!}$. Express $f(n,k)$ in terms of binomial coefficients.

\solution{
\medskip
\textbf{Solution:}
\medskip

Since \[\frac{(n+k)!}{n!k!}=\frac{(n+k)!}{(n+k-k)!k!}=\binom{n+k}{k}\] we see that 
$f(n,k)=\binom{n+k}{k}$
}


% A:  \binom{n+k}{n}

\ppart %(5 points)
What identity about binomial coefficients arises from what we proved
in Lecture 3? Hint: how can you express $\binom{n+1}{k+1}$ in terms of smaller binomial coefficients? 

\solution{
\medskip
\textbf{Solution:}
\medskip

By direct substitution from part (a) we get:
 \[\binom{n+k+2}{k+1} = \binom{n+k+1}{k+1} + \binom{n+k+1}{k}\]
This is usually written as: \[\binom{n+1}{k+1} = \binom{n}{k+1} + \binom{n}{k}\]
}

\ppart %(15 points)
% From Velleman p. 278, problem 5(e)
Recall the definition of Fibonacci numbers:
\[
F_{0}=0;
F_{1}=1;
\text{for every }n\geq 2, F_{n}=F_{n-2}+F_{n-1}\]
Prove that for all $n\geq 0$
\[
F_{2n} = \sum_{i=0}^{n-1}{\binom{2n-i-1}{i}}\qquad  \text{AND}\qquad
F_{2n+1}=\sum_{i=0}^{n}{\binom{2n-i}{i}}
\]

Hint: use induction, and the formula you derived above

%Should be a proof using strong induction, either directly from the
%defintions or using some version of the sum identity above.
%Give a hint?
%I found it useful to try small cases, and to look at where the
%corresponding entries were in the array from lecture 3.
\solution{
\medskip
\textbf{Solution:}
\medskip
We can prove this by induction on $n$. Let $P(n)$ be the statement that \[
F_{2n} = \sum_{i=0}^{n-1}{\binom{2n-i-1}{i}}\qquad  \text{AND}\qquad
F_{2n+1}=\sum_{i=0}^{n}{\binom{2n-i}{i}}
\]
\subparagraph{Base Case:}For $n=0$, $\sum_{i=0}^{-1}{\binom{2n-i-1}{i}}=0$ since the summation basically has no terms. Indeed $F_{0}=0$ so the first half of what we need to show holds. $\sum_{i=0}^{0}{\binom{2n-i}{i}}=1$ and $F_{1}=1$ so the second half also holds.
\subparagraph{Induction Step:} Assume $P(n)$. We want to prove $P(n+1)$. We need to show 2 things:
\[
F_{2n+2} = \sum_{i=0}^{n}{\binom{2n-i+1}{i}}\qquad  \text{and}\qquad
F_{2n+3}=\sum_{i=0}^{n+1}{\binom{2n-i+2}{i}}
\]
First, let's see what $\sum_{i=0}^{n}{\binom{2n-i+1}{i}}$ is equal to. The first term of the summation, i.e, when $i=0$ is $1$, therefore, we can write this as \[
1+ \sum_{i=1}^{n}{\binom{2n-i+1}{i}}\]Now, using the identity from part (b), we can write this as
\[
1+ \sum_{i=1}^{n}{\left[ \binom{2n-i}{i}+ \binom{2n-i}{i-1}\right] } 
\] 
which is, of course, equal to 
\[
1+\sum_{i=1}^{n}{\binom{2n-i}{i}}+\sum_{i=1}^{n}{\binom{2n-i}{i-1}}\]
We notice that if we let $i=0$, $\binom{2n-i}{i}=1$, so we can ``absorb'' that 1 into the first summation and write
 \[
\sum_{i=0}^{n}{\binom{2n-i}{i}}+\sum_{i=1}^{n}{\binom{2n-i}{i-1}}\]
 Things are starting to look good since we recognize that first sum to be $F_{2n+1}$. In order to attack the second sum, we make a substitution: let $k=i-1$ (which means, wherever we see $i$, we put $k+1$. So the above becomes \[
\sum_{i=0}^{n}{\binom{2n-i}{i}}+\sum_{k=0}^{n-1}{\binom{2n-k-1}{k}}\]
From our induction hypothesis, this equals $F_{2n+1}+F_{2n}$ so this does indeed equal $F_{2n+2}$. (For those who are confused about what I proved: if you want to prove that $a=b$, you can just prove that $b=a$).
\medskip

Now, let's see what $\sum_{i=0}^{n+1}{\binom{2n-i+2}{i}}$ is equal to. 
For $i=n+1$, $\binom{2n-i+2}{i}=\binom{n+1}{n+1}=1$. For  $i=0$, $\binom{2n-i+2}{i}=1$. Therefore, we can write this thing as
\[
1+1 +\sum_{i=1}^{n}{\binom{2n+-i+2}{i}}
\] 
which, using the same identity again, can be written as
\[
1+1+\sum_{i=1}^{n}{\left[ \binom{2n-i+1}{i}+\binom{2n-i+1}{i-1}\right]}
\]which is equal to
\[
1+1+\sum_{i=1}^{n}{\binom{2n-i+1}{i}}+\sum_{i=1}^{n}{\binom{2n-i+1}{i-1}}
\]Since for $i=0$, $\binom{2n-i+1}{i}=1$ and for $i=n+1$, $\binom{2n-i+1}{i-1}=\binom{n}{n}=1$, we can ``absorb'' one of the $1$'s into the first sum and the other into the second sum and write
\[
\sum_{i=0}^{n}{\binom{2n-i+1}{i}}+\sum_{i=1}^{n+1}{\binom{2n-i+1}{i-1}}
\]and making the substitution $i-1=k$ into the second sum, we get
\[
\sum_{i=0}^{n}{\binom{2n-i+1}{i}}+\sum_{k=0}^{n}{\binom{2n-k}{k}}
\] By what we proved before, the first sum equals $F_{2n+2}$ and by our induction hypothesis, the second sum equals $F_{2n+1}$. Therefore, $\sum_{i=0}^{n+1}{\binom{2n-i+2}{i}}=F_{2n+2}+F_{2n+1}=F_{2n+3}$ as desired.
 


}

\problem
On a set of $n$ elements how many of the following are there?

\ppart binary relations

\solution{
\medskip
\textbf{Solution:}
\medskip

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

\solution{
\medskip
\textbf{Solution:}
\medskip
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

\solution{
\medskip
\textbf{Solution:}
\medskip
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

\solution{
\medskip
\textbf{Solution:}
\medskip
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

\solution{
\medskip
\textbf{Solution:}
\medskip
The number of
  symmetric or reflexive relations $=$ the number of reflexive
  relations $+$ the number of symmetric relations $-$ the number of
  reflexive and symmetric relations $= 2^{n^2 - n} + 2^{n+\binom{n}{2}} - 2^{\binom{n}{2}}$.
}


%\problem (15 points)
% Counting numbers of combinations.

%Problem 10 from Spring 00 (about counting the number of binary
%relations, symmetric binary relations, etc.  5 parts)


\end{problems}
\end{document}

\problem (10 points)
% Division rule

\ppart
An artist makes paper screens out of squares of colored paper.
Each screen is made up of nine squares of different colored paper.
Nine colors is all he has.
How many different screen can he make?
The screens can be rotated and flipped, and they are still considered
the same screen.

\ppart
Generalize to $n^2$ colors, $n$ by $n$ screens. 


\problem (15 points)
% Poker hands, more combinations

Another form of poker uses 7 cards instead of 5.
Calculate how many 7-card hands contain:
\ppart
Four cards of one rank and three cards of another rank.
\ppart
Three cards of one rank and two cards of each of two other ranks.
\ppart
Pairs of each of three different ranks and another card of a fourth
rank.
\ppart
Pairs of each of two different ranks and three cards of a third,
fourth, and fifth rank.
\ppart
Cards of seven different ranks.

\problem (5 points)
% Card trick:  counting numbers of permutations

Reconsider the card trick done in lecture.
Describe a way of doing a similar trick for 6 cards, where the
assistant reveals 5 cards.  Explain why your method works. 

% Too easy?  If so, can you think of a variation?
