\documentclass{amsart}
\usepackage{amssymb}
\usepackage{amsfonts}
\begin{document}

\centerline{\Large \textbf{Solutions for Homework 1 problems}}

{\bf Problem $2$}: What is the number of $k$-subsets chosen from $1$ to $n$ containing no two consecutive integers?

The solution is given by the number of weak compositions of $n-(2k-1)$ into
$k+1$ parts, which i given by
$$\left( \begin{array}{c}
n-(2k-1)+(k+1)-1 \\
k+1-1
\end{array} \right)=\left( \begin{array}{c}
n-k+1 \\
k
\end{array} \right) $$
The way to see this is as follows.  To each $k$-subset of $1$ to $n$ we can associate a sequence of $k$ dots and $n-k$ lines, where the position of the dots determine which elements are in the $k$ subset.  For example the sequence $\{\circ | \circ | \circ\}$ corresponds to the $3$-subset $\{1,3,5\}$ of the integers from $1$ to $5$ .
We can build up $k$-subsets that satisfy the conditions of this problem as follows.  
Start with the $k$ dots $\{\circ \circ \circ \cdots \circ\}$. A $k$ subset will be determined once we specify the location of the $n-k$ lines.  Since our subset must not contain any two consecutive integers, there must be a line separating any two circles, i.e, there must be a line between the first and second circles, the second and third circles, and so on. It takes $k-1$ lines to do this.  
So far, our sequence looks like $\{\circ | \circ | \cdots \circ | \circ\}$.
We now have $n-k-(k-1)$ remaining lines to insert into the sequence.  For each of the remaining lines, there are $k+1$ distinct postions in the sequence that we could insert the line into.  These positions correspond to inserting the line before the first dot, in between the first
 and second dots, in between the second and third dots, ... in between the $k-1^{th}$ and $k^{th}$ dots, and after the $k$th dot.  These positions determine all the unique ways of adding a line.  Since all of the lines are indistinguishable, if makes no difference if we add a line immediately before or after an existing line, as these two additions give the same sequence.  Thus we want to distribute $n-k-(k-1)$ lines to $k+1$ different postitions, and each way to do so determines a unique $k$-subset of $1$ to $n$ containing no two consecutive integers.
The number of ways this can be done is given by the number of weak compositions of $n-k-(k-1)=n-2k+1$ into $k+1$ parts.

\textbf{Problem 3:}  What is the number of monotone increasing functions mapping the set $\{1,\dots,n\}$ into itself?\\
\\
\textbf{Solution:}  Given a multi-subset $\{a_1,\dots,a_n\}$ chosen from the set $\{1,\dots,n\}$, there is exactly one way to make a monotone increasing function from $\{1,\dots,n\}$ to $\{a_1,\dots,a_n\}$.  To construct this function $f$, first order the set $\{a_1,\dots,a_n\}$ and then set $f(i) = a_i$.  Therefore, the number of monotone increasing functions mapping $\{1,\dots,n\}$ to itself is in one-to-one correspondence with the number of multi-subsets of $\{1,\dots,n\}$.  This in turn is in one-to-one correspondence with the number of $n$-weak compositions of $n$, of which there are ${2n-1} \choose n$.\\
\\

\textbf{Problem 4:} Prove that the Catalan numbers give the
cardinality of the set of Standard tableaux in a $2 \times n$
rectangular diagram. A Standard tableaux for a $2 \times n$ rectangular
array of boxes is a way to arrange the numbers $\{1,2,\ldots,2n\}$ in
the boxes in such a way they increase across rows and down
columns. 

\textbf{Solution} We show a bijection from the ballot problem
to the standard tableaux problem.  Consider a sequence of votes
$\{+,-\}^{2n}$ to the two candidates with $+$ being the vote for
the first candidate and $-$ being the vote for the second.
If the $i$th vote  in the sequence is a $+$ we add $i$ to the first row. Else we
add $i$ to the second row.
Each candidate gets $n$ votes so both the rows are completely
filled.  Increasing order in a row is guaranteed by the way the
numbers are filled.
At any prefix of the sequence the number of votes for the
first candidate has at least as many votes as the second so the
increasing order in the columns are also guaranteed.

The other direction of the mapping and its correctness follows using
the similar arguments.



\noindent
\textbf{Problem 5.}  A Full binary tree is one where every node has either 2 or 0 children. Set up a bijection between binary trees with $n$ nodes and full binary trees with $2n+1$ nodes.\\

Let the set of all Full Binary Trees with $2n+1$ nodes be denoted by $FBT_{2n+1}$ and the set of all Binary Trees with $n$ nodes by $BT_n$.  Now take $K\in FBT_{2n+1}$.  First I show by induction that $K$ has $n+1$ leaves (i.e nodes with no children).  

