Falling Factorials, Generating Functions, and Conjoint Ranking Tables

Brad Osgood and William Wu Department of Electrical Engineering Stanford University Stanford, CA 94305 USA

                      osgood@stanford.edu
                     willywu@stanford.edu

Abstract We investigate the coefficients generated by expressing the falling factorial (xy)\underline{k} as a linear combination of falling factorial products x\underline{l}y\underline{m} for l, m = 1, …, k. Algebraic and combinatoric properties are discussed, some in relation to Stirling numbers.

1 Introduction

Let x\underline{k} denote the falling factorial power,

x\underline{k} = x(x − 1) … (x − k + 1) , k ∈ ℕ, k ≥ 1 .

We think of x ∈ ℝ, but the definition can make sense in more general settings. Problems from discrete Fourier analysis – distant from the topics considered here – led us to falling factorial powers of products expressed as

(xy)\underline{k} = ∑_{l,m=1}^{k} c_{l,m}^{(k)}x\underline{l}y\underline{m} .  (1)

There is the obvious symmetry c_{l,m}^{(k)} = c_{m,l}^{(k)}. Since c_{1,1}^{(1)} = 1 the interest begins when k ≥ 2. For example,

\begin{aligned}(xy)\underline{2} & = x\underline{1}y\underline{2} + x\underline{2}y\underline{1} + x\underline{2}y\underline{2} , \\ (xy)\underline{3} & = x\underline{1}y\underline{3} + x\underline{3}y\underline{1} + 6x\underline{2}y\underline{2} + 3x\underline{2}y\underline{3} + 3x\underline{3}y\underline{2} + x\underline{3}y\underline{3} . \end{aligned}

Note that

\begin{matrix}c_{1,1}^{(2)} = 0 \\ c_{1,1}^{(3)} = 0 , c_{1,2}^{(3)} = c_{2,1}^{(3)} = 0 . \end{matrix}

and that the coefficients that do appear are positive.

Here are the values for c_{l,m}^{(9)} displayed as a symmetric matrix:

(\begin{matrix}0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 15120 & 40320 & 24192 & 4608 & 255 \\ 0 & 0 & 10080 & 544320 & 1958040 & 1796760 & 588168 & 74124 & 3025 \\ 0 & 0 & 544320 & 6108480 & 12267360 & 7988904 & 2066232 & 218484 & 7770 \\ 0 & 15120 & 1958040 & 12267360 & 18329850 & 9874746 & 2229402 & 212436 & 6951 \\ 0 & 40320 & 1796760 & 7988904 & 9874746 & 4690350 & 965790 & 85680 & 2646 \\ 0 & 24192 & 588168 & 2066232 & 2229402 & 965790 & 185766 & 15624 & 462 \\ 0 & 4608 & 74124 & 218484 & 212436 & 85680 & 15624 & 1260 & 36 \\ 1 & 255 & 3025 & 7770 & 6951 & 2646 & 462 & 36 & 1 \end{matrix}) . (2)

The numbers c_{l,m}^{(k)} have a number of interesting properties that are the subject of the present paper. We found a recurrence relation, several closed-form expressions (which appear rather different from each other), a natural combinatorial interpretation in terms of conjoint ranking tables, and we can extend these results to products of more than two variables.

The combinatorics presented here have been considered before in other contexts. To make the present approach self-contained and more readable we have rederived (briefly) some of these earlier results, with references. We also mention several questions that we were unable to answer.

2 Stirling Numbers and Falling Factorial Powers

One can solve for the coefficients c_{l,m}^{(k)} in any particular case, but that there should generally be such an expansion emerges from the connection between falling factorial powers, ordinary powers, and Stirling numbers; see Knuth [4], whose notation we follow.

In combinatorics one defines the (unsigned) Stirling numbers of the first kind by

[\begin{matrix}k \\ l \end{matrix}] = the number of permutations of k letters which consist of l disjoint cycles.

In particular

[\begin{matrix}k \\ k \end{matrix}] = 1 , [\begin{matrix}k \\ l \end{matrix}] = 0 if k < l.  (3)

For us, the important fact is

x\underline{k} = ∑_{l=1}^{n}(−1)^{k−l} [\begin{matrix}k \\ l \end{matrix}] x^{l} .  (4)

Stirling numbers of the second kind, denoted by \begin{cases}k \\ l \end{cases}\}, are defined by

\begin{cases}k \\ l \end{cases}\} = the number of partitions of a set of k elements into l nonempty subsets.

