Enumeration of Sand Piles

Enumeration of Sand Piles

Sylvie Corteel

Prism, Université de Versailles - Saint-Quentin-en-Yvelines (France)

Algorithms Seminar

October 16, 2000

[summary by Michel Nguyen-The]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

Abstract

Sand piles are integer partitions that can be obtained from a column of n grains by moving grains from left to right according to rules defined by a model. We try to better understand the structure of those objects by decomposing and counting them. For the model introduced by Goles, Morvan, and Phan, we fing generating functions according to area, height, and width. We establish a bound for the number of the sand piles consisting of n grains in IPM(k) for large n. We present the series according to area and height for Phan's model L(q). We introduce a more general model, where grains can also go to the left, that we call Frobenius sand piles. (Joint work of S. Corteel with D. Gouyou-Beauchamps (LRI, Orsay)).

1 Preliminaries and SPM(k) Model

After the necessary basic concepts, we present here the simplest model of sand pile, i.e., the SPM(k) model, from which all other models are derived.

1.1 Definitions

A sand pile made of n grains is a partition of the integer n. A partition of an integer n is a non-increasing sequence of positive integers l=(l₁,...,l_l). The l_i are called the parts of the partition. The area of the sand pile is the sum |l|=l₁+...+l_l=n. The height of the sand pile is the number h(l)=l of parts of the partition. For any partition l, we will consider that l_i=0 for i<1 and i>h(l). The width w(l) of the sand pile l is the largest part l₁. The Ferrers diagram of a partition l is a drawing of l such that the ith column is a pile of l_i packed squares (called grains). The rows are labelled from bottom to top. The conjugate l' of l is the partition whose ith part is the number of squares in the ith column of the Ferrers diagram of l.

Let p=(p₁,...,p_l) be a sand pile and p'=(p'₁,...,p'_p₁) be its conjugate. The moves of the sand grains are of two types (see Figure 1):

Vertical rule: a grain can move from column i to column i+1 if p'_i-p'_i+1£2, so that

( p'₁,···,p'_p₁ ) is replaced with ( p'₁,···,p'_i-1,p'_i+1+1,···,p'_p₁ ) .
Horizontal rule: a grain can move from column i to column j if j>i+1 and p'_i-1=p'_i+1=...=p'_j=p'_j+1+1, so that

( p'₁,···,p'_p₁ ) is replaced with ( p'₁,···,p'_i-1, p'_i+1,···,p'_j, p'_j+1+1,···,p'_p₁ ) .

The shift is said to have length 0 or or j-i-1, respectively.

(a)(b)

Figure 1: (a) Application of horizontal rule to (5,4,2,1) and (4,3,2,1,1); (b) application of vertical rule to (4,4,2,1) and (4,3,2,1,1,1).

In the SPM(k) model (Sand Pile Model), introduced by Goles and Kiwi [3], the initial configuration is made of one column of n grains, and the only available rule is the vertical rule.

1.2 Generating function

Let p(n,k) denote the number of partitions of n of width k. Then:

F(q,x)=1+

n,k³1

p(n,k)qⁿx^k =xqF(q,x)+F(q,xq)

i=1

1-xqⁱ

1.3 Example of bijection

There is a bijection between partitions with odd parts and partitions with distinct parts, as is reflected by the generating functions identity

i=1

1-q²ⁱ⁺¹

i=1

1-q²ⁱ

1-qⁱ

i=1

(

1+qⁱ

)

1.4 Order on partitions

Let µ=(µ₁,µ₂,...) and l=(l₁,l₂,...) be two partitions of n. We say that µ³l if and only if there exists a sequence of moves of n induced by the rules to go from µ to l. In the SPM(k) model, this order is equivalent to the dominance order L_B(n) [1] on the conjugates: µ³l if and only if å_i=1^jµ'_i³å_i=1^jl'_i for all j³1. Brylawski [1] showed:

Theorem 1 Let n be an integer. The set of partitions of n with the previously defined order is a lattice, where the maximal element is (1,1,...,1), and the minimal element is (n). Moreover, the infimum and the supremum of two partitions can be respectively defined as follows:

inf(µ,l)=p such that p'_j=min(å_i=1^jµ'_i,å_i=1^jl'_i) -å_i=1^jp'_i for all j³1.
sup(µ,l)=a such that a'_j=max(å_i=1^jµ'_i,å_i=1^jl'_i) -å_i=1^ja'_i for all j³1.

Figure 2: L_B(6)

In Figure 2, the maximal element (1,1,1,1,1,1) is on the left.

Length of a maximal chain

The length of a maximal chain is greater than 2n-3 [1], and smaller than 2(

l+1

)+lj+1 [3], where l and j are defined by n=j+l(l+1)/2 and 0£ j£ l. For n=6, the two bounds are equal to 9, which shows that they both can be attained. The corresponding maximal chain is displayed in Figure 2.

