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.
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:
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→ | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 2 | 1 | 3 | 6 | 10 | 15 | 21 | 28 |
| 3 | 1 | 4 | 10 | 20 | 35 | 56 | 84 |
| 4 | 1 | 5 | 15 | 35 | 70 | 126 | 210 |
| 5 | 1 | 6 | 21 | 56 | 126 | 252 | 462 |
| 6 | 1 | 7 | 28 | 84 | 210 | 462 | 924 |
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.
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 items. 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
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 n, Γ(x−n) is approximately (−1)n/n!/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 one of them is negative).
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:
When n<0≤m<−n, we can re-write (n+m)!/n! as product(: n+1+i ←i |m) in which each factor is a negative integer; we thus obtain:
For n and m both negative, we can do the same but now obtaining F(n, m) = (n+m).(n+m−1)…(n+1)/m! in which the numerator is a product of finitely many non-zero finite terms and the numerator is infinite, so we should expect the value 0, although we obtain no clear way to establish that this actually does hold true.
Note that (aside from the unestablished zero when both inputs are negative) this analysis and the next can be pursued without ever invoking the Γ function as a way to extend our function to the complex plane; we need only extend F to let n and m take arbitrary integer values, rather than only natural values.
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:
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.
For small complex x and natural n, we have Γ(x−n) ≈ (−1)n/n!/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
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:
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 !
| ↓n \ m→ | −5 | −4 | −3 | −2 | −1 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| −5 | 1 | −4 | 6 | −4 | 1 | ||||||
| −4 | 1 | −3 | 3 | −1 | |||||||
| −3 | 1 | −2 | 1 | ||||||||
| −2 | 1 | −1 | |||||||||
| −1 | 1 | ||||||||||
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | −4 | −3 | −2 | −1 | 1 | 2 | 3 | 4 | 5 | 6 | |
| 2 | 6 | 3 | 1 | 1 | 3 | 6 | 10 | 15 | 21 | ||
| 3 | −4 | −1 | 1 | 4 | 10 | 20 | 35 | 56 | |||
| 4 | 1 | 1 | 5 | 15 | 35 | 70 | 126 | ||||
| 5 | 1 | 6 | 21 | 56 | 126 | 252 |
Written by Eddy.