Here

\begin{cases}k \\ 1 \end{cases}\} = \begin{cases}k \\ k \end{cases}\} = 1 , \begin{cases}k \\ l \end{cases}\} = 0 if k < l.  (5)

The special values in (3) and (5) will come up in adjusting summation indices. Corresponding to (4) one has

x^{k} = ∑_{l=1}^{n} \begin{cases}k \\ l \end{cases}\} x\underline{l} .  (6)

We included the phrase ‘Generating Functions’ in the title of the paper because the sequences

[\begin{matrix}k \\ l \end{matrix}], \begin{cases}k \\ l \end{cases}\}, and c_{l,m}^{(k)} each count something and each appears in an expansion in powers, (4),

(6), and (1), much like classical generating functions.

Proceeding with the derivation of (1), from (4) and (6) we have

(xy)\underline{k} = ∑_{p=1}^{k}(−1)^{k−p} [\begin{matrix}k \\ p \end{matrix}] (xy)^{p} = ∑_{p=1}^{k}(−1)^{k−p} [\begin{matrix}k \\ p \end{matrix}] x^{p}y^{p}

= ∑_{p=1}^{k}(−1)^{k−p} [\begin{matrix}k \\ p \end{matrix}] (∑_{l=1}^{p} \begin{cases}p \\ l \end{cases}\} x\underline{l}) (∑_{m=1}^{p} \begin{cases}p \\ m \end{cases}\} y\underline{m})

= ∑_{p=1}^{k} ∑_{l=1}^{p} ∑_{m=1}^{p}(−1)^{k−p} [\begin{matrix}k \\ p \end{matrix}] \begin{cases}p \\ l \end{cases}\} \begin{cases}p \\ m \end{cases}\} x\underline{l}y\underline{m}

= ∑_{l=1}^{k} ∑_{m=1}^{k} ∑_{p=1}^{k}(−1)^{k−p} [\begin{matrix}k \\ p \end{matrix}] \begin{cases}p \\ l \end{cases}\} \begin{cases}p \\ m \end{cases}\} x\underline{l}y\underline{m}

= ∑_{l,m=1}^{k} c_{l,m}^{(k)}x\underline{l}y\underline{m} ,

where the second-to-last equality holds since by convention \begin{cases}a \\ b \end{cases}\} = 0 when a < b, and

c_{l,m}^{(k)} = ∑_{p=1}^{k}(−1)^{k−p} [\begin{matrix}k \\ p \end{matrix}] \begin{cases}p \\ l \end{cases}\} \begin{cases}p \\ m \end{cases}\} .  (7)

This establishes the expansion (1) and provides a formula for the coefficients. It is not clear from this expression that the c’s are nonnegative. We will deduce this from a combinatorial characterization in Section 4.

When l = k,

c_{k,m}^{(k)} = ∑_{p=1}^{k}(−1)^{k−p} [\begin{matrix}k \\ p \end{matrix}] \begin{cases}p \\ k \end{cases}\} \begin{cases}p \\ m \end{cases}\}

= [\begin{matrix}k \\ k \end{matrix}] \begin{cases}k \\ k \end{cases}\} \begin{cases}k \\ m \end{cases}\}
= \begin{cases}k \\ m \end{cases}\} .

Thus the Stirling numbers of the second kind appear in the last row (or column) of the matrix of the c’s, as we see in (2).

There are a few more arithmetic properties of the c_{l,m}^{(k)} that we wish to note, expressed most easily in terms of the symmetric matrix C^{(k)} whose (l, m)-entry is c_{l,m}^{(k)}. Let Σ^{(k)} be the k × k diagonal matrix whose entries are

Σ_{lm}^{(k)} = (−1)^{k−l} [\begin{matrix}k \\ l \end{matrix}] δ_{lm} .

Let S_{2}^{(k)} be the upper triangular matrix with nonzero entries

(S_{2}^{(k)})_{lm} = \begin{cases}m \\ l \end{cases}\} , l ≤ m .

One can check that

C^{(k)} = S_{2}^{(k)}Σ^{(k)}(S_{2}^{(k)})^{T} .

In turn it follows that C^{(k)} is invertible and has the same signature as Σ^{(k)}. Since the diagonal entries in Σ^{(k)} alternate sign, C^{(k)} has ⌈k/2⌉ positive eigenvalues and k − ⌈k/2⌉ negative eigenvalues. Moreover, the diagonal entries of S_{2}^{(k)} are 1’s so det S_{2}^{(k)} = 1, and then