If $n=1$, then $K$ must have 3 nodes, 1 of which is the root and 2 are the children.  So it has 2=1+1 leaves.

Now assume for $K\in FBT_{2k+1}$, it has $k+1$ leaves.  Then if we want to add nodes to get a $FBT$, $K'$, with exactly $2(k+1)+1=2k+3$ nodes then the only way we can do that is by adding 2 nodes to an $FBT$ which we can only do by adding them both to the same leaf.  Which in that case will give us $k+1-1+2=(k+1)+1$ nodes.  Thus by induction an $FBT$ of $2n+1$ nodes has $n+1$ leaves.

Now for an $FBT$, $K$, assign the map $\phi: FBT_{2n+1} \rightarrow BT_n$ which takes $K$ and deletes all of its leaves.  Clearly $\phi(K)$ is a binary tree which has $(2n+1)-(n+1)=n$ nodes.  So this map is well defined.  It is also not hard to see that if $K_1,K_2\in FBT_{2n+1}$ don't have exactly the same configuration of leaves then they can't have exactly the same configuration of non-leaves (since every non-leaf is forced to have 2 children by definition).  That is, if we have a leaf $p$ that is in $K_1$ but not in $K_2$, then we must have a non-leaf (the parent of $p$) that is in $K_1$ but not in $K_2$.  Thus $\phi$ is injective.

Also if given a $K\in BT_n$, there is exactly one way to fill it up into an $FBT$ with $2n+1$ nodes without changing any of the existing nodes.  That is to add one child to every node with only one child, two children to every node with 0 children, and 0 children to every node with 2 children.  This is the smallest $FBT$ with $K$ inside and will have exactly $2n+1$ nodes because this is exactly the process which is inverse to $\phi$.  So we then have $\phi^{-1}:BT_n\rightarrow FBT_{2n+1}$ that is well defined and injective since this process of adding nodes is unique.

Thus $\phi$ is a bijective map which gives us that the number of Full Binary Trees with $2n+1$ nodes is equal to the number of Binary Trees with $n$ nodes.



\noindent \textbf{Problem 6} All points of the plane that have integer coordinates are colored red, blue, or green.  Prove that there will be a rectangle whose vertices are all of the same color.  (Hint: use the pigeonhole principle!)
\\\\
proof:  

Claim: Any $4\times(3^4+1)$ section of the lattice will have such a rectangle.  This proof uses the pigeonhole principle twice. 

  First, note that a set of four vertices will have two vertices of the same color by the pigeonhole principle.  

  Next, note that there are $3^4$ distinct ways to color four distinct vertices.  So by the pigeonhole principle, a collection of $3^4+1$ such colorings will have a repeat.  
  Now think of our four vertices as a column in $\mathbb{Z}\times\mathbb{Z}$ and collect $3^4+1$ columns.  There will be a repeat of column colorings which already has two vertices with the same color.  Thus we have a rectangle with four vertices of the same color.  (Note: the same method can be used for any finite number of colors)


\noindent {\bf \large Problem 7}  I will give a bijection between the set of partitions of n into distinct terms and the set of partitions of n into odd terms.  Let $a_1 + a_2 + \cdots + a_k = n$ be a partition of n into {\em odd} terms (assume WLOG that this partition is written in descending order).  Now group all terms of the partition which are equal, so that we have:

\[
\alpha_1\, a_1 + \alpha_2 \, a_{1+\alpha_1} + \alpha_3 \, a_{1+\alpha_1 + \alpha_2} + \cdots + \alpha_l \, a_{1+\alpha_1 + \cdots + \alpha_{l-1}} = n
\]

\noindent Where $\alpha_i$ is the multiplicity of the term $a_{1+\alpha_1 + \cdots + \alpha_{i-1}}$.  Expand each $\alpha_i$ in binary as $\alpha_i = 2^{m_1^{(i)}} +  2^{m_2^{(i)}} + \cdots +  2^{m_{N_i}^{(i)}}$  where each $m_j^{(i)}$ is a non-negative integer, and $m_j^{(i)} \neq m_k^{(i)}$ whenever $j \neq k$.  Since the binary representation of any positive integer is unique, and the terms $a_1, \ldots, a_{1+\alpha_1 + \cdots + \alpha_{l-1}}$ are odd and distinct, we have that the following partition must have distinct parts:

\begin{align*}
2^{m_1^{(1)}} \, a_1 + 2^{m_2^{(1)}} \, a_1 + \cdots + 2^{m_{N_1}^{(1)}} \, a_1 + 2^{m_{1}^{(2)}} \, a_{1+\alpha_1} + \cdots +  2^{m_{N_2}^{(2)}} \, a_{1+\alpha_1} \\
+ \cdots + 2^{m_1^{(l)}} \, a_{1+\alpha_1 + \cdots + \alpha_{l-1}} + \cdots + 2^{m_{N_l}^{(l)}} \, a_{1+\alpha_1 + \cdots + \alpha_{l-1}}  = n
\end{align*}

