Combin.PS1

My Solution for Combinatorics for the Fall 2015 semester, Problem Set 1. Keep your Academic Integrity plz.

Combinatorics: Problem Set 1

Himemiya

1 Problem 1

1.1

Which is equivalent to distribute $n$ distinct balls into $k$ distinct bins unrestrictedly. Therefore the answer is

 $k^{n}.$

1.2

Which is equivalent to distribute $n$ distinct balls into $k$ distinct bins such that every bin contains at most 1 ball. Therefore the answer is

 $\mathchoice{\hphantom{{}^{\leavevmode{n}}_{\mathchoice{\makebox[7.499886pt][c]% {\displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt]% [c]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}}}P^{\kern-% 13.499794pt\leavevmode{n}\kern 7.499886pt\mathchoice{\makebox[7.499886pt][c]{% \displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c% ]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}}_{\kern-31.4% 99519pt\mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{\makebox[7.499886% pt][c]{\textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}}{\makebox[7.4998% 86pt][c]{\scriptscriptstyle}}\kern 7.499886pt\leavevmode{k}}}{\hphantom{{}^{% \kern-13.499794pt\leavevmode{n}\kern 7.499886pt\mathchoice{\makebox[7.499886pt% ][c]{\displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.49988% 6pt][c]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}% \leavevmode{n}}_{\kern-31.499519pt\mathchoice{\makebox[7.499886pt][c]{% \displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c% ]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}\kern 7.49988% 6pt\leavevmode{k}\mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{% \makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}% }{\makebox[7.499886pt][c]{\scriptscriptstyle}}}}P^{\kern-43.499336pt\kern-13% .499794pt\leavevmode{n}\kern 7.499886pt\mathchoice{\makebox[7.499886pt][c]{% \displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c% ]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}\leavevmode{n% }\kern 7.499886pt\mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{% \makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}% }{\makebox[7.499886pt][c]{\scriptscriptstyle}}}_{\kern-61.499062pt\kern-31.4% 99519pt\mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{\makebox[7.499886% pt][c]{\textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}}{\makebox[7.4998% 86pt][c]{\scriptscriptstyle}}\kern 7.499886pt\leavevmode{k}\mathchoice{% \makebox[7.499886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{\textstyle% }}{\makebox[7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c]{% \scriptscriptstyle}}\kern 7.499886pt\leavevmode{k}}}{\hphantom{{}^{\kern-43.4% 99336pt\kern-13.499794pt\leavevmode{n}\kern 7.499886pt\mathchoice{\makebox[7.4% 99886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[% 7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}% \leavevmode{n}\kern 7.499886pt\mathchoice{\makebox[7.499886pt][c]{% \displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c% ]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}\leavevmode{n% }}_{\kern-61.499062pt\kern-31.499519pt\mathchoice{\makebox[7.499886pt][c]{% \displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c% ]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}\kern 7.49988% 6pt\leavevmode{k}\mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{% \makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}% }{\makebox[7.499886pt][c]{\scriptscriptstyle}}\kern 7.499886pt\leavevmode{k}% \mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{% \textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c% ]{\scriptscriptstyle}}}}P^{\kern-73.498878pt\kern-43.499336pt\kern-13.499794% pt\leavevmode{n}\kern 7.499886pt\mathchoice{\makebox[7.499886pt][c]{% \displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c% ]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}\leavevmode{n% }\kern 7.499886pt\mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{% \makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}% }{\makebox[7.499886pt][c]{\scriptscriptstyle}}\leavevmode{n}\kern 7.499886pt% \mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{% \textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c% ]{\scriptscriptstyle}}}_{\kern-91.498604pt\kern-61.499062pt\kern-31.499519pt% \mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{% \textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c% ]{\scriptscriptstyle}}\kern 7.499886pt\leavevmode{k}\mathchoice{\makebox[7.4% 99886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[% 7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}% \kern 7.499886pt\leavevmode{k}\mathchoice{\makebox[7.499886pt][c]{% \displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c% ]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}\kern 7.49988% 6pt\leavevmode{k}}}{\hphantom{{}^{\kern-73.498878pt\kern-43.499336pt\kern-13.4% 99794pt\leavevmode{n}\kern 7.499886pt\mathchoice{\makebox[7.499886pt][c]{% \displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c% ]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}\leavevmode{n% }\kern 7.499886pt\mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{% \makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}% }{\makebox[7.499886pt][c]{\scriptscriptstyle}}\leavevmode{n}\kern 7.499886pt% \mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{% \textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c% ]{\scriptscriptstyle}}\leavevmode{n}}_{\kern-91.498604pt\kern-61.499062pt% \kern-31.499519pt\mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{% \makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}% }{\makebox[7.499886pt][c]{\scriptscriptstyle}}\kern 7.499886pt\leavevmode{k}% \mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{% \textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c% ]{\scriptscriptstyle}}\kern 7.499886pt\leavevmode{k}\mathchoice{\makebox[7.4% 99886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[% 7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}% \kern 7.499886pt\leavevmode{k}\mathchoice{\makebox[7.499886pt][c]{% \displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c% ]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}}}P^{\kern-10% 3.498421pt\kern-73.498878pt\kern-43.499336pt\kern-13.499794pt\leavevmode{n}% \kern 7.499886pt\mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{\makebox% [7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}}{% \makebox[7.499886pt][c]{\scriptscriptstyle}}\leavevmode{n}\kern 7.499886pt% \mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{% \textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c% ]{\scriptscriptstyle}}\leavevmode{n}\kern 7.499886pt\mathchoice{\makebox[7.4% 99886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[% 7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}% \leavevmode{n}\kern 7.499886pt\mathchoice{\makebox[7.499886pt][c]{% \displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c% ]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}}_{\kern-121.% 498146pt\kern-91.498604pt\kern-61.499062pt\kern-31.499519pt\mathchoice{% \makebox[7.499886pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{\textstyle% }}{\makebox[7.499886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c]{% \scriptscriptstyle}}\kern 7.499886pt\leavevmode{k}\mathchoice{\makebox[7.4998% 86pt][c]{\displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.4% 99886pt][c]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}% \kern 7.499886pt\leavevmode{k}\mathchoice{\makebox[7.499886pt][c]{% \displaystyle}}{\makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c% ]{\scriptstyle}}{\makebox[7.499886pt][c]{\scriptscriptstyle}}\kern 7.49988% 6pt\leavevmode{k}\mathchoice{\makebox[7.499886pt][c]{\displaystyle}}{% \makebox[7.499886pt][c]{\textstyle}}{\makebox[7.499886pt][c]{\scriptstyle}% }{\makebox[7.499886pt][c]{\scriptscriptstyle}}\kern 7.499886pt\leavevmode{k}% }}=\frac{k!}{(k-n)!}.$