det C^{(k)} = ∏_{l=1}^{k}(−1)^{k−l} [\begin{matrix}k \\ l \end{matrix}] .

For all k, it appears that the rows (columns), the diagonals, and the anti-diagonals of C^{(k)} are all unimodal; this is quite visible for k = 9 in (2). Stronger than unimodality, numerical evidence suggests that the rows, diagonals, and anti-diagonals are log-concave. In fact, numerical evidence suggests that the associated polynomials for these sequences have negative real roots, satisfying Newton’s sufficient test for log-concavity [7].

3 Recurrence Relation

Falling factorial powers satisfy

Δx\underline{n} = nx\underline{n−1} ,

where Δ is the forward difference operator. A little more generally, using the two-variable analog Δf(x, y) = f(x + 1, y + 1) − f(x, y), one can verify that

\begin{aligned}Δ(x\underline{l}y\underline{m}) & = (Δx\underline{l})y\underline{m} + x\underline{l}(Δy\underline{m}) + (Δx\underline{l})(Δy\underline{m}) \\ & = lx\underline{l−1}y\underline{m} + mx\underline{l}y\underline{m−1} + lmx\underline{l−1}y\underline{m−1} . \end{aligned}

Then, on the one hand,

\begin{aligned}Δ(xy)\underline{k} & = ∑_{l,m=1}^{k} c_{l,m}^{(k)}(lx\underline{l−1}y\underline{m} + mx\underline{l}y\underline{m−1} + lmx\underline{l−1}y\underline{m−1}) \\ & = ∑_{l=0}^{k−1} ∑_{m=1}^{k} c_{l+1,m}^{(k)}(l + 1)x\underline{l}y\underline{m} + ∑_{l=1}^{k} ∑_{m=0}^{k−1} c_{l,m+1}^{(k)}(m + 1)x\underline{l}y\underline{m} + ∑_{l,m=0}^{k−1} c_{l+1,m+1}^{(k)}(l + 1)(m + 1)x\underline{l}y\underline{m} . \end{aligned}

On the other hand, apply the identity

v\underline{k} = \frac{1}{v}(v\underline{k+1} + kv\underline{k})

with v = (x + 1)(y + 1) to write

\begin{aligned}Δ(xy)\underline{k} & = ((x + 1)(y + 1))\underline{k} − (xy)\underline{k} \\ & = \frac{1}{(x + 1)(y + 1)} (((x + 1)(y + 1))\underline{k+1} + k((x + 1)(y + 1))\underline{k}) − (xy)\underline{k} , \end{aligned}

and then

Δ(xy)\underline{k} = ∑_{l,m=1}^{k+1} c_{l,m}^{(k+1)} \frac{(x + 1)\underline{l}}{x + 1} \frac{(y + 1)\underline{m}}{y + 1} + k ∑_{l,m=1}^{k} c_{l,m}^{(k)} \frac{(x + 1)\underline{l}}{x + 1} \frac{(y + 1)\underline{m}}{y + 1} − ∑_{l,m=1}^{k} c_{l,m}^{(k)}x\underline{l}y\underline{m}

= ∑_{l,m=1}^{k+1} c_{l,m}^{(k+1)}x\underline{l−1}y\underline{m−1} + k ∑_{l,m=1}^{k} c_{l,m}^{(k)}x\underline{l−1}y\underline{m−1} − ∑_{l,m=1}^{k} c_{l,m}^{(k)}x\underline{l}y\underline{m}

= ∑_{l,m=0}^{k} c_{l+1,m+1}^{(k+1)}x\underline{l}y\underline{m} + k ∑_{l,m=0}^{k−1} c_{l+1,m+1}^{(k)}x\underline{l}y\underline{m} − ∑_{l,m=1}^{k} c_{l,m}^{(k)}x\underline{l}y\underline{m} .

Comparing the two expressions for Δ(xy)\underline{k}, and rearranging terms, we have shown the following: Theorem 1. The coefficients c_{l,m}^{(k)} satisfy the recurrence

c_{l+1,m+1}^{(k+1)} = c_{l,m}^{(k)} + (l + 1)c_{l+1,m}^{(k)} + (m + 1)c_{l,m+1}^{(k)} + ((l + 1)(m + 1) − k)c_{l+1,m+1}^{(k)} .

We remark that while this recurrence generally has four terms, exceptions occur at the edges of the matrix. Careful bookkeeping shows that in the last row when l = k, the recurrence reduces to the two term recurrence

