Back-tracking Pascal's triangle

There's a central function of combinatorics, known as Pascal's triangle, which is in principle defined on pairs of natural numbers: however, it's capable of being extended to pairs of complex numbers, albeit with complications wherever the first of them is a negative integer. On this page, I set out how we can resolve those complications, but first I must provide some background.

Pascal's triangle

The function in question answers the question how many ways are there to chose m items from a set of n items ? Write this as chose(n, m). Quite plainly, if m > n the answer is none, i.e. chose(n, m) = 0; equally, if m is n or 0, there's only one set of m items we can select – either the empty set, or all n items. As for the rest, we can express chose(n) in terms of chose(n−1) by considering the implications of marking (an arbitrary) one of our n items and asking whether it's in our chosen set of m items. Each way of selecting m items from our set of n either does or doesn't select the marked item, so the ways of chosing m items from a set of n can be written as a sum of: the number of ways of chosing m of the n−1 unmarked items; plus the number of ways of chosing (the marked item and) m−1 of the remaining n−1 items. Thus

Now, there's a touch of asymmetry in chose's handling of its two arguments, and the analysis gets noticeably cleaner if I eliminate that, so I define a function F by F(n, m) = chose(n+m, m), so chose(n, m) = F(n−m, m) and our recurrence relation becomes:

F(n, m)
= chose(n+m, m)
= chose(n+m−1, m) +chose(n+m−1, m−1)
= F(n−1, m) +F(n, m−1)

with F(0, m) = 1 = F(n, 0) for all natural n, m expressing the chose(n,0) and chose(n, n) results. This enables us to compute all values of F(n, m) for natural n, m. Here are the first few:

↓n \ m→0123456

If you truncate this table along a diagonal of constant n+m, you get Pascal's triangle: the truncated diagonal of the triangle implies the next diagonal line to be added below and to the right of it. The usual presentation of Pascal's triangle is as a diagram of chose's values, so shear the above, so that its top row becomes the diagonal downwards and to the right, to get the orthodox layout.

Note that an interesting thing happens if you look at the corresponding table of F(n, m) reduced modulo 3 (i.e. representing each whole number by whichever of {0, 1, 2} differs from it by a multiple of 3): you get a discrete semblance of the Sierpinsky triangle.

The standard formula

We can, in fact, express chose(n, m) as a formula in n and m, using the factorial function, which gives the number of permutations of a set of given size. Its value for a natural number n is written n! and can be computed from 0! = 1, (1+n)! = n!.(1+n); alternatively, n! = product(:successor|n). Using this, we can write chose(n, m) as n!/m!/(n−m)! (hence F(n, m) = (n+m)!/n!/m!) because: we can form a list of the m chosen items followed by the n−m unchosen items; permuting the first m among themselves or the last n−m among themselves doesn't change which are the chosen items; going through all permutations of the whole list should yield all possible choices of m items as the first m entries in the list. There are n! permutations of the whole list; but this gives us m!.(n−m)! lists for each choice of m items as the first m in the list.

We can confirm the formula for F (hence trivially that for chose) inductively for natural n, m by: first observe that it holds true whenever n or m is zero (so we only have to demonstrate it for positive n, m) and, in particular, for any natural n, m whose sum is less than 2; then, for given positive n, m, inductively suppose that the formula holds true for any pair with smaller sum, hence in particular for F(n−1, m) and F(n, m−1), so

F(n, m)
= F(n−1, m) +F(n, m−1)
= (n+m−1)!/m!/(n−1)! +(n+m−1)!/(m−1)!/n!
= n.(n+m−1)!/m!/n! +m.(n+m−1)!/m!/n!
= (n+m).(n+m−1)!/m!/n!
= (n+m)!/m!/n!

From this we can induce that this formula holds true for all natural n and m.

Now, factorial can be expressed in terms of the gamma function, Γ, as n! = Γ(1+n); and Γ is defined on the whole complex plane, save for a simple pole at each non-positive integer; for x near 0 and natural k, Γ(x−k) is approximately (−1)k/k!/x. Consequently, we can extend our definition of F(n, m) (hence of chose(n, m) also) to allow n and m to take any value in the complex plane. Thus