2 IPM(k) Model

A more realistic generalization of SPM(k) model limits the lengths of the possible horizontal shifts of a grain.

2.1 Definition

In [4], the sand piles in IPM(k) are characterized in the following way:

Proposition 1 A sand pile in IPM(k) is a partition p=(p₁,...,p_l) of n such that

for 1£ i£ l, 0£p_i-p_i+1£ k+1;
for any i<j with p_i-p_i+1=k+1 and p_j-p_j+1=k+1, there exists z with i<z<j such that p_z-p_z+1< k.

2.2 Generating functions

2.2.1 Area and height

Theorem 2 The generating function S_k(q,x) of IPM(k) sand piles, with q and x respectively counting area and height, satisfies

S_k(q,x)=1+

pÎIPM(k)

x^l(p)q^|p| =1+

i=1

xqⁱ

1-xqⁱ

S_k(q,xqⁱ) +xq^k+1S_k(q,xq^k).

Figure 3: Decomposition of a sand pile in IPM(1).

Proof. A sand pile in IPM(k) is either the empty partition, or a partition in IPM(k) where one duplicates i times the highest column and adds to it at least one part i (1£ i£ k), or a partition in IPM(k) where one duplicates k times the highest column and adds to it one part of length k+1. This decomposition yields the last expression for S_k(q,x) in the statement of the theorem, after noting that S_k(q,xq^r) is the generating function obtained by duplicating r times the highest column in each sand pile.

Note the particular cases:

S₁(q,x)=1+

n³1

xⁿq^n(n+1)/2

i=1

æ
ç
ç
è

1-xqⁱ

ö
÷
÷
ø

; S_¥(q,x)=

i=1

æ
ç
ç
è

1-xqⁱ

ö
÷
÷
ø

2.2.2 Area and width

Theorem 3 The generating function S_k(q,y) of IPM(k) sand piles, with q and y respectively counting area and width, satisfies:

S_k(q,y)=

æ
ç
ç
è

1-(yq)^k+1

1-yq

+y^kq^k-1

ö
÷
÷
ø

S_k(q,yq)+y^kq^k-1

(

S_k(q,yq)-S_k(q,yq²)

)

In particular:

₁(q,y)=1+

n³1

yⁿq^n(n-1)/2

i=1

1+q-q^i-1

1-qⁱ

2.2.3 Height and width

Let p_k(h,w) be the number of sand piles in IPM(k) of height h and width w and P_k,h(y) the generating function å_w³0p_k(h,w)y^w.

Theorem 4 The generating function P_k,h(y) follows the recurrence:

P_k,0(y)=1; P_k,1(y)=y

1-y^k+1

1-y

; P_k,2(y)=y

1-y^k+1

1-y

1-y^k+2

1-y

-y^2(k+1);

P_k,h(y)=

æ
ç
ç
è

1-y^k+1

1-y

+y^k

ö
÷
÷
ø

P_k,h-1(y)-y^kP_k,h-2(y) for h³3.

Now, let P_k(x,y) be the width (variable x) and the height (variable y) generating function å_h³0P_k,h(y)x^h. From the previous recurrence one gets:

Theorem 5 The generating function P_k(x,y) is given by:

P_k(x,y)=

1-x(y^k+1-y^k+1)+x²y^k(1-y)

1-x

æ
ç
ç
è

1-y^k+1

1-y

+y^k(1-x)

ö
÷
÷
ø

Let p_k(n) be the number of sand piles in IPM(k) of half perimeter (width + height) n, and P_k(x)=å_n³0p_k(n)xⁿ be its generating function. As P_k(x)=P_k(x,x), its expression is:

P_k(x)=

(1-x)²(1-x^k+1+x^k+2)

1-2x-3x^k+2+x^k+3+x^k+1

When k grows, the quantity p_k(n), asymptotically equal for large n to c_k/r_kⁿ with c_kÎR and r_k the smallest root of the denominator 1-2x-3x^k+2+x^k+3+x^k+1, gets closer to 2ⁿ, the number of partitions of semi-perimeter n.

2.3 Asymptotics

Define

p_k=[qⁿ]

i³1

1-q^ki

1-qⁱ

, B_k=(

k-1

)^1/2, and C_k=

æ
ç
ç
è

k-1

6k³

ö
÷
÷
ø

^1/4.

Then p_k(n)=C_kn^-3/4exp(B_kn^1/2)O(1+n^-1/4). If I_k(n) is the number of partitions of n in IPM(k), then p_k+1(n)£ I_k(n)£ p_k+2(n).

3 The Model L(q)

The model L(q) generalizes the SPM(k) by restricting its vertical rule, instead of the horizontal rule as IPM(k). Namely, the difference between the two consecutive columns involved must be greater then q.

3.1 Definition

