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
chose(n, m) = chose(n−1,m) +chose(n−1, m−1)
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→
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.
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
F(w, z) = Γ(1+w+z)/Γ(1+w)/Γ(1+z)
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:
rearrange the formula in terms of factorials to avoid the poles.
try to extrapolate the recurrence relation backwards or
look for limiting values implied by the Γ formula just given,
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:
i!/j! = i.(i−1)…(j+1) when i > j
i!/j! = 1/j/(j−1)/…/(i+1) when i < j
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:
−k = F(−2, 1) = F(−3, 1) +F(−2, 0)
k = F(−1, 0) = F(−1, −1) +F(−2, 0)
h = F(0, −1) = F(−1, −1) +F(0, −2)
−h = F(1, −2) = F(1, −3) +F(0, −2)
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
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 !
Written by Eddy.