1.3

Everyone has ${\left({{k}\atop{r}}\right)}$ ways to receive postcards. The $n$ distinct persons implies exponent $n$. Therefore the answer is

 ${\left({{k}\atop{r}}\right)}^{n}.$

1.4

Which is equivalent to distribute $m$ identical balls into $n$ distinct bins unrestrictedly. Therefore the answer is

 $\left({\left({{m}\atop{n}}\right)}\right)={\left({{m+n-1}\atop{n-1}}\right)}.$

1.5

The $m$ kinds of postcards implies the answer satisfyes the product rule. Therefore we multiply them all,

 $\prod_{i=1}^{k}\left({\left({{m_{i}}\atop{n}}\right)}\right)=\prod_{i=1}^{k}{% \left({{m_{i}+n-1}\atop{n-1}}\right)}.$

2 Problem 2

Assuming we chose $i$ blue balls, then once we choose $j$ red balls satisfying $2n-(i+j)\leq n$ and $j\leq n$, i.e. $n-i\leq j\leq n$, we fixed a way to select $2n$ balls. Therefore the answer is

 $\displaystyle\sum_{i=0}^{n}\sum_{j=n-i}^{n}1$ $\displaystyle=\sum_{i=0}^{n}(n-(n-i)+1)$ $\displaystyle=\sum_{i=0}^{n}(i+1)$ $\displaystyle=(1+(n+1))\frac{n+1}{2}$ $\displaystyle=\frac{1}{2}(n+1)(n+2).$

3 Problem 3

3.1

Consider the powerset of $[n]$. $\forall a\in 2^{[n]}$, $\forall i\in a$, we connect an edge from $a$ to $a\setminus\{i\}$. Then the LHS denotes the number of the edges in our graph.

Our graph contains $2^{n}$ vertices, each vertex has degree of $n$. Therefore the number of edges is $2^{n}\times n/2$, i.e.

 $\sum_{i=0}^{n}i{\left({{n}\atop{i}}\right)}=\sum_{k=1}^{n}k{\left({{n}\atop{k}% }\right)}=n\cdot 2^{n-1}.$

