\documentclass[12pt,reqno,oneside]{amsart}
\thispagestyle{empty}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\gdef\theequation{\thesection{.}\arabic{equation}}
\oddsidemargin 0in
\evensidemargin 0in
\textwidth 6.5in
\newcommand{\reals}{\mathbb{R}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bdf}{\mathbf{f}}
\newcommand{\bdg}{\mathbf{g}}
\newcommand\lcb{\left\{}
\newcommand\rcb{\right\}}
\newcommand\lb{\left[}
\newcommand\rb{\right]}
\newcommand\lp{\left(}
\newcommand\rp{\right)}
\newcommand\cmp{\mathbf{p}}
\newcommand\cmpq{\mathbf{q}}
\newcommand\nodd{{\mathop{o}}}
\newcommand{\neven}{{\mathop{e}}}
%\newcommand{\nodd}{\mathfrac{o}}
\newcommand{\hu}{\hat{u}}
\newcommand{\hv}{\hat{v}}
\newcommand{\hf}{\hat{f}}
\newcommand{\fS}{\mathfrak{S}}
\newcommand\Res{\mathop{\mathrm{Res}}}
\newcommand\esp{\mathbf{e}}
\newcommand\E{\mathrm{e}}
\newcommand\sth{^{\text{th}}}
\newcommand\natnums{\mathbb{N}}
\newcommand\cD{\mathcal{D}}
\newcommand\cH{\mathcal{H}}
\newcommand\cG{\mathcal{G}}
\newcommand\cJ{\mathcal{J}}
\newcommand\cT{\mathcal{T}}
\newcommand\cR{\mathcal{R}}
\newcommand\tH{\widetilde{\cH}}
\newcommand\tT{\widetilde{\cT}}
\newcommand\hT{\widehat{\cT}}
\newcommand\hH{\widehat{\cH}}
\newcommand\hU{\widehat{U}}
\newcommand\hP{\widehat{P}}
\newcommand\hQ{\widehat{Q}}
\newcommand\tphi{\tilde{\phi}}
\newcommand\hphi{\hat{\phi}}
\newcommand\tf{\tilde{f}}
\newcommand\tU{\tilde{U}}
\newcommand\tpsi{\tilde{\psi}}
\newcommand\trho{\tilde{\rho}}
\newcommand{\bisq}{b_{n,i}^{\, 2}}
\newcommand{\subover}[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\title[Composition sum identities]{Composition sum identities related to the
distribution of coordinate values in a discrete simplex.}
\author{
R. Milson\\Dept. Mathematics \& Statistics\\Dalhousie University\\
Halifax, N.S. B3H 3J5\\
Canada\\
{\tiny{milson@mathstat.dal.ca}} }
\dedicatory{{\rm Submitted: March 27, 2000; Accepted: April 13,
2000.\\ AMS Subject Classifications: 05A19, 05A20. }}
\thanks{This research supported by a Dalhousie University grant.}
%\pagestyle{empty}
\begin{document}
\begin{abstract}
Utilizing spectral residues of parameterized, recursively defined
sequences, we develop a general method for generating identities of
composition sums. Specific results are obtained by focusing on
coefficient sequences of solutions of first and second order,
ordinary, linear differential equations.
Regarding the first class, the corresponding identities amount to a
proof of the exponential formula of labelled counting. The
identities in the second class can be used to establish certain
geometric properties of the simplex of bounded, ordered, integer
tuples.
We present three theorems that support the conclusion that the inner
dimensions of such an order simplex are, in a certain sense, more
ample than the outer dimensions. As well, we give an algebraic
proof of a bijection between two families of subsets in the order
simplex, and inquire as to the possibility of establishing this
bijection by combinatorial, rather than by algebraic methods.
\end{abstract}
\maketitle
\pagestyle{myheadings}
\section{Introduction}
\markboth{\hfill{\sc the electronic journal of combinatorics
\textbf{7} (2000), \#R20}} {{\sc the electronic journal of
combinatorics \textbf{7} (2000), \#R20}\hfill}
The present paper is a discussion of composition sum identities that
may be obtained by utilizing spectral residues of parameterized,
recursively defined sequences. Here we are using the term
``composition sum'' to refer to a sum whose index runs over all
ordered lists of positive integers $p_1, p_2, \ldots, p_l$ that such
that for a fixed $n$,
$$p_1+\ldots + p_l=n.$$
Spectral residues will be discussed in detail
below.
Compositions sums are a useful device, and composition sum identities
are frequently encountered in combinatorics. For example the Stirling
numbers (of both kinds) have a natural representation by means of such sums:
\cite[\S 51, \S 60]{Jordan}:
$$
s^l_n = \frac{n!}{l!}
\sum_{p_1+\ldots+p_l=n}
\frac{1}{p_1\,p_2\,\ldots p_l}; \qquad
\mathfrak{S}^l_n = \frac{n!}{l!}
\sum_{p_1+\ldots+p_l=n}
\frac{1}{p_1!\,p_2!\,\ldots p_l!}.
$$
There are numerous other examples. In general, it is natural to
use a composition sum to represent the value of quantities $f_n$ that
depend in a linearly recursive manner on quantities $f_1, f_2, \ldots,
f_{n-1}$. By way of illustration, let us mention that this point of
view leads immediately to the interpretation of the $n\sth$ Fibonacci
number as the cardinality of the set of compositions of $n$ by
$\{1,2\}$ \cite[2.2.23]{Goulden}
To date, there are few systematic investigations of composition sum
identities. The references known to the present author are
\cite{Hoggatt} \cite{Homenko} \cite{Moser}; all of these papers obtain
their results through the use of generating functions. In this
article we propose a new technique based on spectral residues, and
apply this method to derive some results of an enumerative nature.
Let us begin by describing one of these results, and then pass to a
discussion of spectral residues.
Let $S^3(n)$ denote the discrete simplex of bounded, ordered triples
of natural numbers:
$$S^3(n) = \{(x,y,z)\in \natnums^3: 0\leq x