isi-entrance 2005 Q7

isi-entrance · India · solved Combinations & Selection Combinatorial Identity or Bijection Proof

Let $A_{m,n}$ denote the set of strictly increasing sequences $1 \leq \alpha_1 < \alpha_2 < \cdots < \alpha_m \leq n$ of integers, $B_{m,n}$ denote the set of non-negative integer solutions of $\alpha_1 + \alpha_2 + \cdots + \alpha_m = n$, and $C_{m,n}$ denote the set of strictly increasing sequences chosen from $\{1,2,\ldots,n\}$.
a) Construct a bijection from $A_{m,n}$ to $B_{m+1,n-1}$.
b) Construct a bijection from $A_{m,n}$ to $C_{m,m+n-1}$.
c) Find the number of elements in $A_{m,n}$.

a) Define $f(\alpha_1,\ldots,\alpha_m) = (\beta_1,\ldots,\beta_{m+1})$ where $\beta_1 = \alpha_1 - 1$, $\beta_i = \alpha_i - \alpha_{i-1}$ for $2 \leq i \leq m$, $\beta_{m+1} = n - \alpha_m$. This is a bijection from $A_{m,n}$ to $B_{m+1,n-1}$.
b) Define $g(\alpha_1,\ldots,\alpha_m) = (\beta_1,\ldots,\beta_m)$ where $\beta_i = \alpha_i + (i-1)$. This is a bijection from $A_{m,n}$ to $C_{m,n+m-1}$.
c) The number of elements in $B_{m,n}$ equals the number of non-negative integer solutions of $\alpha_1+\cdots+\alpha_m = n$, which is $\frac{(m+n-1)!}{n!(m-1)!}$. Since $A_{m,n}$ bijects with $B_{m+1,n-1}$, the number of elements in $A_{m,n}$ is $\frac{(m+n-1)!}{(n-1)!\, m!}$.

Let $A_{m,n}$ denote the set of strictly increasing sequences $1 \leq \alpha_1 < \alpha_2 < \cdots < \alpha_m \leq n$ of integers, $B_{m,n}$ denote the set of non-negative integer solutions of $\alpha_1 + \alpha_2 + \cdots + \alpha_m = n$, and $C_{m,n}$ denote the set of strictly increasing sequences chosen from $\{1,2,\ldots,n\}$.

a) Construct a bijection from $A_{m,n}$ to $B_{m+1,n-1}$.

b) Construct a bijection from $A_{m,n}$ to $C_{m,m+n-1}$.

c) Find the number of elements in $A_{m,n}$.

Paper Questions

Q1 Q2 Q3 Q4 Q5 Q6 Q7 Q8 Q9 Q10