3.2

 $\displaystyle\sum_{k=1}^{n+1}k^{2}{\left({{n+1}\atop{k}}\right)}$ $\displaystyle=\sum_{k=1}^{n}k^{2}{\left({{n+1}\atop{k}}\right)}+(n+1)^{2}$ $\displaystyle=\sum_{k=1}^{n}k^{2}{\left({{n}\atop{k}}\right)}\cdot\frac{n+1}{n% +1-k}+(n+1)^{2}$ $\displaystyle=(n+1)[\sum_{k=1}^{n}k{\left({{n}\atop{k-1}}\right)}+n+1]$ $\displaystyle=(n+1)[(1{\left({{n}\atop{0}}\right)}+2{\left({{n}\atop{1}}\right% )}+\cdots+(n+1){\left({{n}\atop{n}}\right)})]$ $\displaystyle=(n+1)[\sum_{k=0}^{n}k{\left({{n}\atop{k}}\right)}+\sum_{i=0}^{n}% {\left({{n}\atop{i}}\right)}]$ $\displaystyle=(n+1)[n\cdot 2^{n-1}+2^{n}].$

Therefore

 $\sum_{k=1}^{n}k^{2}{\left({{n}\atop{k}}\right)}=n[(n-1)2^{n-2}+2^{n-1}].$

4 Problem 4

4.1

Let $f_{0}(i)$ denote the number of ’/’ in the left of $x=i$, and $f_{1}(i)$ denote the number of ’$\backslash$’ in the left of $x=i$. Since the line can not be under x-axis, $\forall i,f_{0}(i)\geq f_{1}(i)$. This implies the Catalan number. Therefore the answer is

 $\frac{{\left({{2n}\atop{n}}\right)}}{n+1}.$

4.2

Any line which consists of $n$ ’/’ and $n$$\backslash$’ and starts at $(0,0)$ must end at $(2n,0)$. Then the answer is $2n$ choose $n$, i.e.

 ${\left({{2n}\atop{n}}\right)}.$

5 Problem 5

Consider one of the ends of the rectangle, there can be a $2\times 1$ block or a $2\times 2$ block or two $1\times 2$ blocks. Therefore

 $f(n)=f(n-1)+2f(n-2).$

Notice that $f(1)=1$, $f(2)=3$, then $f(0)=1$. Let $G(x)$ be the generating function we need, then

 $\displaystyle G(x)$ $\displaystyle=\sum_{n\geq 0}f(n)x^{n}$ $\displaystyle=1+x+\sum_{n\geq 2}f(n)x^{n}$ $\displaystyle=1+x+\sum_{n\geq 2}(f(n-1)+2f(n-2))x^{n}$ $\displaystyle=1+x+x^{2}\sum_{n\geq 0}(f(n+1)+2f(n))x^{n}$ $\displaystyle=1+x+x^{2}(1+\sum_{n\geq 1}(f(n)+2f(n-1))x^{n})+2x^{2}G(x)$ $\displaystyle=1+x+x^{2}(G(x)+2xG(x))+2x^{2}G(x)$ $\displaystyle=1+x+3x^{2}G(x)+2x^{3}G(x)$
 $\displaystyle G(x)$ $\displaystyle=\frac{1+x}{1-3x^{2}-2x^{3}}$ $\displaystyle=\frac{1}{1-x-2x^{2}}$ $\displaystyle=\frac{1}{(1+x)(1-2x)}$ $\displaystyle=\frac{1}{3}(\frac{2}{1-2x}+\frac{1}{1+x})$ $\displaystyle=\frac{1}{3}(2\sum_{n\geq 0}(2x)^{n}+\sum_{n\geq 0}(-x)^{n}).$

Therefore

 $f(n)=\frac{1}{3}(2^{n+1}+(-1)^{n}).$

6 Problem 6

6.1

Let $f_{0}(n)$ denote the number of strings end with $0$ and are at length of $n$. Similarly, $f_{1}(n)$ denote the strings end with $1$. Notice that

 $\displaystyle f_{0}(n)=f_{0}(n-1)+f_{1}(n-1)=s_{n-1}$ (appending a 0) $\displaystyle f_{1}(n)=f_{0}(n-1)=s_{n-2}$ (appending a 1) $\displaystyle s_{n}=f_{0}(n)+f_{1}(n)=s_{n-1}+s_{n-2}.$

