Question

Prove combinatorially: {{n \ choose x)= {{k+1 \ choose n-1)

This question is asking to prove combinatorially whether  n multi-choose k is equal to k+1 multi-choose n-1

Thank you

Answer 1

$n$ multichoose $k$ counts the multisets of cardinality $k$ that can be made from a set of $n$ distinct elements. Consider a $k$-element multiset made from the set $\{1,\ldots,n\}$; we can represent it schematically as a string of $k$ $0$s and $n-1$ $1$s, the $i$-th $1$ indicating the break between $0$s representing copies of $i$ and $0$s representing copies of $i+1$. However, we can reverse the rôles of $0$ and $1$ we have $k$ dividers and $n-1$ counters. The $k$ dividers break the string into $k+1$ sections, so it represents an $(n-1)$-element multiset chosen from $\{1,\ldots,k+1\}$.