The poles of Γ at non-positive integers imply a pole of factorial at each negative integer. If z+w isn't a negative integer and either w or z is, F(w, z) is necessarily zero. If w and z aren't integers and z+w is a negative integer, we necessarily get a pole (i.e. as z+w approaches a negative integer, F(w, z) goes to infinity unless either w or z approaches an integer as fast as z+w does – in which case both necessarily do; and at least one of them is negative).

Filling in the gaps

The question that then remains is: what happens when w and z are integers whose sum is negative ? We can reasonably hope, when both w and z are negative integers, that the two infinities in the denominator should overcome the one in the numerator to make F(w, z) be zero. It then remains only to make that hope more substantial and to consider the case where one input is a negative integer and the other is a (smaller) natural number. There are essentially three ways to try to approach the problem:

Analysis of the first two can be pursued without ever invoking the Γ function (to extend F and choose to the complex plane); we need only extend F to let n and m take arbitrary integer values, rather than only natural values.

Rearranged formula

If we trust in F(n, m) = (n+m)!/n!/m! and interpret ratios of factorials suitably, we can get values for the cases where n, m aren't both natural. To be specific, interpret i!/j! as 1 when i = j, otherwise:

which may be obtained by applying the inductive rule for factorials, (1+n)!/n! = 1+n, even when n isn't natural. (This is obviously bogus, but gets correct answers in a straightforward way.) For the case n<0≤m<−n, we can re-write (n+m)!/n! this way, as product(: n+1+i ←i |m), in which each factor is a negative integer, so we can negate each to re-write this as a product of consecutive positive integers and hence as a ratio of factorials of naturals:

F(n, m)
= (n+m).(n+m−1)…(n+1)/m!
= (−1)m.(−(1+n))!/(−(1+n+m))!/m!
= (−1)m.F(−(1+n+m), m)

When m≥−n>0, one of the factors in (n+m)!/n! = (n+m)…(n+1) is zero so dividing by (non-zero) m! gives F(n,m) = 0. For n≥0>m, F(n, m) is implied by symmetry applied to either this or the previous. When n and m are both negative, n+m < n gives us (n+m)!/n! = 1/n/…/(n+m+1), with every factor in the denominator negative, and 0 > m gives 1/m! = 0!/m! = 0.(−1)…(1+m), whence F(n, m) = (n+m)!/n!/m! = 0…(1+m)/n/…/(n+m+1) = 0, since all terms in the denominator are non-zero.

Reversed recurrence

The recurrence relations give us, for positive n, 1 = F(n, 0) = F(n−1, 0) +F(n, −1) = 1 +F(n, −1), whence F(n, −1) = 0 for all positive naturals n. Symmetrically, F(−1, m) = 0 for all positive naturals m. Given any natural i for which F(n, −i) = 0 for all naturals n≥i: we can infer, for n>i, 0 = F(n, −i) = F(n−1, −i) +F(n, −i−1) = F(n, −i−1), whence the condition that held for i also holds for i+1. Thus, inductively, F(n, m) = 0 whenever n≥0>m (or, by symmetry, m≥0>n) with n+m ≥ 0, confirming the zeros I infered from behaviour of Γ before I started filling in gaps.

Next, we must wind backwards to deal with the F(n, m) when n+m = −1. We have 1 = F(0, 0) = F(−1, 0) +F(0, −1); symmetry very much wants us to assert F(−1, 0) = F(0, −1) and hence that each is 1/2; but all we can be sure of is that the two sum to 1. So let F(−1, 0) = k and F(0, −1) = h, with k+h = 1. For every positive integer i, 0 = F(i, −i) = F(i−1, −i) +F(i, −(1+i)) so we can infer F(i, −(1+i)) = h.(−1)i; likewise, 0 = F(−i, i) = F(−(1+i), i) +F(−i, i−1) yields F(−(1+i), i) = k.(−1)i. It's interesting to compare these results with what we get from rearranging the formula above: there, F(i, −(1+i)) = (−1)i.F(0, i) = (−1)i without the factor of h or, for the symmetric partner, the factor of k.

