A note on lattice chains and Delannoy numbers
John S. CaughmanCliﬀord R. HaithcockJ.J.P. Veerman
Portland State University Box 751, Portland, OR 97207
February 17, 2005
Abstract.
Fix nonnegative integers
n
1
,...,n
d
and let
L
denote the lattice of integer points(
a
1
,...,a
d
)
∈
Z
d
satisfying 0
≤
a
i
≤
n
i
for 1
≤
i
≤
d
. Let
L
be partially ordered by theusual dominance ordering. In this paper we oﬀer combinatorial derivations of a number of resultsconcerning chains in
L
. In particular, the results obtained are established without recourse to generating functions or recurrence relations. We begin with an elementary derivation of the number of chains in
L
of a given size, from which one can deduce the classical expression for the total numberof chains in
L
. Then we derive a second, alternative, expression for the total number of chains in
L
when
d
= 2. Setting
n
1
=
n
2
in this expression yields a new proof of a result of Stanley [7] relatingthe total number of chains to the central Delannoy numbers. We also conjecture a generalizationof Stanley’s result to higher dimensions.
1 Introduction
Fix nonnegative integers
n
1
,...,n
d
and let
L
denote the lattice of integer points (
a
1
,...,a
d
)
∈
Z
d
satisfying0
≤
a
i
≤
n
i
for 1
≤
i
≤
d
. Partially order
L
by setting (
a
1
,...,a
d
)
(
b
1
,...,b
d
) whenever
a
i
≤
b
i
for each
i
(1
≤
i
≤
d
). In various contexts [2, 3, 5], the number of chains in
L
of a given size has been computedusing either recurrence relations or generating functions. Summing this expression over all possible sizes,one obtains an expression for the total number of chains
L
. In the case when the dimension
d
= 2 and thelattice
L
is a square (so that
n
1
,n
2
share a common value
n
), an alternative expression for this quantity wasgiven by Stanley [7]. In particular, he used generating functions to establish that the total number of chainsin
L
equals 2
n
+1
d
n
, where
d
n
denotes the
n
th
Delannoy number. In [8], a bijective proof of Stanley’s resultis given. The bijection given there is the composition of ﬁve combinatorially deﬁned bijections, perhaps atestament to its subtlety.In this paper we begin with an elementary derivation of the number of chains in
L
of a given size usinginclusion/exclusion. We then derive a formula for the total number of chains in
L
when
d
= 2. Setting
n
1
=
n
2
in this expression yields a new proof of Stanley’s result. We conclude with a few remarks on thehypergeometric form of the expressions derived, and ﬁnally, we conjecture a generalization of Stanley’s resultto higher dimensions.
2 Lattice chains
Fix nonnegative integers
n
1
,...,n
d
. Let
L
=
L
(
n
1
,...,n
d
) denote the lattice of integer points (
a
1
,...,a
d
)
∈
Z
d
satisfying 0
≤
a
i
≤
n
i
for 1
≤
i
≤
d
. Recall
L
is partially ordered by the dominance relation, deﬁnedas follows. Given
a
,
b
∈
L
with
a
= (
a
1
,...,a
d
) and
b
= (
b
1
,...,b
d
), we say
a
b
whenever
a
i
≤
b
i
for1
≤
i
≤
d
.By a
chain
in
L
we mean a subset of
L
that is totally ordered by
. A
k
chain
is a chain with
k
elements.Deﬁne
k
max
=
n
1
+
···
+
n
d
+1 and observe that
k
max
is the maximum number of elements of a chain in
L
.1
Let
C
=
C
(
n
1
,...n
d
) denote the set of chains in
L
, and for each integer
k
, let
C
k
=
C
k
(
n
1
,...n
d
) denotethe set of
k
chains in
L
. These sets have been studied in the contexts of subsets of multisets and partitionsof a set [2, 3, 5]. In the next two sections we study expressions for

C
k

and

C

.
2.1 Counting
k
chains
One obvious way to obtain an expression for

C

is to sum

C
k

over all
k
. This requires us to ﬁrst ﬁnd anexpression for

C
k

. And indeed, a simple expression for

C
k

is not diﬃcult to derive, and has been computedin several places [3, 5] for the special case
n
i
= 1 for all
i
, and, in [2], for the general case. Each of thesederivations proceeds either by solving an appropriate recurrence or through the use of generating functions.In this section we oﬀer a direct counting argument for

C
k