c_{k+1,m+1}^{(k+1)} = c_{k,m}^{(k)} + (m + 1)c_{k,m+1}^{(k)}

which is precisely the recurrence relation describing Stirling numbers of the second kind. The c_{l,m}^{(k)} coefficients can thus be viewed as a generalization of Stirling numbers.

Lastly, we comment that other proofs of the recurrence are possible, for example one that uses the recurrence relations for Stirling numbers.

4 Combinatorial Characterizations

Conjoint analysis is a method in marketing that assigns weightings to independent attributes of a product. It is only the first step that we consider, that of setting up a conjoint ranking table. Suppose there are l ≥ 1 choices for one attribute (e.g., price) and m ≥ 1 for the other (e.g., color). Form an l ×m table, in which each cell represents the two attributes considered jointly; hence the contraction ‘conjoint.’ Let k ≤ lm and rank the conjoint preferences from 1 to k. Since we allow k ≤ lm not every pair of attributes need have a ranking, but we do insist that every individual attribute must enter into the ranking at least once. That is, every row or column must have at least one ranked cell. In particular k ≥ max{l, m}. One can consider the remaining cells as left blank or filled in with zeros.

For a given l and m we refer to such an object as a k-conjoint ranking table. This is quite a general concept and it is easy to imagine many examples. Here is one other. A graduate student is signing up to take qualifying exams, and is required to fill out an l × m table indicating preferences. Each of the l rows refers to a subject area, such as algebra, combinatorics, analysis, etc.. Each of the m columns refers to a particular professor; we assume that they are all equally capable of asking about any of subjects. The student will be asked k questions, where k ≤ lm, and may put the numbers 1 through k in any of the cells, indicating preferences for who asks what kinds of questions. However, the student is not allowed to avoid any professors, and must put at least one number in each column. Similarly, the student is not allowed to avoid any subject areas, and must put at least one number in each row.

For more background on how conjoint analysis is used in marketing, see Green [3].

Theorem 2. The number of k-conjoint ranking tables of size l × m is l! m! c_{l,m}^{(k)}.

Proof of Theorem 2. Let d_{l,m}^{(k)} be the number of l × m conjoint tables containing k ones.

By definition of c_{l,m}^{(k)}, it suffices to show that (xy)\underline{k} = ∑_{l,m=1}^{k} d_{l,m}^{(k)}(x\underline{l}/l!)(y\underline{m}/m!). It also suffices to prove this for x and y restricted to the positive integers, since polynomials coinciding on the positive integers are identical.

The number of ways to place the numbers 1, 2, …, k into distinct cells of a x×y rectangle is clearly (xy)\underline{k}. However, this placement can be done in the following way: choose l rows (in x\underline{l}/l! ways), choose m columns (in y\underline{m}/m! ways), and then place the numbers in the chosen rows and columns so that every row or column is used (in d_{l,m}^{(k)} ways). Summing over l and m gives the result.

Theorem 2 has the following immediate corollary:

Corollary 3. The c_{lm}^{(k)} satisfy

c_{l,m}^{(k)} = 0 for lm < k and c_{l,m}^{(k)} > 0 for lm ≥ k .

Proof. When lm < k, the conjoint ranking table is too small to fit all k numbers, so c_{l,m}^{(k)} = 0. However, when lm ≥ k, there are enough cells in the table to be ranked from 1 to k.

Furthermore, there must exist at least one way of placing the numbers that satisfies the row and column constraints since the conditions 1 ≤ l, m ≤ k imply that k ≥ max(l, m). Thus c_{l,m}^{(k)} > 0.

One can see the pattern of zeros for k = 9 in (2). The hyperbolic shape of the boundary between the zero and nonzero coefficients becomes more pronounced as k increases.

Here we make contact with earlier work, for the core of the proof above is counting a set of binary matrices, and these have been counted in other ways; see Chapter 9 in [2]. One approach is to use the inclusion-exclusion principle. We would like to give this argument to show how it leads to another expression for c_{l,m}^{(k)} (which also appears in older literature, but not as interpreted here).

Fix l and m, take k ≤ lm, and let O be the set of binary matrices of size l × m with 1’s in exactly k positions. Then

|O| = \binom{lm}{k} .

Now let k ≥ max{l, m} and let C be the subset of O which have at least one 1 in every row and in every column. We want to find |C|.

