\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{7}{October 24, 1995}{October 31, 1995}

{\bf Reading:} Sections 4.1--4.3,4.6 and 4.7 of {\it
Discrete Mathematics and its Applications} by Kenneth H. Rosen.

\bigskip

\begin{problems}

\problem
A poker hand consists of $5$ cards drawn from a standard deck of $52$ cards. How many different poker hands are there that contain 
\bparts
\ppart any set of $5$ cards?
\ppart a royal flush ($10$, Jack, Queen, King and Ace of one suit)?
\ppart $4$ of a kind (e.g. four $7$'s)?
\ppart a full house (two of a kind and three of another kind)?
\ppart a flush ($5$ cards in a suit)?
\ppart a straight (five cards in a sequence without any suit restrictions)?
\ppart $3$ of a kind?
\ppart $2$ pairs (e.g. two $7$'s and two $9$'s)?
\ppart $1$ pair?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
On a set of $n$ elements how many of the following are there
\bparts
\ppart relations?
\ppart symmetric relations?
\ppart reflexive relations?
\ppart symmetric and reflexive relations?
\ppart symmetric or reflexive relations?
\ppart equivalence relations (this problem is for extra credit)?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Morse code is a system for representing an alphabet with dots and
dashes.  The arrangements of dots and dashes is then transmitted using
eletrical pulses of varying lengths or analogous mechanical or visual
signals. For example, the letter A may be represented by dash-dot-dot
and the letter B by dash-dot.  Since it takes time and effort to
transmit, the code must be as compact as possible. For a compact code
what is the maximum number of dots/dashes required by any character if
we wish to represent
\bparts
\ppart the letters A,B,$\ldots$,Z?
\ppart the letters A,B,$\ldots$,Z,a,b,$\ldots$,z,0,1,$\ldots$,9? 
\ppart Given that two dots in a row can get confused with a dash, how many 
different characters can you represent with $k$ dots/dashes that have no consecutive dots?
\ppart Suppose a dot takes 1 seconds, a dash takes 3 seconds, and each must
be followed by a 1 second interval of silence.  How many morse symbol
sequences have sending times less than k seconds (including the last
interval of silence)? 
\eparts
Hint: For parts c) and d) determine and solve a recurrence
conditioning on the value of the first symbol.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\iffalse
\problem
Grab your 1995/96 MIT Bulletins.  How many ways can a student majoring
in VI-2 satisfy the restricted electives requirements (don't count
courses no-longer offered).  Ignore the engineering design points
requirement.
\fi
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Prove that 
\[ {\displaystyle \sum_{k=0}^r}\left(\begin{array}{c} n+k\\ k\end{array}\right) = \left(\begin{array}{c} n+r+1\\ r\end{array}\right) \]
whenever $n$ and $r$ are positive integers
\bparts
\ppart using a combinatorial argument.
\ppart using Pascal's identity.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Find the coefficient of 
\bparts
\ppart $x^{10}$ in $(x+(1/x))^{100}$.
\ppart $x^8y^9$ in $(3x+2y)^{17}$.
\ppart $x^k$ in $(x^2 - (1/x))^{100}$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Prove that 
\[ {\displaystyle \sum_{k=1}^n}k\left(\begin{array}{c} n\\ k\end{array}\right) = n2^{n-1} \]
\bparts
\ppart using a combinatorial argument.
\ppart by finding a closed form for $ {\displaystyle \sum_{k=1}^n}\left(\begin{array}{c} n\\ k\end{array}\right)kx^k$ and evaluating it at $x=1$.
\eparts

\end{problems}

\end{document}










