\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}
\newcommand{\ff}[2]{ \ensuremath{ {#1}^{\underline{#2}} }}
\newcommand{\stone}[2]{\ensuremath{\left[\begin{matrix}{#1}\\{#2}\end{matrix}\right]}}
\newcommand{\sttwo}[2]{\ensuremath{\left\{\begin{matrix}{#1}\\{#2}\end{matrix}\right\}}}
\begin{center}
\vskip 1cm{\LARGE\bf
Falling Factorials, Generating Functions, and \\
\vskip .1in Conjoint Ranking Tables
}
\vskip 1cm
\large
Brad Osgood and William Wu \\
Department of Electrical Engineering \\
Stanford University \\
Stanford, CA 94305 \\
USA \\
\href{mailto:osgood@stanford.edu}{\tt osgood@stanford.edu}\\
\href{mailto:willywu@stanford.edu}{\tt willywu@stanford.edu} \\
\end{center}
\vskip .2in
\begin{abstract}
We investigate the coefficients generated by expressing the falling
factorial $\ff{(xy)}{k}$ as a linear combination of falling factorial
products $\ff{x}{l}\ff{y}{m}$ for $l,m =1, \dots, k$. Algebraic and
combinatoric properties are discussed, some in relation to Stirling
numbers.
\end{abstract}
\section{Introduction}
Let $\ff{x}{k}$ denote the \emph{falling factorial power},
\[
\ff{x}{k}=x(x-1)\ldots(x-k+1)\,,\quad k\in \mathbb{N}, k \ge 1\,.
\]
We think of $x \in \mathbb{R}$, 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
\begin{equation}
\label{eq:main}
\ff{(xy)}{k} = \sum_{l,m=1}^k c^{(k)}_{l,m} \ff{x}{l} \ff{y}{m}\,.
\end{equation}
There is the obvious symmetry $c^{(k)}_{l,m} = c^{(k)}_{m,l}$. Since $c^{(1)}_{1,1}=1$ the interest begins when $k \ge 2$.
For example,
\[
\begin{aligned}
\ff{(xy)}{2} &=\ff{x}{1}\ff{y}{2}+\ff{x}{2}\ff{y}{1}+\ff{x}{2}\ff{y}{2}\,,\\
\ff{(xy)}{3}&= \ff{x}{1}\ff{y}{3}+\ff{x}{3}\ff{y}{1}+6\ff{x}{2}\ff{y}{2}+3\ff{x}{2}\ff{y}{3}+3\ff{x}{3}\ff{y}{2}+\ff{x}{3}\ff{y}{3}\,.
\end{aligned}
\]
Note that
\[
\begin{aligned}
&c^{(2)}_{1,1}=0\\
&c^{(3)}_{1,1}=0\,,\quad c^{(3)}_{1,2}=c^{(3)}_{2,1}=0\,.
\end{aligned}
\]
and that the coefficients that do appear are positive.
Here are the values for $c^{(9)}_{l,m}$ displayed as a symmetric matrix:
\begin{equation} \label{eq:C9}
\begin{pmatrix}
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{pmatrix}\, .
\end{equation}
The numbers $c^{(k)}_{l,m}$
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.
\section{Stirling Numbers and Falling Factorial Powers} \label{section:stirling}
One can solve for the coefficients $c^{(k)}_{l,m}$ 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 \cite{knuth:concrete}, whose notation we follow.
In combinatorics one defines the (unsigned) Stirling numbers of the first kind by
\[
\stone{k}{l}
= \text{the number of permutations of $k$ letters which consist of $l$ disjoint cycles.}
\]
In particular
\begin{equation} \label{eq:stirling-1-special}
\stone{k}{k} = 1\,,\quad \stone{k}{l} = 0 \quad \text{if $k 0\quad \text{for} \quad l m \ge k\,.
\]
\end{corollary}
\begin{proof}
When $lm < k$, the conjoint ranking table is too small to fit all $k$ numbers, so $c^{(k)}_{l,m}=0$. However, when $lm \geq 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 \leq l,m \leq k$ imply that $k \geq \max(l,m)$. Thus $c^{(k)}_{l,m} >0$.
\end{proof}
One can see the pattern of zeros for $k=9$ in \eqref{eq:C9}. 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 \cite{charalambides:combinatorics}. 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^{(k)}_{l,m}$ (which also appears in older literature, but not as interpreted here).
Fix $l$ and $m$, take $k \le lm$, and let $\mathcal{O}$ be the set of binary matrices of size $l \times m$ with $1$'s in exactly $k$ positions. Then
\[
|\mathcal{O}| = \binom{lm}{k}\,.
\]
Now let $k \ge \max\{l,m\}$ and let $\mathcal{C}$ be the subset of $\mathcal{O}$ which have at least one $1$ in every row and in every column. We want to find $|\mathcal{C}|$.
For the index $i$ running from $1$ to $l$ let $\mathcal{A}_i$ be the subset of $\mathcal{O}$ whose $i$'th row has all $0$'s, and for the index $i$ running from $1$ to $m$ let $\mathcal{A}_{i+l}$ be the subset of $\mathcal{O}$ whose $i$'th column has all $0$'s. Then
\[
\mathcal{C} = \overline{\mathcal{A}_1}\cap\overline{\mathcal{A}_2}\cap\cdots \cap\overline{\mathcal{A}_{l+m}}\,,\]
where
\[
\overline{\mathcal{A}_i} = \mathcal{O}\setminus \mathcal{A}_i\,.
\]
By the inclusion-exclusion principle
\[
|\mathcal{C}| = |\mathcal{O}|-\sum_{i=1}^{l+m} |\mathcal{A}_i| + \sum_{i_10$ if $\prod_i l_i \ge k$.}
\]
Extensions of the alternate formulas \eqref{eq:formula-2} and \eqref{eq:formula-3} are more complicated to write. For the former, to keep the final result from being too cluttered we use the notation
\[
\|L\| = \sum_{l_i\in L} l_i
\]
and for a multi-index $M = (m_1,m_2, \dots, m_n)$ with $1 \le m_i \le h$ and $\|M\| = h$ we let
\[
\Phi(L,M) = \prod_{i=1}^n (l_i - m_i).
\]
Then
\[
c^{(k)}_L=\frac{k!}{ L!} \sum_{h=0}^{\|L\|} (-1)^h\sum_{M,\|M\|=h} \binom{\Phi(L,M)}{k}\prod_{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 higher-dimensional generalization of rows and columns for matrices.)
As before, we use inclusion-exclusion to count $b^{(k)}_L$, the number of distinct $l_1 \times \ldots \times 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 $\Phi(L,M)$, and $\binom{\Phi(L,M)}{k}$ is the number of ways to distribute $k$ ones amongst these remaining cells.
Lastly, the analog of formula \eqref{eq:formula-3} based on Kronecker products and matrix inversion is
\[
c^{(k)}_L=\frac{k!}{L!}\sum_{r_1,r_2,\dots,r_n=1}^k (-1)^{\sum_i(r_i+l_i)}\binom{\prod_ir_i}{k}\prod_i\binom{l_i}{r_i}\,.
\]
\section{Acknowledgements}
\label{sec:ack}
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.
\begin{thebibliography}{99}
\bibitem{cameron:asymptotics}{
P. J. Cameron, T. Prellberg, and D. Stark, Asymptotics for
incidence matrix classes, {\it Electron. J. Combin.} {\bf 13} (2006), \#R85.
}
\bibitem{charalambides:combinatorics}{
Ch. A. Charalambides, {\it Enumerative Combinatorics}, Chapman \& Hall/CRC
Press, 2002.
}
\bibitem{green}{
P. E. Green and V. Srinivasan, Conjoint analysis in consumer research: issues and outlook, {\it J. Consumer Research} {\bf 5} (1978), 103--123.
}
\bibitem{knuth:concrete}{
R. L. Graham, D. E. Knuth, and O. Patashnik, {\it Concrete Mathematics},
Addison Wesley, second edition, 1994, pp. 257--267.
}
\bibitem{maia-mendez:species}{
M. Maia and M. Mendez, On the arithmetic product of combinatorial
species, {\it Discrete Math.} {\bf 308} (2008), 5407--5427.
}
\bibitem{stanley1989lca}{
R. P. Stanley, Log-Concave and Unimodal Sequences in Algebra,
Combinatorics, and Geometry, {\it Ann. New York Acad. Sci.}
{\bf 576} (1989), 500--535.
}
\bibitem{wilf2006generatingfunctionology}{
H. S. Wilf, {\it Generatingfunctionology}, AK Peters Ltd., 2006, pp. 136--139.
}
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}: Primary 05A10, 11B65, 05A15; Secondary 05A19, 11B73.
\noindent \emph{Keywords:} Binomial coefficients, Stirling numbers, conjoint ranking tables, recurrence relations, generating functions.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A007318},
\seqnum{A008275},
\seqnum{A008277},
and
\seqnum{A068424}.
)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received August 31 2009;
revised version received November 6 2009.
Published in {\it Journal of Integer Sequences}, November 16 2009.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}