using the principle of inclusion/exclusion.
Theorem 1
[2] Fix
n
1
,...,n
d
∈
Z
≥
0
and set
k
max
= 1 +
d
1
n
i
. Then for any integer
k
(0
≤
k
≤
k
max
)
,

C
k
(
n
1
,...,n
d
)

=
k
−
1
r
=0
(
−
1)
r
k
−
1
r
d
i
=1
n
i
+
k
−
rn
i
.
Our proof begins with Lemma 1, which counts the number of sequences
a
1
,...,
a
k
in
L
satisfying
a
1
···
a
k
.
Since such sequences allow duplicate entries, while chains do not, Lemma 1 does not directlycompute

C
k

.
Lemma 1
With the notation of Theorem 1, ﬁx any integer
k
(0
≤
k
≤
k
max
)
. Let
S
k
denote the set of all sequences
a
1
,...,
a
k
in
L
satisfying
a
1
···
a
k
.
Then

S
k

=
d
i
=1
n
i
+
kn
i
.
(1)
Proof.
Consider a sequence
a
1
,...,
a
k
in
L
, where
a
j
= (
a
j
1
,...,a
jd
) for (1
≤
j
≤
k
)
.
This sequencebelongs to
S
k
if and only if for each
i
(1
≤
i
≤
d
)0
≤
a
1
i
≤ ··· ≤
a
ki
≤
n
i
.
(2)The number of integer sequences
a
1
i
,...,a
ki
satisfying (2) is given by
n
i
+
kn
i
. Multiplying these factorstogether as
i
ranges from 1 to
d
, we obtain the result.
As discussed above,
S
k
includes sequences with repeated elements. So we will apply inclusion/exclusionto obtain

C
k

. The next lemma considers the sets to be excluded.
Lemma 2
With the notation of Theorem 1, ﬁx any integer
k
(0
≤
k
≤
k
max
)
,
and let
S
k
be as in Lemma 1. For each
1
≤
i
≤
k
−
1
, let
S
k
(
i
) =
{
a
1
,...,
a
k
∈
S
k

a
i
=
a
i
+1
}
.
Then for any integers
i
i
,...,i
r
such that
1
≤
i
i
<
···
< i
r
≤
k
−
1
,
we have

S
k
(
i
1
)
∩
S
k
(
i
2
)
···∩
S
k
(
i
r
)

=
d
i
=1
n
i
+
k
−
rn
i
.
Proof.
Fix integers
i
i
,...,i
r
such that 1
≤
i
i
<
···
< i
r
≤
k
−
1
.
Each sequence
a
∈
S
k
(
i
1
)
∩
S
k
(
i
2
)
···∩
S
k
(
i
r
)satisﬁes
a
i
j
=
a
i
j
+1
for 1
≤
j
≤
r
. Such a sequence corresponds naturally to a sequence in
S
k
−
r
by deletingthe
r
terms
a
i
j
for 1
≤
j
≤
r
. Replacing
k
by
k
−
r
in Lemma 1 counts

S
k
−
r

. The result follows.
We now prove the theorem.2
Proof of Theorem 1.
Observe

C
k

=
S
k
\
k
−
1
i
=1
S
k
(
i
)
.
By the principle of inclusion/exclusion,

C
k

=
k
−
1
r
=0
(
−
1)
r
i
1
<
···
<i
r

S
k
(
i
1
)
∩···∩
S
k
(
i
r
)

=
k
−
1
r
=0
(
−
1)
r
k
−
1
r
d
i
=1
n
i
+
k
−
rn
i
.
2.2 Counting the total number of chains
In this section we compute

C

, the total number of chains in
L
. One expression is easily obtained using theresult of the previous section. Indeed, recall that a chain in
L
has at most
k
max
=
n
1
+
···
+
n
d
+1 elements.It follows that

C
(
n
1
,...,n
d
)

=
k
max
k
=0

C
k
(
n
1
,...,n
d
)

.
(3)In the special case when
d
= 2 and the lattice
L
is a square (so that
n
1
=
n
2
), Stanley [7, Section 6.3] usedgenerating functions to ﬁnd an alternative expression for this quantity, which we will obtain as Corollary 4below. In this section, however, we begin with a combinatorial derivation of a slight generalization of Stanley’sresult; in particular, we count the total number of chains for the case
d
= 2 without the assumption that
n
1
=
n
2
. Central to our proof is the notion of a
y
strict
chain: a chain in which no two elements have thesame
y
coordinate (ie., 2nd coordinate). We obtain the following theorem.
Theorem 2
Let
n
1
and
n
2
be nonnegative integers. Then

C
(
n
1
,n
2
)

