Pascal’s Triangle Reloaded: Combinations with repetitions

Photo by Shaun Anyi https://www.flickr.com/photos/shaunanyi/10126810486

In my previous post on Pascal’s triangle I showed how to derive the formulas for permutations and combinations and why they correspond to binomial coefficients. These formulas are easy to derive. As an exercise I tried deriving the formula for combinations allowing repetitions and found it hard. I almost gave up but a friend encouraged me with “You’ve already spent a month on it, you might as well keep going.” Not sure that’s logical advice but I’m glad I followed it because it paid off. This post dives deeper into the tantalising triangle.

A reminder: (5 choose 3) allowing repetitions means: choose 3 symbols from 5 symbols, allowing repetitions. (5 choose 3) with repetitions using symbols ABCDE we can start enumerating the combinations like so:

The normal formula for combinations (n choose k) doesn’t allow repetitions and is

I tried to see if there was a similar relationship between the permutations and combinations when allowing repetitions but I couldn’t identify groups of the same size among the permutations, ie. I couldn’t find a common factor.

I tried looking for other patterns but I struggled. I got frustrated. I asked my math friends. One of them said something about how these kind of things build up from a base case. I didn’t know how to use that advice. Another friend reassured me it was a non-trivial problem and I should not give up. I knew there was a formula, so I knew it was possible. It was a bit like knowing that someone else had successfully climbed a mountain that seemed impossible for me to climb.

I went back to the drawing board and tried to understand how the combinations were built recursively. I tried on small examples and found the recursive structure to be

I use the r here to mean (n choose k) allowing repetitions. I found this structure by using small examples, like

Let’s work through this to understand why it is so (if this stuff bores you, skip ahead). (3 choose 2)r gives us the following 6 combinations:

The first column is the combinations of (3 choose 1)r and we just stick an A in front of them — that is all possible combinations involving A. Then we take A out and do the same thing: the second column is combinations of (2 choose 1)r, at that is all the combinations involving B. Then we just have C left, which is (1 choose 1)r.

When we do (n choose k) allowing repetitions, k can actually be larger than n. The recursive formula also works for those examples:

As I was verifying the recursive formula with more complex examples, I noticed some familiar looking numbers:

Those are numbers from Pascal’s triangle!

That means they correspond to the normal combinations-without-repetitions, (n choose k), numbers. I wrote down a mapping from some examples:

And found the correlation to be:

Which means the formula is:

I was excited when I found this because it’s the hardest puzzle I’ve struggled with in a while. I verified my formula by comparing results with the function in the python combinatorics module for large n and k.

I like to understand why formulas work. I was curious why (n choose k) allowing repetitions is equal to (n+k-1 choose k). I stared at some combinations with repetitions until I found a way to make a correlation. I substituted the repeated symbols with new symbols and got the correlation:

This shows that (3 choose 2)r = (4 choose 2). A more complex example:

This shows (3 choose 3)r = (5 choose 3).

If we list the combinations in order we can substitute repetitions by introducing a new symbol which means “repeat the symbol at position x”. In order to be able to repeat a previous symbol we need at least the first symbol to exist, which means we can have up to k-1 new symbols. And that’s one interpretation for why (n choose k) with repetitions is equivalent to (n+k-1 choose k) without repetitions. Neat, right? The other solutions on the internet are also neat.

The numbers representing combinations allowing repetitions are numbers in Pacal’s triangle, just like the numbers representing combinations without repetitions. Let’s compare the “mappings”. Here’s the usual mapping for combinations without repetitions (the binomial coefficients):

We can apply the mapping (n choose k) = (n + k-1 choose k), to get the mapping for the combinations with repetitions:

We know that numbers in Pascal’s triangle are the sum of the two diagonally above it. From this we can derive a recursive rule about combinations with repetitions:

Let’s convince ourselves that this works out using (3 choose 3) allowing repetitions of the symbols ABC as an example. If we enumerated (3 choose 2) allowing repetitions and stick an A in front of them as the final choice we have all combinations that contain A.

What’s left are the combinations allowing repetitions using symbols other than A:

That’s 6 + 4 = 10 combinations, which works out.

