Homework 2

combi_spring_25_hw_2.pdf

How many ways are there to choose $k$ squares on a $n \times n$ square board, such that no two chosen squares belong to the same column, or the same row.

Consider a $n\times n$ square board, we need to choose $k$ squares

For the first square, we have $n^2$ choices, then for the second, we need to remove one column and one row since no two chosen squares belong to the same column, or the same row.

Thus for the second square, we have $(n-1)^2$ choices

Analyously, for $k-1$-th square, we have $(n-(k-1)+1)^2$ choices

For $k$-th square, we have $(n-k+1)^2$ choices

Then since different choices of square's position will form a new way, thus we need to use multiplicative principle

That is the total ways $=\prod_{i=1}^{k}\left(n-i+1\right)^{2}$, then we have $f:\left\lbrace\text{ordered choice}\}\to\{\text{unordered choices}\}\right.$

Here every image has preimage where $|\text{preimage}|=$ $k!$, then use division principle, we have $\begin{aligned} \frac{\prod_{i=1}^{k}\left(n-i+1\right)^{2}}{k!} \end{aligned}$
Let $n$ be a natural number. Find the value of the sum $\begin{aligned} \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k} \end{aligned}$

When $n=2m,m\in\mathbb{N}$, $\begin{aligned} \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}=\sum_{k=0}^{m}\binom{2m}{2k} \end{aligned}$, then i claim it's equal to $2^{2m-1}$

Use induction to prove, Base case: $m=1$, then $\begin{aligned} \sum_{k=0}^{1}\binom{2}{2k} \end{aligned}=\binom20+\binom22=2=2^{2\times 1-1}$

Suppose it's true for $i\leq m-1$, then for $i = m$ we have:

$ \sum_{k=0}^{m}\binom{2m}{2k}=\sum_{k=0}^{m}\left\lbrack\binom{2m-1}{2k}+\binom{2m-1}{2k-1}\right\rbrack=\sum_{k=0}^{m}\left\lbrack\binom{2m-2}{2k}+2\binom{2m-2}{2k-1}+\binom{2m-2}{2k-2}\right\rbrack $

$ =\sum_{k=0}^{m-1}\binom{2m-2}{2k}+2\sum_{k=0}^{m}\binom{2m-2}{2k-1}+\sum_{k=0}^{m}\binom{2m-2}{2k-2} $, let $i=k-1,j=k-1$, then

$ =\sum_{k=0}^{m-1}\binom{2m-2}{2k}+2\sum_{i=0}^{m-1}\binom{2m-2}{2i+1}+\sum_{j=0}^{m-1}\binom{2m-2}{2j}=\sum_{k=0}^{m-1}\binom{2m-2}{2k}+2\sum_{i=0}^{m-1}\binom{2m-2}{2i}+\sum_{j=0}^{m-1}\binom{2m-2}{2j} $

$=2^{2m-3}+2\cdot2^{2m-3}+2^{2m-3}=2^{2m-1}$

Thus it is true

When $n=2m-1,m\in\mathbb{N}$, $\begin{aligned} \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}=\sum_{k=0}^{m-1}\binom{2m-1}{2k} \end{aligned}$, then i claim it's equal to $2^{2m-2}$

Use induction to prove, Base case: $m=1$, then $ \sum_{k=0}^{0}\binom{1}{2k} =\binom10=1=2^{2\times1-2}$

Suppose it's true for $i\leq m-1$, then for $i = m$ we have: $ \sum_{k=0}^{m-1}\binom{2m-1}{2k}=\sum_{k=0}^{m-1}\left\lbrack\binom{2m-3}{2k}+2\binom{2m-3}{2k-1}+\binom{2m-3}{2k-2}\right\rbrack $

$ =\sum_{k=0}^{m-2}\binom{2m-3}{2k}+2\sum_{k=0}^{m-1}\binom{2m-3}{2k-1}+\sum_{k=0}^{m-1}\binom{2m-3}{2k-2} $, let $i=k-1,j=k-1$, then

$ =\sum_{k=0}^{m-2}\binom{2m-3}{2k}+2\sum_{i=0}^{m-2}\binom{2m-3}{2i+1}+\sum_{j=0}^{m-2}\binom{2m-3}{2j}=\sum_{k=0}^{m-2}\binom{2m-3}{2k}+2\sum_{i=0}^{m-2}\binom{2m-3}{2i}+\sum_{j=0}^{m-2}\binom{2m-3}{2j} $

$=2^{2m-4}+2\cdot2^{2m-4}+2^{2m-4}=2^{2m-2}$

Thus it is true

Finally, the answer is $\begin{aligned} \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n}{2k}=2^{n-1} \end{aligned}$
Prove that for any positive integers $n, k$ with $k \leq n$ we have $\binom{n}{k}= \binom{k-1}{k-1}+ \binom{k}{k-1}+ \cdots + \binom{n-1}{k-1}.$

Let's use induction on $k$

When $k=1$, then $\binom{n}{1}=n=\binom{0}{0}+\binom{1}{0}+...+\binom{n-1}{0}=n$

Suppose it's true for $k$, then for $k+1$ we have $\binom{n}{k+1}=\binom{n-1}{k+1}+\binom{n-1}{k}=\binom{k}{k}+\dots+\binom{n-2}{k} +\binom{k-1}{k-1}+\dots+\binom{n-2}{k-1}$

$=\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+\dots+\binom{n-3}{k}+\binom{n-2}{k}$$+\binom{k-1}{k-1}+\binom{k}{k-1}+\binom{k+1}{k-1}+\binom{k+2}{k-1}+\dots+\binom{n-3} {k-1}+\binom{n-2}{k-1}$

$=\binom{k-1}{k-1}+\left\lbrack\binom{k}{k}+\binom{k}{k-1}\right\rbrack+\left\lbrack \binom{k+1}{k}+\binom{k+1}{k-1}\right\rbrack+\left\lbrack\binom{k+2}{k}+\binom{k+2} {k-1}\right\rbrack+\ldots+\left\lbrack\binom{n-3}{k}+\binom{n-3}{k-1}\right\rbrack +\left\lbrack\binom{n-2}{k}+\binom{n-2}{k-1}\right\rbrack$

$=1+\binom{k+1}{k}+\binom{k+2}{k}+\binom{k+3}{k}+\ldots+\binom{n-2}{k}+\binom{n-1} {k}$

$=\binom{k}{k}+\binom{k+1}{k}+\binom{k+2}{k}+\binom{k+3}{k}+\ldots+\binom{n-2}{k} +\binom{n-1}{k}$

Thus it's true for $k+1$, then it's true for all $k\leq n$
Find a combinatorial argument in terms of lattice paths showing that for any $n, m, r$ we have $\binom{n}{m}\binom{m}{r}= \binom{n}{r}\binom{n-r}{m-r}.$

Consider that we start from $(0,0)$, we can walk $n$ steps and $m$ are steps moving right and $n-m$ are steps moving up. In this process, we want to marked $r$ steps in $m$ steps as special steps

Then we want to know how many paths there are to move to $(n-m,m)$ with different $r$ special and moving right steps

On the left hand, the possibilities of moving to $(n-m,m)$ is $\binom{n}{m}$, then we choose $r$ special step of $m$ steps, which is $\binom{m}{r}$

Then the result is $\binom{n}{m}\binom{m}{r}$

On the right hand, we first choose the special and moving right step, which is $\binom{n}{r}$.

Now we are in $(0,r)$, we need to walk $n-m$ up steps and $m-r$ right steps

Then the possibilities is $\binom{n-r}{m-r}$. Finally, the result is $\binom{n}{r}\binom{n-r}{m-r}$

‍