For the index i running from 1 to l let A_{i} be the subset of O whose i’th row has all 0’s, and for the index i running from 1 to m let A_{i+l} be the subset of O whose i’th column has all 0’s. Then

C = \overline{A_{1}} ∩ \overline{A_{2}} ∩ ⋯ ∩ \overline{A_{l+m}} ,

where

\overline{A_{i}} = O \ A_{i} .

By the inclusion-exclusion principle

|C| = |O|−∑_{i=1}^{l+m} |A_{i}|+ ∑_{i_{1}<i_{2}} |A_{i_{1}}∩A_{i_{2}}|− ∑_{i_{1}<i_{2}<i_{3}} |A_{i_{1}}∩A_{i_{2}}∩A_{i_{3}}|+⋯+(−1)^{l+m}|A_{1}∩A_{2}∩⋯∩A_{l+m}| .

To compute the general sum

∑ |A_{i_{1}} ∩ ⋯ ∩ A_{i_{h}}|

we have to have to distinguish the matrices that have zeroed rows from those that have zeroed columns. Suppose among the h sets A_{i_{1}}, …, A_{i_{h}} that p of them have zeroed rows. Then h − p have zeroed columns. For a fixed p there are \binom{l}{p} ways to select p rows to zero out and there are \binom{m}{h−p} ways to select h − p columns to zero out. After these choices, there are (l − p)(m − h + p) cells remaining amongst which we can place k ones. Thus

∑ |A_{i_{1}} ∩ ⋯ ∩ A_{i_{h}}| = ∑_{p=0}^{h} \binom{l}{p}\binom{m}{h − p}\binom{(l − p)(m − h + p)}{k}

and

|C| = ∑_{h=0}^{l+m} ∑_{p=0}^{h}(−1)^{h}\binom{l}{p}\binom{m}{h − p}\binom{(l − p)(m − h + p)}{k} .

Multiplying |C| by k! distinguishes the nonzero elements, whether they are k distinguished balls tossed into bins or the numbers from 1 to k. The end result is evidently the same as counting the number of k-conjoint ranking tables, and hence

c_{l,m}^{(k)} = \frac{1}{l!m!} · k!|C| = \frac{k!}{l!m!} ∑_{h=0}^{l+m} ∑_{p=0}^{h}(−1)^{h}\binom{l}{p}\binom{m}{h − p}\binom{(l − p)(m − h + p)}{k} .  (8)

There is one more approach and one more formula. The equation (1) can also be written in the form

\binom{xy}{k} = ∑_{l,m=1}^{k} b_{l,m}^{(k)}\binom{x}{l}\binom{y}{m} ,  (9)

where

b_{l,m}^{(k)} = \frac{l!m!}{k!}c_{l,m}^{(k)} .

We understand the binomial coefficient to be defined for nonintegral x by

\binom{x}{k} = \frac{Γ(x + 1)}{k!Γ(x − k + 1)} ,

and we use

x(x − 1) … (x − k + 1) = \frac{Γ(x + 1)}{Γ(x − k + 1)} .

We see that the b_{l,m}^{(k)} give a count of the number of the l × m binary matrices with exactly k ones such that each row and column has at least one 1. We have a further comment on the combinatorics of (9) when x and y are integers. The left-hand side, \binom{xy}{k} is just the number of ways to select k elements from an x × y array. How does this jibe with the right-hand side?

For any given selection of k cells there is a unique minimal subarray (smallest number of rows and columns) such that every row and column of that subarray contains a selected cell. This is illustrated in Figure 1. On the left, the darkened cells correspond to a selection of k = 8 cells, and the arrows indicate the rows and columns of the subarray in which the selected cells are contained. On the right we see the subarray extracted, and note that every row and column contains a selected square. Counting all possible such subarrays thus counts the ways of choosing k elements from the big array. This is what the right-hand side in equation (9) does, for \binom{x}{l}\binom{y}{m} is the number of ways to choose an l × m subarray, and then for each such subarray we count the number of ways to populate it with k entries such that no row or column is void. That multiplier is precisely b_{l,m}^{(k)}.

From Theorem 1, the b’s satisfy the recurrence

b_{l+1,m+1}^{(k+1)} = (l + 1)(m + 1)(b_{l,m}^{(k)} + b_{l,m+1}^{(k)} + b_{l+1,m}^{(k)}) + ((l + 1)(m + 1) − k)b_{l+1,m+1}^{(k)} . (10)

But it was noted explicitly by Cameron [1] that Möbius inversion applied to (9) implies

