\documentstyle[12pt,epic,eepic,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{7}{November 2, 1995}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts

\ppart 
The answer is ${52\choose 5}$.
\ppart 
The answer is   $4$. 
\ppart 
The answer is  $13\cdot 48 $.
\ppart 
The answer is  $13\cdot 12\cdot {4\choose 2}\cdot {4\choose 3}.$
\ppart 
The answer is  $4\cdot {13\choose 5}.$
\ppart 
The answer is $9\cdot 4^5$.  (Some people assumed the Ace can appear
at the beginning - Ace, two, three ...,- or at the end - ... Queen,
King, Ace. You will get credit for this.)
\ppart 
The answer is  $13\cdot 12\cdot 11\cdot {4\choose 3}\cdot 4^2$.
\ppart 
The answer is  ${13\choose 2}\cdot 11 \cdot {4\choose 2}^2\cdot 4$.
\ppart 
The answer is  $13\cdot 12\cdot 11\cdot 10 \cdot {4\choose 2}\cdot 4^3$.
\eparts
(For parts g), h) and i) some people assumed you could have anything
else as long as you had at least $3$ of a kind, or at least $2$ pairs,
or at least $1$ pair. You will get credit for this too.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Any relation can be represented
as an $n\times n$ matrix of $0$'s and $1$'s.
\bparts
\ppart $2^{n^2}$ since there are this many different $0-1$ matrices of order $n$.
\ppart The matrix associated with a symmetric relation is symmetric. Since there are $2^{n+{n\choose 2}}$ different symmetric matrices there are an equal number of symmetric relations.
\ppart 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 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^{{n\choose 2}}$.
\ppart 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+{n\choose 2}} - 2^{{n\choose 2}}$.
\ppart The number of equivalence relations is the Bell number $B_n = {\displaystyle(1/e) \sum_{k=0}^{\infty} k^n/k!}$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart There are 26 letters in A,B,$\ldots$,Z. If we use a maximum of 3 
dots/dashes per character then we can represent only $2^1 + 2^2 + 2^3
= 13$ characters. Hence we need at least $4$ and it is easy to see
that $2^1 + 2^2 + 2^3 +2^4 = 29 \geq 26$ and hence the maximum number
of dots/dashes required by any character is $4$.
\ppart There are 62 letters in A,B,$\ldots$,Z,a,b,$\ldots$,z,0,1,$\ldots$,9. 
Since $2^1 + 2^2 + 2^3 +2^4 +2^5 = 61 < 62 < 125 = 2^1 + 2^2 + 2^3
+2^4 +2^5 + 2^6$, the maximum number
of dots/dashes required by any character is $6$.
\ppart Let a {\em valid $k$-sequence} be a sequence of dots/dashes that has 
no consecutive dots. Let $f(k)$ denote the number of valid
$k$-sequences. If the first character in a valid $k$-sequence is a
dash then the rest of the sequence forms a valid $k-1$ sequence. If
the first character in a valid $k$-sequence is a dot then the second
character must be a dash and the rest of the sequence forms a valid
$k-2$ sequence. This gives us the (by now familiar) recurrence
\[ f(k) = f(k-1) + f(k-2)\]
The characteristic equation $x^2-x-1$ has roots $(1+\sqrt{5})/2$ and
$(1-\sqrt{5})/2$. We have boundary conditions $f(1) = 2$ and $f(2) =
2$. The solution to the recurrence is 
$f(k) = (2/\sqrt{5})( (\frac{1+\sqrt{5}}{2})^k - (\frac{1-\sqrt{5}}{2})^k )$.
\ppart Since the effective sending time of a dot is $2$ seconds and the 
effective sending time of a dash is $4$ seconds, we can divide
everything by $2$ and rescale back at the end. So for now let us think
of the effective sending time of a dot as $1$ second and that of a
dash as $2$ seconds. Let $g(k)$ denote the number of sequences with
sending times at most $k$ seconds. If the first symbol is a dot then
the rest of the sequence must have sending time at most $k-1$
seconds. If the first symbol is a dash then the rest of the sequence
must have sending time at most $k-2$ seconds. This gives us the (by
now (uncomfortably) familiar) recurrence
\[ g(k) = g(k-1) + g(k-2)\]
The characteristic equation $x^2-x-1$ has roots $(1+\sqrt{5})/2$ and
$(1-\sqrt{5})/2$. We have boundary conditions $g(1) = 1$ and $g(2) =
3$. The solution to the recurrence is $((\frac{1+\sqrt{5}}{2})^k +
(\frac{1-\sqrt{5}}{2})^k )$. Rescaling back we find the correct
solution is $((\frac{1+\sqrt{5}}{2})^{\lfloor k/2\rfloor} +
(\frac{1-\sqrt{5}}{2})^{\lfloor k/2\rfloor} )$.
\eparts
(In the problem set we asked for the number of sequences having
sending times of less than $k$ seconds. The above solution calculates
the number of sequences having sending times of at most $k$
seconds. Both interpretations will get credit.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart Consider the number of ways of arranging $r$ red and $n+1$ black balls
 in a line. This is equal to ${n+r+1\choose r}$. Now consider counting
the number of ways based on the number $k$ of red balls after the
first black ball. There are ${n+k\choose k}$ such ways for all $k
=0,1,\ldots,r$. Hence we are done.
\ppart 
The proof is by induction on $r$. Let $P(r)$ be the statement $
{\displaystyle \sum_{k=0}^r} {n+k\choose k} = {n+r+1\choose r}.$
Base Case. $P(0)$ is true since
${\displaystyle \sum_{k=0}^0} {n+k\choose k} = 1 {n+0+1\choose 0}.$\\
Inductive step. Assume $P(r)$ is true. Then 
\begin{eqnarray*}
{\displaystyle \sum_{k=0}^{r+1}} {n+k\choose k} & = {\displaystyle \sum_{k=0}^r} {n+k\choose k} + {n+r+1\choose r+1} & \\
 & = {n+r+1\choose r} + {n+r+1\choose r+1} & \mbox{ by inductive hypothesis }\\
 & = {n+r+2\choose r+1} & \mbox{ by  Pascal's identity }
\end{eqnarray*}
Hence $P(r+1)$ is true. So, $P(r)$ is true for all $r$ and we are done.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart ${100 \choose 55}$
\ppart ${17 \choose 8}3^82^9$
\ppart $x^k$ has a nonzero coefficient iff $-100 \leq k \leq  200$ and $k = 2$ mod $3$. In such a case the coefficient is ${100\choose (100 + k)/3}(-1)^{(200 - k)/3}$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart Consider the number of ways of picking a team of size $k$  from a 
group of $n$ people and designating one of them captain. This can be
done in $k{n\choose k}$ ways, for all $k = 0,1,\ldots,n$. But the total
number of ways of doing this can also be counted differently. First
select the captain - $n$ ways - then select an arbitrary subset of the
rest - $2^{n-1}$ ways. Hence the result follows.
\ppart
Differentiating 
\[(1+x)^n = {\displaystyle \sum_{k=0}^n {n\choose k}x^k}\]
we get
\[n(1+x)^{n-1} = {\displaystyle \sum_{k=1}^n k{n\choose k}x^{k-1}}\]
 and evaluating it at $x=1$ we get the desired result.
\eparts.

\end{problems}

\end{document}





