Binomial coefficient notated by recursive summations

Question

I was considering the number of configurations of elements in a 3-atom adsorbate binding site on a nanoparticle, and I got to wondering how many configurations there would be if there were $k$ atoms in the binding site and $n$ elements that the atoms could be (never mind how realistic or physically-relevant this is, I'm more interested in the math).

Just as an example, for a 3-atom binding site ($k=3$) and 3 elements $A$, $B$, and $C$ ($n=3$), there would be $10$ possible combinations: $$AAA \\ AAB \\ AAC \\ ABB \\ ABC \\ ACC \\ BBB \\ BBC \\ BCC \\ CCC$$

I tried a variety of forms to find a general case and eventually I found that for $k=2$, the number of configurations of the $k$ atoms would be the $n^{th}$ triangle number. Therefore, for a function $f(n, k) =$# of configurations, I found that $$f(n, 2) = \sum_{a=1}^n a = \frac{n(n+1)}{2}$$

I then noticed that for $k=3$, the number of configurations was always the sum of the first $n$ triangle numbers. Therefore, $$f(n, 3) = \sum_{a_1=1}^n \sum_{a_2=1}^{a_1} a_2 = \frac{n(n+1)(n+2)}{6}$$

Just briefly checking $k=4$, it seems to follow the same trend. Therefore it would appear that $$f(n, k) = \sum_{a_1=1}^n \sum_{a_2=1}^{a_1} \sum_{a_3=1}^{a_2} \cdots \sum_{a_{k-1}=1}^{a_{k-2}} a_{k-1} = \frac{(n+(k-1))!}{(n - 1)!\space k!}$$

After thinking myself so clever for finding such a relation without combinatorics, I of course noticed I had derived $\binom{n+k-1}{k}$, but that got me wondering... Maybe I'm just blind or maybe it's the fact that I've never taken a stats class and only ever briefly learned combinations/permutations, but I have never seen binomial coefficient defined in terms of repeated summations. Is this a widely-known fact?

Additionally, how could you write $\binom{n}{k}$ as a series of repeated summations? Using my previous example of $\binom{n+k-1}{k}$ as a reference, it is clear that for $\binom{n+k+x}{k}$, the final sum will be $$\cdots \sum_{a_{k+x}}^{a_{k+x-1}} a_{k+x} = \cdots$$

but I am unsure as for how to proceed when the case is $\binom{n}{k}$ as following the above pattern would leave me with $a_0$ and $a_{-1}$ for the lower and upper bounds respectively which does not really work since the subscript on the lower bound, upper bound, and summand should all be increasing for each additional summation.

Finally, is there a way to collapse all $k-1$ sums into a single summation?

Answer 1

Multiple summations

Summing using the hockey-stick identity, we have $$\begin{align} k=2:\;\;&\sum_{x_1=1}^n x_1& & &=\binom {n+1}2\\ k=3: \;\;&\sum_{x_1=1}^n\sum_{x_2=1}^{x_1}x_2 &&=\sum_{x_1=1}^n\binom {x_1+1}2 &=\binom{n+2}3\\ k=4: \;\;&\sum_{x_1=1}^n\sum_{x_2=1}^{x_1}\sum_{x_3=1}^{x_2}x_3 &=\sum_{x_1=1}^n\sum_{x_2=1}^{x_1}\binom {x_2+1}2 &=\sum_{x_1=1}^{n}\binom{x_1+2}3 &=\binom {n+3}4\\ &&\vdots\\ k=k:\;\;&\sum_{x_1=1}^n\sum_{x_2=1}^{x_1}\sum_{x_3=1}^{x_2}\cdots\sum_{x_{k-1}=1}^{x_{k-2}}x_{k-1} &&&=\binom {n+k-1}k\end{align}\\ $$

Collapsing the summations

The last cascade of summations may be collapsed by using the following notation:

$$\sum_{x_1=1}^n\sum_{x_2=1}^{x_1}\sum_{x_3=1}^{x_2}\cdots\sum_{x_{k-1}=1}^{x_{k-2}}x_{k-1}=\sum_{1\le x_{k-1}\le x_{k-2}\le\cdots \le x_2\le x_1\le n}x_{k-1} =\binom {n+k-1}k$$

---

Note that

$\displaystyle \binom {n+1}2$ are Triangular Numbers,

$\displaystyle \binom {n+2}3$ are Tetrahedral Numbers,

$\displaystyle \binom {n+3}4$ are Pentatope Numbers, and

$\displaystyle \binom {n+r-1}r$ are $r$-simplex Numbers.

---

To prove the result, it may be easier to index the summations from inside out, i.e.

$$\sum_{x_{k-1}=1}^n\sum_{x_{k-2}=1}^{x_{k-1}}\cdots \sum_{x_2=1}^{x_3}\sum_{x_1=1}^{x_2}x_1$$

Let $\displaystyle f(j)=\binom {x_j+j-1}j$.

Note that $$\begin{align} \sum_{x_j=1}^{x_{j+1}} f(j) &=\sum_{x_j=1}^{x_{j+1}} \binom {x_j+j-1}j\\ &=\binom {x_{j+1}+j}{j+1}\\ &=\binom {x_{j+1}+\overline{j+1}-1}{\overline{j+1}}\\ &=f(j+1) \end{align}$$ and that $f(1)=x_1$.

Hence $$\begin{align} &\;\;\;\;\sum_{x_{k-1}=1}^{x_k}\sum_{x_{k-2}=1}^{x_{k-1}}\cdots \sum_{x_3=1}^{x_4}\sum_{x_2=1}^{x_3}\sum_{x_1=1}^{x_2} x_1\\ &=\sum_{x_{k-1}=1}^{x_k}\sum_{x_{k-2}=1}^{x_{k-1}}\cdots \sum_{x_3=1}^{x_4}\sum_{x_2=1}^{x_3}\sum_{x_1=1}^{x_2} f(1)\\ &=\sum_{x_{k-1}=1}^{x_k}\sum_{x_{k-2}=1}^{x_{k-1}}\cdots \sum_{x_3=1}^{x_4}\sum_{x_2=1}^{x_3} f(2)\\ &=\sum_{x_{k-1}=1}^{x_k}\sum_{x_{k-2}=1}^{x_{k-1}}\cdots \sum_{x_3=1}^{x_4} f(3)\\ &=\vdots\\ &=\sum_{x_{k-1}=1}^{x_k} f(k-1)\\ &=f(k)\\ &=\binom {x_k+k-1}k\\ &=\binom {n+k-1}k\qquad\text{if }x_k=n\\ \color{red}{\Rightarrow \sum_{x_{k-1}=1}^n\sum_{x_{k-2}=1}^{x_{k-1}}\cdots \sum_{x_3=1}^{x_4}\sum_{x_2=1}^{x_3}\sum_{x_1=1}^{x_2} x_1} &\color{red}{=\binom {n+k-1}k} \end{align}$$

Answer 2

If you go all the way, you'll write your final summand $a_{k-1} =\sum_{a_k=1}^{a_{k-1}}1$ getting altogether $$ f(n, k) = \sum_{a_1=1}^n \sum_{a_2=1}^{a_1} \sum_{a_3=1}^{a_2} \cdots \sum_{a_{k-1}=1}^{a_{k-2}} \sum_{a_k=1}^{a_{k-1}}1 $$ So your nested summations are counting weakly decreasing sequences $n\geq a_1\geq a_2\geq\cdots\geq a_{k-1}\geq a_k\geq 1$. If one represents this as a histogram, namely a column of $a_1$ stacked squares followed by one of $a_2$ squares, and so on terminating with a column of $a_k$ squares, then the shape of the histogram is precisely determined by a path along its top border, starting at $(0,n)$, descending (if necessary) to $(0,a_1)$, then across to $(1,a_1)$, again descending if necessary to $(1,a_2)$, then across, and so on until ending at $(k,1)$. All in all you make $n-1$ descending steps and $k$ steps across, for a total of $n+k-1$ steps in all cases. Among those steps $k$ steps are horizontal (across a column), and they can be chosen in any set of positions, which makes for $ f(n,k)=\binom{n+k-1}k$ possibilities.

Yes, the interpretation of binomial coefficients as counting lattice paths is well known. Indeed the lattice path interpretation is often preferred over the subsets interpretation. For instance if you count the lattice paths in Pascal's triangle (for a properly aligned lattice) from the root to a given binomial coefficient, then every lattice path must pass through exactly one of the neighbouring coefficients in the row above it, and the total number of lattice paths found is the sum of the two numbers for those two coefficients. It follows that the lattice path counts satisfy Pascal's recurrence, and if you known that these numbers are equal to binomial coefficients, it follows that binomial coefficients also satisfy Pascal's recurrence. Lots of other identities between binomial coefficients can similarly be understood in terms of lattice paths.