Mastodawn

\({n+1 \choose k} = \sum_{i=0}^n {i \choose k-1}\)

In words, the above equation says that instead of choosing k things out of n+1 things, we will choose k-1 things out of a bunch of i things. Vary i from 0 to n, and add up all the \( {i \choose k-1} \). Somehow this summation also counts the number of ways of picking k things from n+1 things.

#Combinatorial #proof time!

The LHS is the number of ways of picking k things out of n+1 things. To get the RHS, we'll count the same thing but in a long-winded way. First, let the n+1 things be the numbers {1, 2, ..., n, n+1}. We'll condition on the largest number 𝑚 that gets picked, and then count the number of ways to pick the remaining k-1 things from all remaining smaller numbers. If 𝑚=1, then we have 0 smaller numbers and need to pick k-1 out of them ⟶ \( {0 \choose k-1} \). If 𝑚=2, then we only have 1 smaller number and need to pick 𝑘−1 numbers. As 𝑚 varies from 1 to 𝑛+1, the terms being added vary as \( {i \choose k-1} \) where 𝑖=𝑚−1.

Each of these ways is an independent way of picking k things, so by the sum rule, we get the RHS as the number of ways of picking k things from n-1.

Note that the same proof idea gives a really nice counting based proof for the formula for the sum of the first n natural numbers.

#math #counting

Show thread

Akshar Varma Feb 3, 2024

I came across the above result while trying to (combinatorially) solve the problem @susam wrote about here: https://susam.net/blog/combinatorics-coincidence.html

It is a really nice post going over some #math, specifically #combinatorics, #recurrences and more. There's also a bonus #nested #loops problem.

Combinatorics Coincidence - Susam Pal

Show thread

Akshar Varma Feb 3, 2024

In the process I also thought of a #binomial #coefficient interpretation for choosing k things out of a bag of n objects when the objects can be put back and picked again. In probability problems, this is referred to as picking "with replacement".

Usually, when we say, n choose k, we do not allow repeated choices, every chosen object has to be chosen once. In this case, I want to allow replacements but at the same time, I want to keep using my trusted n choose k idea.

Here's my way around this: We'll still be picking k things, but we'll pick them not from 1 to n but from the set {1, 2, ..., 𝑛, 𝑟₁, 𝑟₂, ..., 𝑟ₖ₋₁}. That is, in addition to the n objects, we add what I'm calling "replacement tokens" 𝑟ₓ. If any of the 𝑟ₓ gets picked, then it is interpreted as the 𝑥th choice was put back and you are now choosing to pick that again. Since the 𝑘th choice is not put back, we only need replacement tokens for choices 1 to k-1.

With these replacement tokens, the problem becomes a standard choose k things out of this set, which we can resolve using the binomial coefficient to get: \({ n+k-1 \choose k }\).

I believe the standard approach to this is via #StarsAndBars but I liked the idea of this "replacement token". Admittedly, I didn't want to use stars and bars here and made up some stuff which I happened to like. :)

#math #counting #proof