b_{l,m}^{(k)} = ∑_{s,t=1}^{k}(−1)^{l+s+m+t}\binom{l}{s}\binom{m}{t}\binom{st}{k} .  (11)

Figure 1: Combinatorial Interpretation of equation (9).

Furthermore, Maia and Mendez [5] found a similar formula using combinatorial species. Möbius inversion is kin to matrix inversion and it is interesting to see how the latter can be used to derive (11).

For k^{2} pairs (x_{i}, y_{i}), i = 1, …, k^{2}, we treat (9) as a system of linear equations for the k^{2} unknowns b_{l,m}^{(k)}. In matrix form, A\underline{β} = \underline{ξ} where

\begin{matrix}\underbrace{[ \begin{matrix}\binom{x_{1}}{1}\binom{y_{1}}{1} & \binom{x_{1}}{1}\binom{y_{1}}{2} & ⋯ & \binom{x_{1}}{1}\binom{y_{1}}{k} & \binom{x_{1}}{2}\binom{y_{1}}{1} & \binom{x_{1}}{2}\binom{y_{1}}{2} & ⋯ & \binom{x_{1}}{k}\binom{y_{1}}{k} \\ \binom{x_{2}}{1}\binom{y_{2}}{1} & \binom{x_{2}}{1}\binom{y_{2}}{2} & ⋯ & \binom{x_{2}}{1}\binom{y_{2}}{k} & \binom{x_{2}}{2}\binom{y_{2}}{1} & \binom{x_{2}}{2}\binom{y_{2}}{2} & ⋯ & \binom{x_{2}}{k}\binom{y_{2}}{k} \\ ⋮ & ⋮ & ⋯ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ \binom{x_{k^{2}}}{1}\binom{y_{k^{2}}}{1} & \binom{x_{k^{2}}}{1}\binom{y_{k^{2}}}{2} & ⋯ & \binom{x_{k^{2}}}{1}\binom{y_{k^{2}}}{k} & \binom{x_{k^{2}}}{2}\binom{y_{k^{2}}}{1} & \binom{x_{k^{2}}}{2}\binom{y_{k^{2}}}{2} & ⋯ & \binom{x_{k^{2}}}{k}\binom{y_{k^{2}}}{k} \end{matrix} ]}_{A} & \underbrace{[ b_{1,1}^{(k)} ; b_{1,2}^{(k)} ; ⋮ ; b_{1,k}^{(k)} ; b_{2,1}^{(k)} ; b_{2,2}^{(k)} ; ⋮ ; b_{k,k}^{(k)} ]}_{\underline{β}} \\ = \underbrace{[ \binom{x_{1}y_{1}}{k} ; \binom{x_{2}y_{2}}{k} ; ⋮ ; \binom{x_{i}y_{i}}{k} ; ⋮ ; \binom{x_{k^{2}}y_{k^{2}}}{k} ]}_{\underline{ξ}} . \end{matrix}

Thus if the sequences (x_{i}) and (y_{i}) are chosen such that A is invertible, we will have an expression for the coefficients in \underline{β}. The matrix inversion can be done quite simply because one can choose sequences that make A the Kronecker product of the Pascal matrix with itself. Recall that the lower-triangular Pascal matrix P is defined by

P_{ij} = \binom{i}{j} , 1 ≤ i, j ≤ k .

The Kronecker square of P is the k^{2} × k^{2} matrix with entries

(P ⊗ P)_{ij} = P⌈_{\frac{i}{k}}⌉⌈_{\frac{j}{k}}⌉ · P_{(i−1)_{k}+1,(j−1)_{k}+1} ,

where i_{k} denotes i mod k. It is easily confirmed that P ⊗ P equals the matrix A when x_{i} = ⌈\frac{i}{k}⌉ and y_{i} = (i − 1)_{k} + 1. Since the inverse of a Kronecker product is the Kronecker product of the inverses,

A^{−1} = (P ⊗ P)^{−1} = P^{−1} ⊗ P^{−1} .

Applying the Pascal matrix inverse formula P_{ij}^{−1} = (−1)^{i+j}\binom{i}{j},

(P ⊗ P)_{ij}^{−1} = (−1)^{⌈^{\frac{i}{k}}⌉+⌈\frac{j}{k}⌉+(i−1)_{k}+1+(j−1)_{k}+1}(\begin{matrix}⌈ & \frac{i}{k} & ⌉ \\ ⌈ & \frac{j}{k} & ⌉ \end{matrix})\binom{(i − 1)_{k} + 1}{(j − 1)_{k} + 1} .