Indeed, if we look at the results from re-arranging the formula, we find that F(−1, 0) = 1 = F(0, −1) and their sum isn't equal to F(0, 0): the recurrence relationship is violated at n = 0 = m. This is not entirely unreasonable: this is the physically realizable (so interpretation of the original derivation of the recurrence relationship should and can be scrutinized for validity) case of an empty set, from which we must select an empty set; and, since it's empty, we can't mark one of its members and classify selections according to whether or not the marked member is selected; so the derivation of the recurrence breaks down here.

From the central few values for F(n, m) with n+m+1 = 0 we obtain:

In principle, this doesn't tell us enough to be sure of the values; but, if we accept that F(n, m) is zero whenever n and m are both negative, as anticipated earlier (and justified by the Γ approach, below), we can infer that F(0, i) = h and F(i, 0) = k for all negative integers i.

Rather than exploring the data and discovering the patterns that arise, I'll now simply exploit what I know from the first analysis to provide the formula that I can inductively prove holds valid for the remaining cases. From the above, we know that F(i, −(1+n+i)) = h.(−1)i.F(i, n) holds true for n = 0 and every natural i. We also know F(0, −(1+n)) = h, so F(i, −(1+n+i)) = h.(−1)i.F(i, n) holds true for i = 0 and any natural n. So suppose that, for some given positive naturals n and m, F(i, −(1+j+i)) = h.(−1)i.F(i, j) for natural i, j whenever either j is in n, or j = n and i is in m. We certainly have this for the case n = 1 or, once we've established it for all j when i < n, for i = n and j = 1. Then observe:

F(m, −(1+n+m))
= F(m, −(n+m)) −F(m−1, −(n+m))
= F(m, −(1+(n−1)+m)) −F(m−1, −(1+n+(m−1)))
= h.(−1)m.F(m, n−1) −h.(−1)m−1.F(m−1, n)
= h.(−1)m.(F(m, n−1) +F(m−1, n))
= h.(−1)m.F(m, n)

whence we can induce that this does, indeed, hold true for every natural n, m. An entirely analogous analysis passes through without difficulty for F(−(1+n+m), m) save that k replaces h.

Limiting values

For natural k and small complex x, we have Γ(x−k) ≈ (−1)k/k!/x, so consider F(n+x, m+y) with n, m integers whose sum is negative. If both are negative (so −(1+n) and −(1+m) are naturals), we get

F(n+x, m+y)
= Γ(1+n+m+x+y)/Γ(1+n+x)/Γ(1+m+y)
≈ (−1)1+n+m +1+n +1+m.x.y.(−(1+m))!.(−(1+n))!/(−(1+n+m))!/(x+y)
= (1/n +1/m)/F(−n,−m)/(1/x +1/y)

which does, indeed, tend to zero as either x or y tends to zero, supporting the hope expressed above.

Alternatively, one integer is negative and the other is not (but is smaller, so that their sum is still negative). By symmetry of F, it suffices to consider the case n<0≤m<−n. So, for a small complex z, we get:

F(m, n+z)
= Γ(1+m+n+z)/Γ(1+m)/Γ(1+n+z)
≈ (−1)1+m+n +1+n.z.(−(1+n))!/m!/(−(1+m+n)!)/z
= (−1)m.(−(1+n))!/m!/(−(1+m+n)!)
= (−1)m.F(−(1+n+m), m)

in which −(1+n+m) and m are given to be naturals. Since z is entirely absent from the final form, we can let it tend to zero without difficulty. Note, for contrast, that the matching analysis for chose would have obliged us to look at chose(N+x, M) for N<0≤M (which would fall out in roughly the same way) and separately at chose(N+x, M+y) for M≤N<0 with x and y varying independently, which yields a more complicated analysis !

Extended table

↓n \ m→−5−4−3−2−1012345

Valid CSSValid HTML 4.01 Written by Eddy.