%q10S.tex: 
%begin macros
\baselineskip=14pt
\parskip=10pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
\def\g{\bigtriangledown}
\def\S{\cal S}
\nopagenumbers
%end macros
 

\centerline
{
\bf  Solutions to Quiz \# 10 for Dr. Z.'s Number Theory
Course for Dec. 5, 2013
}
\bigskip


{\bf 1.} An {\it extremely distinct} partition
of $n$ is a sequence of integers
$$
(\lambda_1, \lambda_2, \dots, \lambda_t) \quad ,
$$
such that
$$
\lambda_1 + \lambda_2 + \dots + \lambda_t = n \quad ,
$$
and
$$
\lambda_1 - \lambda_2 \geq 2
\quad
\lambda_2 - \lambda_3 \geq 2
\quad ,
\dots ,
\quad,
\lambda_{t-1} - \lambda_t \geq 2
$$
and
$$
\lambda_t>0 \quad,
$$
Let $q(n)$ be the number of 
partitions of $n$, and $q(n,k)$ 
be the number of exteremely distinct partitions of 
$n$ whose largest part is $k$.

(i) (5 points) Explain why
$$
q(n,k) = \sum_{r=1}^{k-2} q(n-k, r) \quad ,
$$
and, of course
$$
q(n,n)=1 \quad .
$$
(ii) Use the above recurrence, and 
$$
q(n)=\sum_{k=1}^{n} q(n,k)
$$ 
to 
compute $q(n)$ for $1 \leq n \leq 5$.


{\bf Sol. to 1(i)}: If you take an extremely disctinct partion of $n$ with largest part $k$, and chop its head
(that equals $k$), what remains is another such partion, but of the smaller number $n-k$, and whose
largest part $r$, can be either $1$, or $2$, all the way to $r-2$ (it can't be $r-1$ or $r$).

Adding up all these options  explains the recurrence.


{\bf Important Fact}: If you have $\sum_{a}^{b}$ and $a>b$ then the answer is always $0$.

$$
q(1,1)=1
$$
$$
q(2,1) = \sum_{r=1}^{-1} q(1, r) =0 \quad,\quad  q(2,2)=1 \quad ;
$$
$$
q(3,1) = \sum_{r=1}^{-1} q(2, r) =0 \quad,\quad  
q(3,2) = \sum_{r=1}^{0} q(1, r) =0 \quad,\quad  q(3,3)=1 \quad  ;
$$
$$
q(4,1) = \sum_{r=1}^{-1} q(3, r) =0 \quad,\quad  
q(4,2) = \sum_{r=1}^{0} q(2, r) =0 \quad,\quad  
q(4,3) = \sum_{r=1}^{1} q(1, r) = q(1,1)=1 \quad,
$$
$$
q(4,4)=1 \quad ;
$$
$$
q(5,1) = \sum_{r=1}^{-1} q(4, r) =0 \quad,\quad  
q(5,2) = \sum_{r=1}^{0} q(3, r) =0 \quad,\quad  
q(5,3) = \sum_{r=1}^{1} q(2, r) = q(2,1)=0 \quad,
$$
$$
q(5,4) = \sum_{r=1}^{2} q(1, r) = q(1,1)+q(1,2)=1+0=1 \quad,
$$
$$
q(5,5)=1 \quad .
$$
Finally
$$
q(1)=q(1,1)=1 \quad ,
$$
$$
q(2)= q(2,1)+q(2,2)=0+1=1 \quad
$$
$$
q(3)= q(3,1)+q(3,2) + q(3,3)=0+0+1=1 \quad
$$
$$
q(4)= q(4,1)+q(4,2) + q(4,3)+ q(4,4) =0+0+1=1 \quad
$$
$$
q(5)= q(5,1)+q(5,2) + q(5,3)+ q(5,4)+q(5,5) =0+0+0+1+1=2 \quad .
$$

{\bf Ans. to 1(ii)}: $q(1)=1,q(2)=1, q(3)=1, q(4)=1, q(5)=2$.


\end