\noindent So we have a map from a partition with odd parts to a partition with distinct parts.  The inverse map can be defined as follows.  Begin with a partition of distinct terms: $b_1 + b_2 +\cdots + b_k = n$ and write it as:

\[
2^{l_1}\frac{b_1}{2^{l_1}} + 2^{l_2}\frac{b_2}{2^{l_2}} +\cdots + 2^{l_k}\frac{b_k}{2^{l_k}}= n
\]

\noindent Where $\frac{b_1}{2^{l_1}}, \ldots, \frac{b_k}{2^{l_k}}$ are odd.  Now rewrite this as:

\[
\frac{b_1}{2^{l_1}} +\cdots +\frac{b_1}{2^{l_1}} + \frac{b_2}{2^{l_2}}+\cdots + \frac{b_2}{2^{l_2}} +\cdots + \frac{b_k}{2^{l_k}} +\cdots + \frac{b_k}{2^{l_k}} = n
\]

\noindent Where each group of terms with indices $i$ and $l_i$ have multiplicity $2^{l_i}$.  This partition has odd parts.  Clearly the two above processes are inverses of one another since applying one map to the result of the other will return us to the original partition, so we have our bijection.  Therefore, the number of partitions of n with distinct parts is the same as the number of partitions of n with odd parts. \hfill $\Box$

\vspace{0.5in}


\noindent
\textbf{Problem 8.}  what is the number of conjugacy classes in $S_n$? How would you determine the cardinality of a conjugacy class? Suppose you choose a permutation in $S_n$ uniformly at random. What is the expected number of cycles?\\

\textbf{Solution:}  It is an elementary fact from algebra (proof omitted here) that two elements are conjugate in $S_n$ if and only if they are of the same cycle type.  Therefore, the conjugacy classes in $S_n$ are indexed by the different cycle types.  The cycle types are denoted by $c=(c_1,c_2,\dots,c_n)$, where $c_i$ denotes the number of cycles of length $i$.  We have $c_1 + 2c_2 + \cdots + nc_n = n$. Thus, the number of possible conjugacy classes is the number of partitions of $n$.  Now, the cardinality of a conjugacy class is given by 
the formula for the number of permutations of type $c$ is $$\frac{n!}{c_1! c_2! \dots c_n ! 1^{c_1} 2^{c_2} \dots n^{c_n}}$$

Next, denote $E(\pi)$ as the expected number of cycles of a random permutation $\pi\in S_n$ and $P(k)$ as the probability of $\pi$ having $k$ many cycles in its cycle decomposition.  So by definition $E(\pi)=\sum_{k=1}^n P(k)k$.  Now since $S_n$ is finite and $P(k)$ is a uniform distribution then $P(k)=\frac{c(n,k)}{n!}$ where $c(n,k)$, the signless Stirling number of the first kind, is the number of permutations with $k$ many cycles in its decomposition.  

Now we also know that 
$$\sum_{k=1}^n c(n,k)x^k=x(x+1)(x+2)\cdots(x+(n-1))$$
So take 
$$\frac{d}{dx} (\sum_{k=1}^n c(n,k)x^k)=(\sum_{k=1}^n kc(n,k)x^{k-1})$$
and $$\frac{d}{dx}\prod_{j=0}^{n-1} x+j=[(x+1)\cdots(x+(n-1))]+[x(x+2)\cdots(x+(n-1))]$$
$$~~~~~~~~~~~~+\cdots+[x\cdots(x+(n-2))]$$  
Now then 
$$(\sum_{k=1}^n kc(n,k)x^{k-1})=[(x+1)\cdots(x+(n-1))]+[x(x+2)\cdots(x+(n-1))]$$
$$~~~~~~~~~~~~~~~~+\cdots+[x\cdots(x+(n-2))]$$ 
and in fact this has to be true for all values of $x$ so let $x=1$ and we get $$\sum_{k=1}^n kc(n,k)=\frac{n!}{1}+\frac{n!}{2}+\ldots+\frac{n!}{n}=n!\sum_{k=1}^n \frac{1}{k}$$ 
thus $$\sum_{k=1}^n \frac{c(n,k)}{n!}k=\sum_{k=1}^n \frac{1}{k}$$  
Thus the expectation for the number of cycles of a random permutation $\pi\in S_n$ is $$E(\pi)=\sum_{k=1}^n \frac{1}{k}$$


\end{document}