I was happy to have understood the formula better but something was still bothering me. One of my first ideas to find the formula was: say we are combining scoops of ice cream and allowing repetitions. Say we have 5 flavours and we want to build an ice cream with 4 scoops. This is (5 choose 4) with repetitions. Then one process would be to find all the ways we can sum to 4 — (4),(3,1),(2,2),(2,1,1),(1,1,1,1) and for each arrangement, populate it with 5 flavours. For example, the first arrangement with 4 scoops of one flavour, we would have 5 possibilities. Then for (2,1,1) we want 2 scoops of the same flavour and two unique scoops different: we have (5 choose 3) flavour combinations, but then with each flavour combination we have to swap which flavour has 2 scoops, so its (5 choose 3) * 3.

Which of these ice creams would you like?

To calculate (n choose k) or (num_flavours choose num_scoops) with repetitions using this process, we could do the following:

1. Enumerate all the ways to sum to k using numbers 1..k-1 (each sum is an arrangement of scoops eg. (2,1,1) means 2 scoops of the same flavour, 1 unique flavour, 1 unique flavour)
2. For each arrangement we get from step 1, determine the number of ways of combining the flavours into each arrangment — (n choose j), where j is the number of numbers in the sum, eg. (5 choose 3) for the sum (2,1,1)
3. For each combination of “flavours” in each sum “arrangement”, determine the number of different ways the flavours can occur in that arrangment, eg. for every 3 flavour combination in the arrangement (2,1,1), there are 3 different ways they can be arranged because each flavour can be the one that is repeated twice.

This kind of step-by-step process is called an algorithm — computer science stuff. It’s more complicated than the formula. There’s no reason you would want to calculate it like this if there is an algebraic formula. I just wanted to see if there was a relation between the numbers in step 1 (the number of ways to sum to k using the natural numbers less than it) and the number of (n choose k) with repetitions. I was secretly hoping these sum-numbers would also be Pascal triangle numbers. I tried to find a formula for them but couldn’t. It turns out the concept of these sum-numbers are Partitions in number theory. There doesn’t seem to be a formula for them so they have to be calculated using an algorithm.

While I was trying to find a formula for partitions, I found a different cool relation:

The generalisation being:

Let’s convince ourselves this works with the example (4 choose 4)r which is the same as (7 choose 4) because it’s as if we had 3 extra symbols that tell us which position to repeat (1..k-1). We want the number of combinations of 4 symbols out of these 7 symbols

First imagine we want to create combinations using all the extra symbols.

There is only one place left for the original symbols. So there are (4 choose 1) ways of choosing the main symbols and there is (3 choose 3) or only 1 way to choose the extra symbols. So there are (4 choose 1) * (3 choose 3) combinations of this type: AEFG, BEFG, CEFG, DEFG. Because our extra symbols mean repeat 1st position, repeat 2nd position, and repeat 3rd position, these combinations correspond to AAAA, BBBB, CCCC, DDDD.

Now imagine we want to create combinations using just two of the extra symbols. There are (3 choose 2) ways to choose from the 2 extra symbols:

and for each of these we can insert (4 choose 2) pairs of of the main symbols. For example, all the possible combinations from the first arrangement are: AEFB, AEFC, AEFD, BEFC, BEFD, CEFD. These correspond to AAAB, AAAC, AAAD, BBBC, BBBD, CCCD. So there are (3 choose 2) * (4 choose 2) strings of this type.

We can continue by creating combinations with just one extra symbol, and then none.

Lastly I want to show a stunning and simple property of numbers that represent combinations.

It’s plain to see but it’s not immediately obvious that the diagonals are sums of sums of sums… (∑ i is summation notation). If we draw out the combinatoric trees, we can see pictorially that they are sums of sums of sums. Here are the trees for (5 choose 3):

And here’s the equivalent number for (3 choose 3) with repetitions.

The point is, if we see trees appearing like this, then we know it must be a combinatoric number, a number from The Triangle!

Wow. All I wanted to do was derive as an exercise the formula for combinations with repetitions and I find out all this. I’m also not finished with my investigations. I can’t wait to publish this so I can start on the next post. I’m reading through this awesome historical perspective on mathematical forays into The Triangle.