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

%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}


%\hidesolutions
%\showsolutions

\begin{document}


\problemset{8}

%s96
\begin{problem}
How many ways are there to distribute eight balls into six distinct
boxes with the first two boxes having collectively at most four balls if

\begin{problemparts}
\ppart the balls are identical?

 
\solution{
Let us consider placing $n$ balls into $k$ boxes so that exactly $r$
balls are placed in the first two boxes. This can be done in
\[
{r+2-1 \choose 2-1}{(n-r)+(k-2)-1 \choose (k-2)-1}
\]
ways, since there are ${\rm BP}(r,2) = {r+2-1 \choose 2-1}$ ways to
place $r$ balls into first two boxes and ${\rm BP}(n-r,k-2) =
{(n-r)+(k-2)-1 \choose (k-2)-1}$ ways to place the remaining $n-r$
balls into the other $k-2$ boxes. We can place the balls into boxes,
so that {\em at most} $r$ balls go into the first two boxes, in
\[
\sum_{i=0}^r{{i+2-1 \choose 2-1}{(n-i)+(k-2)-1 \choose (k-2)-1}}
\]
ways. In particular for $n=8$, $k=6$ and $r=4$ we get
\[
\sum_{i=0}^4{{i+2-1 \choose 2-1}{(8-i)+(6-2)-1 \choose (6-2)-1}} = 1056{.}
\]

}
\ppart the balls are distinct?


\solution{
As in the part (a), we compute the number of ways $n$ balls can be
placed into $k$ boxes so that exactly $r$ of them are placed in the
first two boxes. Since the balls are distinct, we have ${n \choose r}$
ways to choose which balls to place in the first two boxes, and then
we have $2^r$ ways to place the balls into first two boxes, and
$(k-2)^{n-r}$ ways to place the rest of the balls into the remaining
$k-2$ boxes. Thus the total number of posibilities is
\[
{n \choose r}2^r(k-2)^{n-r}{.}
\]
If we require that {\em at most} $r$ balls go into the first two boxes
we compute that the number of posibilities is
\[
\sum_{i=0}^r{{n \choose i}2^i(k-2)^{n-i}}{.}
\]
For $n=8$, $k=6$ and $r=4$ we get
\[
\sum_{i=0}^4{{8 \choose i}2^i(6-2)^{8-i}} = 1531904{.}
\]
}
\end{problemparts}
\end{problem}

%s02
\begin{problem} 
Prove the following identity by algebraic manipulation and
by giving a combinatorial argument:

\[\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\]

\solution{
 Algebraic:
\begin{eqnarray*}
\binom{n}{k}\binom{n-k}{r-k} &= &\frac{n!}{k!(n-k)!}\frac{(n-k)!}{(r-k)!(n-r)!}\\
&= &\frac{n!}{(n-r)!k!(r-k)!}\\
&= &\frac{n!r!}{r!(n-r)!k!(r-k)!}\\
&= &\frac{n!}{r!(n-r)}\frac{r!}{k!(r-k)!}\\
&= &\binom{n}{r}\binom{r}{k}\\\
\end{eqnarray*}

Combinatoric:
With a group of $n$ balls, I wish to pick a group of $k$ balls and another group of 
$r-k$ balls.  I could do it by picking a group of $r$ balls and then partition it
into sets of $k$ and $r-k$.  On the other hand, I can first pick $k$ balls and then pick $r-k$ balls
from the remaining $n-k$ balls. 
}

\end{problem}

%s01
\begin{problem}

Suppose that $f(x)$ is the generating function for the sequence $a_0,
a_1, a_2, \ldots$.  Find generating functions for the following
sequences.

\begin{problemparts}
\problempart $< 0, 0, 0, a_0, a_1, a_2, \ldots >$

\solution{
\begin{eqnarray*}
a_0 x^3 + a_1 x^4 + a_2 x^5 + \ldots
        & = &   x^3 \cdot (a_0 + a_1 x + a_2 x^2 + \ldots) \\
        & = &   x^3 f(x)
\end{eqnarray*}
}

