3. Some variants and generalizations


In [6] Hoggatt and Alexanderson give an interesting algorithm relating to the multinomial coefficients. We again take an anchor

æ
ç
è
k1
k2
... 
km
ö
÷
ø

and consider its nearest neighbours. Precisely we have, at level (n+1), the multinomial coefficients

æ
ç
è
n+1 
k1+1 
k2
... 
km
ö
÷
ø
æ
ç
è
n+1 
k1
k2+1 
... 
km
ö
÷
ø
æ
ç
è
n+1 
k1
k2
... 
km+1 
ö
÷
ø
;

at level n we have the m(m-1) multinomial coefficients

æ
ç
è
n
k1
k2
... 
ki-
ki+e
... 
kj-e
... 
km
ö
÷
ø
,     1 £ i < j£ m,     e = ±1;

and at level (n-1) we have the m multinomial coefficients

æ
ç
è
n-
k1-
k2
... 
km
ö
÷
ø
æ
ç
è
n-
k1
k2-
... 
km
ö
÷
ø
æ
ç
è
n-
k1
k2
... 
km-
ö
÷
ø
.

These m(m+1) coefficients, as they prove, may then be partitioned into m sets, each containing (m+1) coefficients, in such a way that the product of the coefficients in each set is a given number N, namely

N (n-1)!(n!)m-1(n+1)!
Õ (ki-1)!( Õ ki!)m-1 Õ (ki+1)!
,       (3.1)

which is thereby seen to be an integer. The method of partitioning is not claimed to be unique. This theorem may, in the case m=2, be regarded as a restatement of the Star of David Theorem, in the case a1=1, a2=-1; notice that we may certainly allow negative integers among the ai in the Star of David Theorem, so long as kj+ai remains positive. However, for m³3, the Hoggatt-Alexanderson Theorem diverges from what we have called the Hyperstar of David Theorem.

On the other hand we may generalize the Hoggatt-Alexanderson Theorem in the following direction. We regard the theorem we have described as the case (1,-1) of the following theorem.

Theorem 3.1 Given the multinomial anchor

æ
ç
è
n
k1
k2
... 
km
ö
÷
ø
we define its set of (p,q)-satellites to consist

at level (n+p) of the m coefficients
æ
ç
è
n+p
k1+p
k2
... 
km
ö
÷
ø
æ
ç
è
n+p
k1
k2+p
... 
km
ö
÷
ø
æ
ç
è
n+p
k1
k2
... 
km+p
ö
÷
ø

at level (n+q) of the m coefficients

æ
ç
è
n+
k1+q
k2
... 
km
ö
÷
ø
æ
ç
è
n+q
k1
k2+
... 
km
ö
÷
ø
æ
ç
è
n+q
k1
k2
... 
km+q
ö
÷
ø

and at level (n+p+q) of the m(m-1) coefficients

æ
ç
è
n+p+q
k1
k2
... 
ki-
ki+e
ki+1 
... 
kj-
kj+h
kj+1
... 
km
ö
÷
ø
,     1 £i < j £ m
(e, h) = (p,q)    or     (q,p).
 

Then these m(m+1) coefficients may be partitioned into m sets, each containing (m+1) coefficients, in such a way that the product of the coefficients in each set is the number N(p,q) given by

N(p,q) =  (n+p)!(n+q)!((n+p+q)!)m-1
Õ (ki+p)! Õ (ki+q)! ( Õ ki!)m-1
,       (3.2)

Corollary 3.2 The number N(p,q) is an integer.

For N(p,q) is a rational number whose mth power is an integer.

Note that p, q may take any integer values such that the factorial functions in (3.2) are applied to non-negative integers.

Of course the partitioning function is exactly that used in [6]; theirs is the hard work!

We may, just as for binomial coefficients, generalize the content of Section 1 substantially beyond the domain of multinomial coefficients. Indeed, in Section 1, all we require of the basic function of n, k1, k2,...,km is that it be a separable function; thus we may replace the multinomial coefficient by a function

F(n,k1,k2,...,km) = f(n)f1(k1)...fm(km)
,       (3.3)

An example of such a separable function is the q-analogue of the multinomial coefficient. This is the Gaussian polynomial (see [7]), obtainable from the multinomial coefficient

æ
ç
è
n
k1
k2
... 
km
ö
÷
ø
by replacing each occurrence of r! by
(qr-1)(qr-1-1)...(q-1)
(q-1)r
of course, 0!q is just 1. The Gaussian polynomial
æ
ç
è
k1
k2
... 
km
ö
÷
ø

 

q

may be regarded as the coefficient of a1k1a2k2...amkm in the expansion of (a1+a2+...+am)n in the algebra over R generated by (a1,a2,...,am; q) subject to ajai=qaiaj, i<j, qai=aiq. Notice that, in this generalization of the material of Section 1, it is not necessary that the functions f1, f2,...,fm be the same; however, if F in (3.3) is (as in the special case of the multinomial coefficients and in the example of the Gaussian polynomials) invariant under the action of the symmetric group Sm, then the functions f1, f2,...,fm may be chosen to be the same, given that F is separable.

The material of Section 2 makes it obvious how we would extend the definition of F, given by (3.3) to the domain of arbitrary integers n, k1, k2,...,km. The formula (2.5) is easily generalized by replacing the multinomial coefficient by F; indeed, the generalization does not even require that F be separable. However, one has to be careful in assigning a value to F in the regions in which the multinomial coefficient takes the value 0; this problem was first encountered in extending the harmonic triangle in [4]. We do not want to put any stress on this technical point here, since it is in the regions where formula (2.5) holds that the real interest lies.

Finally, we may obviously generalize Theorem 3.1, provided that we insist in (3.3) that F be invariant under the action of Sm. We leave the details to the reader.


NEXT