= 2
n
1
+1
n
2
i
=0
n
1
+
ii
n
2
i
.
(4)
Proof.
To each chain
ξ
in
L
(
n
1
,n
2
) we associate a pair (
A
ξ
,ξ
) where
A
ξ
⊆ {
0
,
1
,...,n
1
}
and
ξ
is a
y
strict chain in
L
(
n
1
,n
2
−
1). If
ξ
denotes the chain (
x
1
,y
1
)
(
x
2
,y
2
)
···
(
x
k
,y
k
), then we deﬁne
A
ξ
=
{
x
i

y
i
=
y
i
+1
or
y
i
=
n
2
}
and
ξ
=
ξ
\{
(
x
i
,y
i
)

x
i
∈
A
ξ
}
. See Figure 1.This is a bijective correspondence, and we now exhibit the inverse map which associates a chain in
L
(
n
1
,n
2
) with each pair (
A,ξ
) consisting of a subset
A
⊆ {
0
,
1
,...,n
1
}
and a
y
strict chain
ξ
in
L
(
n
1
,n
2
−
1).Let (
A,ξ
) be such a pair. For each
i
(0
≤
i
≤
n
1
) let top
ξ
(
i
) denote the maximum
y
such that
ξ
∪{
(
i,y
)
}
isa chain in
L
(
n
1
,n
2
). Then the chain associated with the pair (
A,ξ
) is the chain
ξ
=
ξ
∪{
(
i,
top
ξ
(
i
))

i
∈
A
}
.Given this correspondence, it remains only to count the number of pairs (
A,ξ
). Let
ξ
be an
i
element
y
strict chain in
L
(
n
1
,n
2
−
1). Then there are
n
2
i
choices for the
y
coordinates that appear in
ξ
. Oncethe
y
coordinates have been chosen, we may choose the
x
coordinates freely, as long as the resulting choicemaintains the chain condition for
ξ
. That is, we must choose
i x
coordinates such that 0
≤
x
1
≤
x
2
≤ ··· ≤
x
i
≤
n
1
. The number of such choices for the
x
coordinates is given by
n
1
+
ii
. Thus, we have
n
2
i
=0
n
1
+
ii
n
2
i
y
strict chains in
L
(
n
1
,n
2
−
1). For each such chain
ξ
, we have 2
n
1
+1
choices for a subset
A
. It follows thatthe number of pairs (
A,ξ
) is given by the right side of (4).
Remark.
A recursive proof of (4), albeit somewhat less illuminating, can also be given as follows. A simpleinclusion/exclusion argument shows that for positive integers
n
1
and
n
2

C
(
n
1
,n
2
)

= 2

C
(
n
1
,n
2
−
1)

+ 2

C
(
n
1
−
1
,n
2
)
−
2

C
(
n
1
−
1
,n
2
−
1)

.
(5)It is readily veriﬁed that the expression on the right side of (4) also satisﬁes this recurrence, along withappropriate initial conditions.3
0123012345
012012345
0123012345
012012345
A = {2, 5}A = {1, 3}
Figure 1a Figure 1b
Figure 1: Mapping ChainsWe close this section with a few comments on symmetry. Observe that although the quantity

C
(
n
1
,n
2
)

is, by its deﬁnition, symmetric in
n
1
and
n
2
, the expression in (4) is less obviously so. It is perhapsalso worth noting, then, that our expression for

C
(
n
1
,n
2
)