In [4], the sand piles in L(q) are characterized in the following way:

Proposition 2 A sand pile in L(q) is a partition p=(p₁,...,p_l) of n such that

for 1£p₁, p'_i-p'_i+1³q-1;
for any i<j with p'_i-p'_i+1=q-1 and p'_j-p'_j+1=q-1, there exists z with i<z<j such that p_z-p_z+1>q.

Let L_q(q,x)= 1+å_{pÎ L(q)}x^l(p)q^|pi| the generating function of sand piles in L(q) according to their height and area.

Lemma 1 L_q(q,x) satisfies the q-equation:

L_q(q,x)=

1-(xq)^q-1

1-xq

æ
ç
ç
è

(xq)^q-1

1-xq

+x^q-1q^q

ö
÷
÷
ø

L_q(q,xq).

Theorem 6 L_q(q,x) is given by:

_q(q,x)=

n³0

x^{q n}q^{q n(n+1)/2}

1-(xqⁿ⁺¹)^q

1-xqⁿ⁺¹

i=1

æ
ç
ç
è

1-xqⁱ

ö
÷
÷
ø

Bounds can be obtained for all q for the number l_n,q of partitions in L(n,q).

4 Frobenius Model

Another generalization consists in allowing the grains to move both to the left and to the right. In [2], Corteel defines such a model, called the Frobenius sand pile, in the following way:

Definition 1 Let l be an integer. A Frobenius sand pile is a pair consisting of a pivot indice p(a)£ l and a sequence of integers (a₁,a₂,...,a_l) such that

a₁£ a₂£ ...£ a_p(a) ³ a_p(a)+1³...³ a_l.

4.1 Order on Frobenius sand piles

Definition 2 Let a=(p(a),(a₁,a₂,...,a_l)) and b=(p(b),(b₁,b₂,...,b_l)) be two Frobenius sand piles. Then a³_Fb if and only if, for all i,j³0,

p(a)+j

l=p(a)-i

a_l³

p(b)+j

l=p(b)-i

b_l.

Proposition 3 Let L_F(n) be the set of Frobenius partitions ordered by ³_F. Then L_B(n) is a suborder of L_F(n).

Length of a maximal chain

For n³3, the length of a maximal chain is greater than 2n-4, and smaller than 2(

l+1

)+lj+1, where l and j are defined by n=j+l(l+1)/2 and 0£ j£ l.

Definition 3 Let a=(p(a),(a₁,a₂,...,a_l)) be a sand pile. a_<, a_>, a_£, and a_³ are defined by

a_<

(

a_p(a)-1,a_p(a)-1,...,a₁

)

;

a_>

(

a_p(a)+1,a_p(a)+2,...,a_l

)

;

a_£

(

a_p(a),a_p(a)-1,...,a₁

)

;

a_³

(

a_p(a),a_p(a)+1,...,a_l

)

If we constrain horizontal shifts to be smaller than k, we can create an increasing sequence of orders IFPM(k) with the relations of order ³_k. The Frobenius sand piles of IFPM(k) are characterized by:

Proposition 4 Let a=(p(a),(a₁,a₂,...,a_l)) be a sand pile. This sand pile belongs to IFPM(k) if and only if both of a_< and a_>, and at least one of a_£ and a_³ belong to IPM(k).

4.2 Generating functions

The only available generating function is the series of F-partitions given by

k³1

q^k

i=1

(

1-qⁱ

)

For IFPM(k), we must so far satisfy ourselves with the bound F_k(n)£ |IFPM(n,k)| £ F_k+1(n) for

F_k(n)=[qⁿ]

æ
ç
ç
è

j³1

q^j

i=1

1-q^(k+1)i

(

1-qⁱ

)

ö
÷
÷
ø

5 Conclusion and Open Questions

We have studied different sand pile models related to integer partitions, and in particular we have computed generating functions and asymptotic bounds. A question of interest would consist in getting exact asymptotics instead of asymptotic bounds only. One could start with the area generating function in the SPM case, given by

n³0

xⁿq^n(n+1)/2

i=1

æ
ç
ç
è

1-qⁱ

ö
÷
÷
ø

References

[1]: Brylawski (Thomas). -- The lattice of integer partitions. Discrete Mathematics, vol. 6, 1973, pp. 201--219.
[2]: Corteel (Sylvie). -- Problèmes énumératifs issus de l'Informatique, de la Physique et de la Combinatoire. -- Thèse, Université Paris-Sud, 2000.
[3]: Goles (Eric) and Kiwi (Marcos A.). -- Games on line graphs and sand piles. Theoretical Computer Science, vol. 115, n°2, 1993, pp. 321--349.
[4]: Phan (Ha Duong). -- Structures ordonnées et piles de sable. -- Thèse, Université Paris 7, 1998.

This document was translated from L^AT_EX by H^EV^EA.