\problempart $< a_0, a_1 + 1, a_2 + 2, a_3 + 3, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + (a_1 + 1) x + (a_2 + 2) x^2 + (a_3 + 3) x^3 + \ldots}
\hspace{1in} \\
        & = &   (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)
                + (0 + 1 x + 2 x^2 + 3 x^3 + \ldots) \\
        & = &   f(x) + \frac{x}{(1 - x)^2}
\end{eqnarray*}
}

\problempart $< a_0, 0, a_1, 0, a_2, 0, a_3, 0, \ldots >$

\solution{
\begin{eqnarray*}
a_0 + a_1 x^2 + a_2 x^4 + a_3 x^6 + \ldots
        & = &   f(x^2)
\end{eqnarray*}
}

\problempart $< a_0, -a_1, a_2, -a_3, a_4, \ldots >$

\solution{
\begin{eqnarray*}
a_0 - a_1 x + a_2 x^2 - a_3 x^3 + a_4 x^4 - \ldots
        & = &   f(-x)
\end{eqnarray*}
}

\problempart $< a_0, 0, a_2, 0, a_4, 0, \ldots >$

\solution{
\begin{eqnarray*}
\lefteqn{a_0 + a_2 x^2 + a_4 x^4 + a^6 x^6 + \ldots}
\hspace{1in} \\
        & = &   \frac{1}{2} (
                (a_0 - a_1 x + a_2 x^2 - a_3 x^3 + \ldots) \\
        &   & \mbox{} + (a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \ldots)) \\
        & = &   \frac{1}{2}(f(-x) + f(x))
\end{eqnarray*}
}

\end{problemparts}

\end{problem}

%s00
\begin{problem}
On a set of $n$ elements how many of the following are there

\begin{problemparts}

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

}
\ppart symmetric binary relations? 
\solution{
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 reflexive binary relations? 
\solution{
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{
The matrix
  associated with a symmetric and reflexive relation is symmetric and
  ha s $1$'s along the main diagonal. Hence the number of such
  relations is $2^{{n\choose 2} }$.
}
\ppart symmetric or reflexive binary relations? 
\solution{

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}}$.
}
\end{problemparts}
\end{problem}



%f94, s00
\begin{problem}
How many integers in the range from 1 to 1000 are not
  divisible by any of the numbers 6, 10, and 15?
  
\solution{
Here we use inclusion-exclusion to count the number of
    integers from 1 to 1000 not divisible by 6, 10, or 15.  Make a
    table, and add the numbers with appropriate signs:
    
    \begin{tabular}{|c|r|r|c|}
      \hline
      divisible by & least common multiple & number of integers & include/exclude \\
      each of      & of divisors           &from 1 to 1000     & $+/-$\\
      \hline
      \hline
      &   1 & 1000 & $+$ \\
      6         &   6 & 166 & $-$ \\
      10        &  10 & 100 & $-$ \\
      15        &  15 &  66 & $-$ \\
      6, 10     &  30 &  33 & $+$ \\
      6, 15     &  30 &  33 & $+$ \\
      10, 15    &  30 &  33 & $+$ \\
      6, 10, 15 &  30 &  33 & $-$ \\
      \hline
    \end{tabular}
    
    \hspace{3in} These add up to 734.

}


\end{problem}


\begin{problem}
Compute $11^8$ without using a calculator.
\end{problem}



\begin{problem}
Prove  that 
\[
\binom{p-1}{k} \equiv (-1)^k \pmod{p}
\]
where $p$ is prime and $0\le k<p$.

\solution{
When $k=0$, $\binom{p-1}{0}\equiv 1\pmod{p}$. 
We note that $\binom{p}{k}\equiv 0 \pmod{p}$. 
Since $\binom{p}{k}=\binom{p-1}{k}+\binom{p-1}{k-1}$,
$\binom{p-1}{k}=-\binom{p-1}{k-1}$. 
Therefore, by induction, $\binom{p-1}{k}\equiv (-1)^k \pmod{p}$

}

\end{problem}



\end{document}

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

