***Question 1*** Each ordering can be decided in two steps: 1. Pick the ordering of $2,3,...,n$ - for which there are $(n-1)!$ options. 2. Pick the position of the $1$s - ${n\choose 2}$ options. So $A_{n}={n \choose 2} (n-1)!.$ ***Question 2*** WLOG, fix violinists $1,2,3,\dots,n$ in trios $1,2,3,\dots,n$ respectively. There are $n!$ ways to distribute the cellists between the trios. There are $n!$ ways to distribute the pianists between the trios. Hence there are $(n!)^2$ ways the students can form into trios. ***Question 3*** Each walk corresponds uniquely to a string of $a$ $Rs and $b$ $Us. Hence, $C_{a,b}=\frac{(a+b)!}{a!b!}.$ ***Question 4*** For all $n\geq 3,$ a tiling of the $2\times n$ grid will either end with an vertical domino or two horizontal dominoes hence $D_{n}=D_{n-1}+D_{n-2}$with $D_{1}=1$ and $D_{2}=2.$ That is, $D_{n}$ is the $n$th Fibonacci number. ***Question 5*** (a) Sorting the subsets by the number of its odd/even elements $k$ gives $E_{n}=\sum_{k=0}^n {n\choose k}^2$since there are ${n \choose k}^2$ ways to choose $k$ odd numbers and $k$ even numbers from $n$ odd numbers and $n$ even numbers respectively. Hence, it is sufficient to show $\sum_{k=0}^n {n\choose k}^2 = {2n \choose n}.$ Observe that ${2n\choose n}$ counts the $n$-element subsets of $\{1,2,3,\dots,2n\}.$ Each $n$-element subset containing $k$ even numbers contains $n-k$ odd numbers. There are ${n \choose k}$ and ${n \choose n-k}$ ways to choose $k$ even numbers and $n-k$ odd numbers from $\{ 1,2,3,\dots,2n \}$ respectively. Summing over all possible values of $k$ gives $\begin{align} {2n \choose n} &= \sum_{k=0}^n {n \choose k} {n\choose n-k } \\ &= \sum_{k=0}^n {n\choose k}^2 & \text{since ${n\choose k}={n\choose n-k}$} \tag*{$\square$}\end{align}$ (b) **Bijective proof**: Let $\textlbrackdbl 2n \textrbrackdbl$ denote $\{ 1,2,\dots,2n \}.$ For all $X \subseteq \textlbrackdbl 2n \textrbrackdbl,$ define functions $o$ and $e$ by $o(X)=\{x \in X: 2 \not \mid x \} \quad \text{and} \quad e(X)=\{ x\in X:2 \mid X \}$ Let $S$ be the set of subsets of $\textlbrackdbl 2n \textrbrackdbl$ with equally many even and odd numbers and ${\textlbrackdbl 2n \textrbrackdbl \choose n}$ denote the set of $n$-element subsets of $\textlbrackdbl 2n \textrbrackdbl$. Define $f:S\to{\textlbrackdbl 2n \textrbrackdbl \choose n}$ by $f(X) = e(X) \cup (o(\textlbrackdbl 2n \textrbrackdbl)\setminus o(X))$ First, I'll show that $f$ is 'well-defined', that is, for all $X\in S,$ indeed $f(X)\in{\textlbrackdbl 2n \textrbrackdbl \choose n}.$ Fix $X\in S.$ Then by definition of $S,$ $|o(X)|=|e(X)|.$ Since $e(X)$ and $o(\textlbrackdbl 2n \textrbrackdbl)\setminus o(X)$ are disjoint (as they contain even and odd numbers respectively) $\begin{align} |f(X)|&=|e(X)|+|o(\textlbrackdbl 2n \textrbrackdbl) \setminus o(X)| \\ &=|e(X)|+ n - |o(X)| & \text{since $|o(\textlbrackdbl 2n \textrbrackdbl)|=n$} \\ &= |e(X)| +n - |e(X)| =n & \text{since $|o(X)|=|e(X)|$} \end{align}$Hence, $f(X)\in {\textlbrackdbl 2n \textrbrackdbl \choose n}$ since $f(X)$ is a subset of $\textlbrackdbl 2n \textrbrackdbl$ (by definition, $f(X) \subseteq X \subseteq \textlbrackdbl 2n \textrbrackdbl$) and $|f(X)|=n$. Next, I'll show that $f$ is injective. Let $X_{1},X_{2}\in S$ such that $f(X_{1})=f(X_{2}).$ Since the odd and even parts are disjoint, must have $e(X_{1})=e(X_{2})$ and $o(X_{1})=o(X_{2})$ which implies $X_{1}=X_{2}.$ Let $Y\in {\textlbrackdbl 2n \textrbrackdbl \choose n}.$ Define $X=e(Y) \cup (o(\textlbrackdbl 2n \textrbrackdbl)\setminus o(Y)).$ Then $f(X)=e(Y) \cup o(Y)=Y $hence, $f$ is surjective. $\square$ ***Question 6*** STS for all $n>1,$ $\sum_{k=1}^{n}(-1)^k k {n \choose k}=0$ since the zeroth term of the original sum is zero. By the binomial theorem, $\begin{align} (1+x)^{n} = \sum_{k=0}^{n} {n\choose k} x^{k} \end{align}$Taking derivatives of both sides wrt to $x$ gives $\begin{align} \frac{d}{dx} [(1+x)^{n}] &= \frac{d}{dx} \sum_{k=0}^n {n \choose k}x^{k} \\ n(1+x)^{n-1}&= \sum_{k=1}^n k {n\choose k} x^{k-1} \\ nx(1+x)^{n-1} &= \sum_{k=1}^n k {n\choose k} x^k & \text{multiplying both sides by $x$} \end{align}$Substituting $x=-1,$ gives that for all $n>1,$ $0 = \sum_{k=1}^n (-1)^k k {n \choose k} \tag*{$\square$}$ ***Question 7*** (a) Rhombus tilings of the $n$th grid correspond uniquely to the number of ways to stack unit cubes against the corner of the room below: ![[Pasted image 20241010094020.png|500]] For $n>1,$ suppose we know $F_{n-1}.$ The 'new arrangements' that contribute to $F_{n}$ are exactly those with box in column $n.$ There are exactly $n+1$ of such arrangements so $F_{n}=n+1+F_{n-1}.$ (b) By induction on $n,$ $\begin{align} F_{n} &=(3+\dots+n+1)+F_{1} \\ &= \frac{(n+1+3)(n+1-3+1)}{2} +3 \ \\ &= \frac{1}{2}(n^2 +3n+1) \end{align}$ Check: $F_{60}=\frac{1}{2}\times 60^{2}+\frac{3}{2}\times 30+1= 1800+90+1= 1891.$ (c) $F_{n}=\frac{1}{2}(n^2+3n+1)=\frac{(n+2)(n+1)}{2}=\frac{(n+2)!}{n!2!}={n+2 \choose 2}.$ **Bijective proof**: Every tiling of the $n$th corresponds uniquely to a $2$-element subsets of $\{ R_{1},R_{2},\dots,R_{n},C_{1},C_{2} \}.$ Define the map as follows: 1. If there are $0$ boxes, map this tiling to $\{ C_{1},C_{2} \}$ 2. If there are $k\geq 1$ boxes on row $1$ and $0$ on row $2,$ map this tiling to $\{ R_{k},C_{1} \}$ 3. If there are $k\geq 1$ boxes on rows $1$ and $2,$ map this tiling $\{ R_{k}, C_{2} \}$ 4. If there are $k> 1$ boxes on row $1$ and and $l<k$ on row $2,$ map this tiling to $\{ R_{k},R_{l}\}$ This map is clearly surjective and injective and hence bijective.