Since $s_{1}=2$, $s_{2}=3$, $s_{n}$ is the Fibonacci number begins with $s_{0}=1$, $s_{1}=2$.

6.2

Let $f_{0}(n)$ denote the number of strings end with $0$ and are at length of $n$. Similarly, $f_{1}(n)$ denote the strings end with $01$ and $f_{2}(n)$ denote $011$. Notice that

 $\displaystyle f_{0}(n)=f_{0}(n-1)+f_{1}(n-1)+f_{2}(n-2)=t_{n-1}$ (appending a 0) $\displaystyle f_{1}(n)=f_{0}(n-1)=t_{n-2}$ (appending a 1) $\displaystyle f_{2}(n)=f_{1}(n-1)=t_{n-3}$ (appending a 1) $\displaystyle t_{n}=f_{0}(n)+f_{1}(n)+f_{2}(n)=t_{n-1}+t_{n-2}+t_{n-3}$ $\displaystyle t_{1}=2$ $\displaystyle t_{2}=4$ $\displaystyle t_{3}=7$ $\displaystyle t_{0}=1$

Let $G(x)$ denote the generating function we need, then

 $\displaystyle G(x)$ $\displaystyle=\sum_{n\geq 0}t_{n}x^{n}$ $\displaystyle=1+2x+4x^{2}+\sum_{n\geq 3}(t_{n-1}+t_{n-2}+t_{n-3})x^{n}$ $\displaystyle=1+2x+4x^{2}+x\sum_{n\geq 3}t_{n-1}x^{n-1}+x^{2}\sum_{n\geq 3}t_{% n-2}x^{n-2}+x^{3}\sum_{n\geq 3}t_{n-3}x^{n-3}$ $\displaystyle=1+2x+4x^{2}+x(G(x)-1-2x)+x^{2}(G(x)-1)+x^{3}G(x)$ $\displaystyle G(x)$ $\displaystyle=\frac{1+x+x^{2}}{1-x-x^{2}-x^{3}}.$

7 Problem 7

7.1 Assuming the votes is distinguishable

Enumerate a vote of Han Meimei as the first vote, then the problem is reduced to $p-1$ and $q$ votes and we have to make sure the votes of Han Meimei is not less than votes of Li Lei in the whole vote counting process. This implies the Catalan numbers. We assign orders to $q$-th Catalan numbers and then insert the remaining votes of Han Meimei into the votes sequence. Hence the number of ways is

 $\displaystyle pC_{q}q!q!\prod_{i=2q+i}^{p+q-1}i$ $\displaystyle=p\frac{\prod_{i=q+2}^{2q}i}{q!}q!q!\prod_{i=2q+1}^{p+q-1}$ $\displaystyle=\frac{(p+q-1)!p}{q+1}.$

And the probability is

 $\frac{p(p+q-1)!}{(q+1)(p+q)!}=\frac{p}{(q+1)(p+q)}.$

7.2 Assuming the votes is indistinguishable

Let $f(p,q)$ denote the number of ways we desired. Consider $p$ and $q$ represent a location in Cartesian coordinate system, $f(p,q)$ represents number of paths that start from $(0,0)$ goto $(p,q)$ and consisted of up or right and do not cross three line segments: $(0,0)-(1,0)$, $(1,0)-(1+q,q)$ and $(q+1,q)-(p,q)$. Observation:

 $\displaystyle f(p,q)=\begin{cases}1&(p=q=0)\\ 0&(p\leq q\lor p<0)\\ f(p-1,q)+f(p,q-1)\end{cases}.$

Then we observe that $f(p,q)=\sum_{i=0}^{q}f(p-1,i)=\sum_{i=q}^{p}f(i,q-1)$.

I can not figure out a solution for this recursion. According to [1], the answer is $C(p-1,q)$ where $C(n,k)={\left({{n+k}\atop{n}}\right)}\frac{n-k+1}{n+1}$ is the Catalan’s triangle. Therefore the answer we desired is

 ${\left({{p+q-1}\atop{q}}\right)}\frac{p-q}{p}.$

And the probability is

 ${\left({{p+q-1}\atop{q}}\right)}\frac{p-q}{p{\left({{p+q}\atop{p}}\right)}}=% \frac{p-q}{p+q}.$

References

• 1 Knuth, Donald E. ”The Art of Computer Programming, Volume 4: Generating All Trees; History of Combinationatorial Generation, Fascicle 4.” (2006).