Combinatorial Connections Not Concerning Connecticut

Brain isn't a hard drive. For starters, it's moister. It suffers more severe fragmentation issues. Also, you can increase information retention by adding more information. Because connections help to remember. Today, we are going to see the connections between r-simplex, combinations with repetitions, Pascal's triangle, non-decreasing functions and inspector Canardo.

How many ways are there to choose k elements among n distinct gallinaceans, allowing repetitions (à la "sampling with replacement")?

• For k = 1, that's n. I you disagree, please write a letter to your government.
• For k = 2, to see what happen, let's enumerate the choices for n = 5 items named a b c d e:

    aa, ab, ac, ad, ae,
        bb, bc, bd, be,
            cc, cd, ce,
                dd, de,
                    ee

Since order doesn't matter, I've sorted them alphabetically. Not only the items are sorted, but in a given item, each letter must be greater or equal than the previous (e.g. we skip ba as already covered by ab). If we replace letters by positive integers, we see that the searched value is the number of non-decreasing functions from [1..k] to [1..n]. Using the one-to-one transformation from such a function f to x -> f(x) + x, we see that's also the number of increasing functions from [1..k] to [2..n+k]. We uniquely define the latter functions by chosing k distinct elements in [2..n+k]. This allows us to conclude:

As you have noticed in the example there were 5 choices starting with a, 4 with b, 3 with c, 2 with d and 1 with e. This is a general pattern for k = 2, yielding the triangular numbers. Now, for k = 3 (keeping n = 5), we can resursively construct the choices as so:

• Fix the first letter as a. The following suffixes are all the items already seen for k = 2.
• Fix the first letter as b. The following suffixes mustn't contain a. Hence we must choose among 4 letters rather than 5.
• Etc until e, where the suffix must be ee. We get:

Adding the first triangular numbers gives a tetrahedral number (not to be confused with square pyramidal number). The same process applies for larger k, yielding the simplicial polytopic (aka r-simplex) numbers, which you can find as columns in a left justified Pascal triangle.

Reference: sand beach.

view raw combinatorial_connections.md hosted with ❤ by GitHub