From the formula for A^{−1} let us derive (11). We have

\underline{β} = A^{−1}\underline{ξ} , b_{l,m}^{(k)} = β_{i} , where i = k(l − 1) + m,

or

\begin{aligned}b_{l,m}^{(k)} = β_{i} & = ∑_{j=1}^{k^{2}} A_{i,j}^{−1}ξ_{j} = ∑_{j=1}^{k^{2}} A_{i,j}^{−1}\binom{⌈\frac{j}{k}⌉ ((j − 1)_{k} + 1)}{k} \\ & = ∑_{j=1}^{k^{2}}(−1)^{⌈^{\frac{i}{k}}⌉+⌈\frac{j}{k}⌉+(i−1)_{k}+1+(j−1)_{k}+1}(\begin{matrix}⌈ & \frac{i}{k} & ⌉ \\ ⌈ & \frac{j}{k} & ⌉ \end{matrix})\binom{(i − 1)_{k} + 1}{(j − 1)_{k} + 1}\binom{⌈\frac{j}{k}⌉ ((j − 1)_{k} + 1)}{k} . \end{aligned}

Both i and j run from 1 to k^{2}. From the equation i = k(l−1)+m, it follows that ⌈\frac{i}{k}⌉ = l and (i−1)_{k}+1 = m. Similarly, writing j = ks+t where s ∈ {0, 1, …, k−1} and t ∈ {1, 2, …, k}, it follows that ⌈\frac{j}{k}⌉ = s + 1 and (j − 1)_{k} + 1 = t. Thus,

\begin{aligned}b_{l,m}^{(k)} & = ∑_{s=0}^{k−1} ∑_{t=1}^{k}(−1)^{l+s+1+m+t}\binom{l}{s + 1}\binom{m}{t}\binom{(s + 1)t}{k} \\ & = ∑_{s=1}^{k} ∑_{t=1}^{k}(−1)^{l+s+m+t}\binom{l}{s}\binom{m}{t}\binom{st}{k} , \end{aligned}

which is (11).

We conclude this part of the discussion by noting that we have three different expressions for the c’s (or the b’s), (7), (8) and (11) – and we do not know algebraically how to derive one from another!

5 More Than Two Variables

For an expansion

(x_{1}x_{2} ⋯ x_{n})\underline{k} = ∑_{L} c_{L}^{(k)}x_{1}\underline{l_{1}}x_{2}\underline{l_{2}} ⋯ x_{n}\underline{l_{n}} , L = (l_{1}, l_{2}, …, l_{n}) , 1 ≤ l_{i} ≤ k ,

of a product of more than two variables all the results in the preceding sections have natural extensions. Modifications to the earlier arguments are straightforward and so we record the outcomes with little additional detail – the chief problem is notation. We follow the generally accepted conventions on multi-indexing. In particular

L! = l_{1}!l_{2}! ⋯ l_{n}! .

The formula for the c’s in terms of Stirling numbers is

c_{L}^{(k)} = ∑_{p=1}^{k}(−1)^{k−p} [\begin{matrix}k \\ p \end{matrix}] ∏_{i=1}^{n} \begin{cases}p \\ l_{i} \end{cases}\} .

or simply

c_{L}^{(k)} = ∑_{p=1}^{k}(−1)^{k−p} [\begin{matrix}k \\ p \end{matrix}] \begin{cases}p \\ L \end{cases}\} .

if we allow ourselves the analog to the the multi-indexed case of binomial coefficients and write

\begin{cases}p \\ L \end{cases}\} = ∏_{i=1}^{n} \begin{cases}p \\ l_{i} \end{cases}\} .

There is a natural extension of the product rule for the forward difference operator and it can be applied just as before to obtain a recurrence relation. It will pay to invest in a little extra notation. We write

L + 1 = (l_{i} + 1: i = 1, …, n)

and for a subset S ⊆ {1, …, n} we write

L_{S} = (l_{i}: i ∈ S) , L_{S} + 1 = (l_{i} + 1: i ∈ S) , L\overline{S} = (l_{i}: i ∈ \{1, …, n\} \ S) .

The result is

c_{L+1}^{(k+1)} = c_{L}^{(k)} − kc_{L+1}^{(k)} + ∑_{m=1}^{n} ∑_{|S|=m} (∏_{i∈S} l_{i}) c_{L_{S}+1,L\overline{S}}^{(k)} .