is quite conveniently stated using the notationof hypergeometric series. Recall that for any complex number
a
and any natural number
n
, we deﬁne(
a
)
n
:= (
a
)(
a
+ 1)
···
(
a
+
n
−
1). Using this notation, the
2
F
1
hypergeometric series is deﬁned as follows:
2
F
1
(
a,b
;
c
;
z
) =
∞
n
=0
(
a
)
n
(
b
)
n
(
c
)
n
z
n
n
!for complex
a,b,c,z
with
c
= 0. There are many identities involving such series. For example, one of thesocalled Euler transformations (see [6, p.33]) gives that
2
F
1
(
a,b
;
c
;1
/
2) = 2
a
2
F
1
(
a,c
−
b
;
c
;
−
1)
.
(6)By Theorem 2, we see that
C
(
n
1
,n
2
) = 2
n
2
+12
F
1
(
−
n
1
,n
2
+ 1;1;
−
1)
.
Applying (6), we obtain the more symmetric expression
C
(
n
1
,n
2
) = 2
n
1
+
n
2
+12
F
1
(
−
n
1
,
−
n
2
;1;1
/
2)
.
3 Delannoy numbers
The Delannoy numbers count the number of lattice paths in
L
(
n
1
,n
2
) from (0
,
0) to (
n
1
,n
2
) in which onlyvertical
v
= (0
,
1), horizontal
h
= (1
,
0), and diagonal
d
= (1
,
1) steps are allowed. Such a path is sometimesreferred to as a (restricted) king’s walk. When
n
1
and
n
2
share a common value
n
, we refer to
d
n
=
D
(
n,n
) asthe
central Delannoy numbers
. For arbitrary dimension
d
, we set
D
(
n
1
,...,n
d
) equal to the number of latticepaths in
L
(
n
1
,...,n
d
) that begin from the srcin and terminate at (
n
1
,...,n
d
), in which only positive stepsfrom the
d
dimensional unit hypercube are allowed. This follows [4]. Indeed, for more about generalizationsof the Delannoy numbers, we refer the reader to [4, 1].Although the Delannoy numbers are typically derived recursively or with generating functions, we cancount the number of restricted king’s walks as follows. Observe that
D
(
n
1
,n
2
) =
D
(
n
2
,n
1
) so we mayassume without loss of generality that
n
1
≤
n
2
.
Theorem 3
Let
n
1
,n
2
be nonnegative integers such that
n
1
≤
n
2
. Then
D
(
n
1
,n
2
) =
n
1
i
=0
n
2
+
ii
n
2
n
1
−
i
.
(7)
Proof.
A walk is a sequence of
h
,
v
, and
d
steps. To reach (
n
1
,n
2
), the number of
h
,
d
steps must sum to
n
1
and the number of
v
,
d
steps must sum to
n
2
. Let
i
denote the number of diagonal
d
steps in a givenwalk. Clearly, 0
≤
i
≤
n
1
. Also, the total number of steps of such a walk is
n
1
+
n
2
−
i
. The number of
h
4
steps is given by
n
1
−
i
. The number of
v
steps is
n
2
−
i
. So the total number of such walks is given by thetrinomial coeﬃcient
n
1
+
n
2
−
ii,n
1
−
i,n
2
−
i
=
n
1
+
n
2
−
in
1
−
i
n
2
i
. Thus, the total number of walks is
n
1
i
=0
n
1
+
n
2
−
in
1
−
i
n
2
i
.
Reindexing the sum (replacing
i
by
n
1
−
i
) we obtain the desired result.
Comparing lines (4) and (7), we have the following.
Corollary 4
[7, 8] For any nonnegative integer
n
,
C
(
n,n
) = 2
n
+1
D
(
n,n
)
.
Remark.
We note that the expression in (7) can also be established recursively. Indeed, a simple inclusion/exclusion argument shows that
D
(
n
1
,n
2
) =
D
(
n
1
,n
2
−
1) +
D
(
n
1
−
1
,n
2
) +
D
(
n
1
−
1
,n
2
−
1)
.
It is then readily veriﬁed that the expression on the right side of (7) also satisﬁes this recurrence, along withappropriate initial conditions.We conclude this paper with a conjecture, analogous to Corollary 4, that appears to be supported bynumerical evidence.
Conjecture 1
If
n
1
=
n
2
=
···
=
n
d
, then
C
(
n
1
,n
2
,...,n
d
) = 2
n
1
+1
D
(
n
1
,n
2
,...,n
d
)
.
References
[1] JM. Autebert and S. R. Schwer. On generalized Delannoy paths.
SIAM J. Discrete Math.
, 16(2):208–223,2003.[2] WS. Chou. Formulas for counting chains in multisets.
Utilitas Mathematica
, 40:3–12, 1991.[3] H. W. Gould and M. E. Mays. Counting chains of subsets.
Utilitas Mathematica
, 31:227–232, 1987.[4] S. Kaparthi and H. R. Rao. Higher dimensional restricted lattice paths with diagonal steps.
DiscreteApplied Mathematics
, 31:279–289, 1991.[5] R. B. Nelson and Jr. H. Schmidt. Chains in power sets.
Mathematics Magazine
, 64:23–31, 1991.[6] H. M. Srivastava and H. L. Manocha.
A Treatise on Generating Functions
. Ellis Horwood Limited, WestSussex, 1984.[7] R. P. Stanley.
Enumerative Combinatorics, Volume 2
. Cambridge University Press, Cambridge, 1999.[8] R. A. Sulanke. Counting lattice paths by narayana polynomials.
The Electronic Journal of Combinatorics
,7(1):1–9, 2000.5