The generalization of a 2-dimensional conjoint ranking table allows for n independent attributes (color, price, shape, …) with l_{i} choices for the i’th attribute. Based on the recurrence one can then show that L!c_{L}^{(k)} is the number of ways to fill in an l_{1} × l_{2} × ⋯ × l_{n} conjoint ranking table with the numbers 1 through k, insisting, as before, that each attribute must enter into the ranking at least once. Again this implies the nonnegativity of the c’s, more precisely

c_{L}^{(k)} = 0 if ∏_{i} l_{i} < k and c_{L}^{(k)} > 0 if ∏_{i} l_{i} ≥ k.

Extensions of the alternate formulas (8) and (11) are more complicated to write. For the former, to keep the final result from being too cluttered we use the notation

∥L∥ = ∑_{l_{i}∈L} l_{i}

and for a multi-index M = (m_{1}, m_{2}, …, m_{n}) with 1 ≤ m_{i} ≤ h and ∥M∥ = h we let

Φ(L, M) = ∏_{i=1}^{n}(l_{i} − m_{i}).

Then

c_{L}^{(k)} = \frac{k!}{L!} ∑_{h=0}^{∥L∥}(−1)^{h} ∑_{M,∥M∥=h} \binom{Φ(L, M)}{k} ∏_{i=1}^{n} \binom{l_{i}}{m_{i}} .

While the derivation of this formula is only an extension of the argument for two variables, some discussion will help make the form clearer.

Let “slices” refer to the objects of dimension n − 1 in a multidimensional table which are given by fixing the entry in one coordinate position. (One could say this is the higherdimensional generalization of rows and columns for matrices.) As before, we use inclusionexclusion to count b_{L}^{(k)}, the number of distinct l_{1}×…×l_{n} (0, 1)-tables with exactly k ones and no zeroed slices; that is the formula without the factorials in front. In the outer summation, the index h is the number of zeroed slices. The inner summation then runs over possible ways to distribute the h zeroed slices across the n different dimensions.

The number of zeroed slices in dimension i is m_{i}, and \binom{l_{i}}{m_{i}} is the number of ways to select a particular set of m_{i} slices to zero out.

After removing the zeroed slices, the number of remaining cells is given by Φ(L, M), and \binom{Φ(L,M)}{k} is the number of ways to distribute k ones amongst these remaining cells.

Lastly, the analog of formula (11) based on Kronecker products and matrix inversion is

c_{L}^{(k)} = \frac{k!}{L!} ∑_{r_{1},r_{2},...,r_{n}=1}^{k}(−1)^{∑_{i}(r_{i}+l_{i})}\binom{∏_{i} r_{i}}{k} ∏_{i} \binom{l_{i}}{r_{i}} .

6 Acknowledgements

We would like to thank Jiehua Chen, John T. Gill III, Michael Godfrey, and Donald Knuth for their interest and suggestions, and particularly the referee for a very meticulous report and many insightful comments.

This research was supported by a scholarship from the Frank H. and Eva Buck Foundation.

References

[1] P. J. Cameron, T. Prellberg, and D. Stark, Asymptotics for incidence matrix classes, Electron. J. Combin. 13 (2006), #R85.

[2] Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC Press, 2002.

[3] P. E. Green and V. Srinivasan, Conjoint analysis in consumer research: issues and outlook, J. Consumer Research 5 (1978), 103–123.

[4] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics, Addison Wesley, second edition, 1994, pp. 257–267.

[5] M. Maia and M. Mendez, On the arithmetic product of combinatorial species, Discrete Math. 308 (2008), 5407–5427.

[6] R. P. Stanley, Log-Concave and Unimodal Sequences in Algebra, Combinatorics, and Geometry, Ann. New York Acad. Sci. 576 (1989), 500–535.

[7] H. S. Wilf, Generatingfunctionology, AK Peters Ltd., 2006, pp. 136–139.

2000 Mathematics Subject Classification: Primary 05A10, 11B65, 05A15; Secondary 05A19, 11B73. Keywords: Binomial coefficients, Stirling numbers, conjoint ranking tables, recurrence relations, generating functions.

(Concerned with sequences \underline{A007318}, \underline{A008275}, \underline{A008277}, and \underline{A068424}. )

Received August 31 2009; revised version received November 6 2009. Published in Journal of Integer Sequences, November 16 2009.

Return to Journal of Integer Sequences home page.