Printer Friendly

Parallel rank of two sandpile models of signed integer partitions.

1. Introduction

The study of the order relation in particular subsets of integer partitions has been recently addressed from the point of view of the discrete dynamical models. The excellent survey [1] describes several subsets of integer partitions which have a lattice structure in terms of discrete dynamical models. Before going further, we borrow from [1] the following description of discrete dynamical model (briefly DDM): "At each (discrete) time step, such a model is in some state, which we call a configuration. Configurations are described by combinatorial objects, like graphs, integer partitions, and others, and we will not distinguish a configuration and its combinatorial description. A discrete dynamical model is then defined by an initial configuration and (some) evolution (rules) which (say) under which conditions the (configurations) may be changed, and which (describe) the new configurations one may obtain. These (rules) can generally be applied under a local condition, and (they imply) a local modification of the current configuration. Note that in the general case the evolution (rules) can be applied in several places in a configuration, leading to several configurations. If a configuration c' can be obtained from a configuration c after one application of (some) evolution (rule), we say that c' is a successor of c, or c is a predecessor of c', which is denoted by c [right arrow] c'". In this paper, we consider integer partitions; therefore, we use the term configuration as an equivalent to integer partition. There are two ways in which we can apply the evolution rules on a given configuration: a sequential way (in this case, we refer also to sequential dynamic of the DDM) and a parallel way (in this case, we refer also to parallel dynamic of the DDM). In the sequential way, we apply the evolution rules separately on each summand of the configuration. In the parallel way, we apply the evolution rules concurrently on all the summands of the configuration. When we start from the initial configuration and apply the evolution rules in a sequential way, generally we obtain an oriented graph which represents the Hasse diagram of a poset of integer partitions with an order relation [??]. In this case, one usually proves that the relation c [right arrow] c' is equivalent to saying that c is covered by c with respect to the partial order [??]. Therefore, several concepts of the classical order theory find their interesting formulation in dynamic terms. The first implicit formulation of the covering rules of an integer partitions lattice as evolution rules of a DDM was given in the famous Brylawski paper [2]. In this paper, Brylawski proposed a dynamical approach in order to study the lattice [L.sub.B](n) of all the partitions of a fixed positive integer n with the dominance order. However, the explicit identification of a specific set of integer partitions with a DDM begins in [3, 4]. In the DDM introduced by Goles and Kiwi in [4], denoted by SPM(n), a configuration is an integer partition a = ([a.sub.1],..., [a.sub.n]) of the positive integer n, and each summand of a is identified with a pile of sand grains; hence, the name is sandpile model (briefly SPM). In this model, there is only one evolution rule.

Rule 1 (vertical rule). One grain can move from a column to the next one if the difference of height of these two columns is greater than or equal to 2.

In the model [L.sub.B](n) (introduced by Brylawski [2]), the movement of a sand grain respects Rule 1 and also the following.

Rule 2 (horizontal rule). If a column containing p + 1 grains is followed by a sequence of columns containing p grains and then one column containing p - 1 grains, one grain of the first column can slip to the last one.

There are a lot of specializations and extensions of this model which have been introduced and studied under different names, different aspects, and different approaches. The SPM(n) can be also related to the self-organized criticality (SOC) property, introduced by Baket al. in [5]. The study of such systems has been developed in an algebraic context [6], in a combinatorial game theory setting [4,7, 8], in the theory of cellular automata [9-11], and in the setting of discrete dynamical systems [12-14].

There exists a wide literature concerning dynamical models related in several ways to the original model SPM(n), [8,15-29].

When we study the parallel dynamic of an SPM which also has a lattice structure, starting from its initial configuration (denoted by [??]), we always arrive after s unit time steps to a unique final configuration (denoted by [??]), that is, the maximum of the correspondent lattice. This nonnegative integer s, denoted by [T.sub.par]([??]), was introduced explicitly in [3, 4]. The number [T.sub.par]([??]) is relevant to the study of a DDM of integer partitions which is also a graded lattice because it represents a type of "parallel rank" of the graded lattice. The classical concept of rank can be identified with the number of sequential unit steps needed to reach [??] starting from [??], and in [4] this number is denoted by [T.sub.seq]([??]).Our question is then as follows: is it possible to refine the concept of "parallel rank" [T.sub.par]([??]) in such a way that this refinement conducts us to have further information concerning the graded lattice? For example, can the parallel dynamic of the model, in some sense, characterize the symmetry of the corresponding lattice? It is very difficult, in general, to establish, for example, when a graded lattice has the Sperner property, or it is rank unimodal or rank symmetric. Can a refinement of the study of the parallel dynamic of an SPM that is also a graded lattice be helpful in addressing these problems? In this paper, we introduce and study some concepts related to the parallel dynamic of SPMs, and we study these concepts in the wider environment of the signed integer partitions, that is, integer partitions whose summands can be also negative. The signed integer partitions have been recently introduced by Andrews in [30]and further studied in [31] from an arithmetical point of view. The reason why we work in the signed integer partitions environment is not only formal. In the context of the signed integer partitions, it is easier to see the symmetry of the examined models. Almost all these models of the signed integer partitions are equipped with an involution order-reversing map that makes their self-duality immediately clear. Moreover, a signed integer partition is a generalization of a usual integer partition; therefore, all the classical results can be considered as particular cases of their analogues obtained with signed integer partitions. In the sequel, we assume that (X, [??]) is a finite graded lattice of signed integer partitions with minimum [??] and maximum [??]. We denote by rank(X) the rank of X. Moreover, we also assume that X is a generic deterministic DDM having k distinct evolution rules [R.sub.1],..., [R.sub.k]. In our case, this means that at each position at most one rule is applied (however the same rule maybe applied at several different positions). In our model X, given two configurations w, w' [member of] X, it results that w is covered by w' (with respect to the partial order [??]) if and only if w' is obtained from w with the application of some rule [R.sub.i]. Therefore, in the sequel, we can always identify [T.sub.seq]([??]) with rank(X).

If w and w' are two different configurations of X, we say that w' is a parallel successor of w, and we write w [??] w' or w' = w [??] if w' is the configuration which is obtained with all the possible parallel applications of the rules [R.sub.1],..., [R.sub.k] on the parts of w. If we apply in parallel [m.sub.i] times the rule [R.sub.i] on w, for i = 1,..., k, in order to obtain w', we write w [??] <([m.sub.1],..., [m.sub.k])>w', and we also set M(w) := ([m.sub.1],..., [m.sub.k]) and [absolute value of M(w)] := [m.sub.1] +... + [m.sub.k]. We write w [??] <M(w), M(u),...,M(z)>w' if there exists u, v,..., z such that w [??] <M(w)> u [??] 4 <M(u)> v [??]... z [??] <M(z)>w'. Let us note that there is a unique finite sequence <[w.sub.0], [w.sub.1],..., [w.sub.s]> of configurations in X such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

The sequence in (1) is a chain of length s in X that we call fundamental chain of X. It is clear that

[s - 1.summation over (i = 1)] [absolute value of M([w.sub.i])] = [T.sub.seq]([??]) (2)

and [T.sub.par]([??]) = s. We call parallel rank of X the integer [T.sub.par]([??]) and sequential rank of X the integer [T.sub.seq]([??]). We also call fundamental sequence of X the integer sequence

([absolute value of M([w.sub.0])], [absolute value of M([w.sub.1])],..., [absolute value of M([w.sub.s-1])]). (3)

We say that X is parallel unimodal if the fundamental sequence of X is a unimodal sequence; we also say that X is parallel symmetric if the fundamental sequence of X is a symmetric sequence. In this paper, we compute the parallel rank and the fundamental sequence in two cases. In the first case, when X is the lattice P(n, r) of all the signed integer partitions of the form [a.sub.r],..., [a.sub.1], [b.sub.1],..., [b.sub.n - r], where n [greater than or equal to] r [greater than or equal to] 0 are two fixed integers and r [greater than or equal to] [a.sub.r] [greater than or equal to]... [greater than or equal to] [a.sub.1] [greater than or equal to] 0 [greater than or equal to] [b.sub.1] [greater than or equal to]... [greater than or equal to] [b.sub.n - r] [greater than or equal to] -(n - r). In the second (more difficult) case, when X is the sublattice P(n, d, r) of all the signed integer partitions of P(n, r) having exactly d nonzero parts. The paper is structured as follows. In Section 2, we define the lattice P(n, r) and establish the evolution rules which determine its covering relations, and we compute the usual rank, the parallel rank, and the fundamental sequence of P(n, r). In Section 3, we introduce a new integer parameter 1 [less than or equal to] d [less than or equal to] n and define the sublattice P(n, d, r). We establish three evolution rules which determine the covering relations in P(n, d, r) and determine the usual rank of this lattice. In Section 4, we compute the parallel rank and the fundamental sequence of P(n, d, r) for all the values of the integers parameters n, d, and r. The complete results of our computations are listed in Tables 1 and 2.

2. The Sandpile Model P(n, r)

In this section, we introduce the lattice of signed integer partitions P(n, r), and we examine some of its basic properties. Let n, r be two fixed nonnegative integers such that n [greater than or equal to] r. We call (n, r)-signed partition an n-tuple of integers

[a.sub.r]... [a.sub.1] | [b.sub.1]... [b.sub.n - r], (4)

such that

(i) [a.sub.1],..., [a.sub.r] [member of] {1,..., r, 0},

(ii) [b.sub.1],..., [b.sub.n - r] [member of] {-1,..., -(n - r), 0},

(iii) [a.sub.r] [greater than or equal to]... [greater than or equal to] [a.sub.1] [greater than or equal to] 0 [greater than or equal to] [b.sub.1] [greater than or equal to]... [greater than or equal to] [b.sub.n - r].

In some cases, when n and r are clear from the context, we say simply signed partition instead of (n, r)-signed partition. We denote by P(n, r) the set of all the (n, r)-signed partitions. If w is an (n, r)-signed partition, we call parts of w the integers [a.sub.r],..., [a.sub.1], [b.sub.1]... [b.sub.n - r], nonnegative parts of w the integers [a.sub.r],..., [a.sub.1], and non-positive parts of w the integers [b.sub.1],..., [b.sub.n - r]. We set [summation](w) := [[summation].sup.r.sub.i = 1] [a.sub.i] + [[summation].sup.n - r.sub.j = 1] [b.sub.j], and if m [member of] Z is such that [summation](w) = m, we say that w is an (n, r)-signed partition of m; in this case, we write w [??] m. We set [w.sub.+] = [a.sub.r]... [a.sub.1] | and [w.sub.-] = |[b.sub.1]... [b.sub.n - r]. In order to simplify the notations, in the numerical examples we write the integers [b.sub.1],..., [b.sub.n - r] of a generic (n, r)-signed partition without the minus sign. For example, we write 44l0 | 0ll25 instead of 44l0 | 0(-1)(-1)(-2)(-5). Sometimes, when we do not distinguish between nonnegative and nonpositive parts, we write an (n, r)-signed partition without vertical bar |. Also, we denote by [[absolute value of w].sub.>] the number of parts of w that are strictly positive, with [[absolute value of w].sub.<] the number of parts of w that are strictly negative, and we set [parallel]w[parallel] = [[absolute value of w].sub.>] + [[absolute value of w].sub.<]. If w = [a.sub.r]... [a.sub.1] | [b.sub.1]... [b.sub.n - r] and w' = [a'.sub.r].... [a'.sub.1].... [b'.sub.n - r] are two (n, r)-signed partitions, we set [w.sub.+] = [w'.sub.+] if [a'.sub.i] = [a.sub.i] for all i = r,..., 1, [w.sub.-] = [w'.sub.-] = [w'.sub.-] if [b'.sub.j] = [b.sub.j] for all j = 1,..., n - r, and w = w' if [w.sub.+] = [w'.sub.+] and [w.sub.-] = [w'.sub.-]. On P(n, r), we consider the partial order on the components that we denote by [??]. As usual, we write w [??] w' if w [??] w' and w [not equal to] w'. Moreover, we write w [??] w' (or w' [??] w) if w' covers w. Since (P(n, r), [??]) is a finite distributive lattice (because its partial order is on the components), it is also graded with minimum element 0... 0 | (n - r)... (n - r) and maximum element r... r | 0... 0.

Now let us describe the evolution rules which describe P(n, r) as a discrete dynamical model. In the sequel, if w [member of] P(n, r), were present the sequence of the positive parts of w as a not-increasing sequence of columns of stacked squares and the sequence of the negative parts of w as a not-decreasing sequence of columns of stacked squares. We call pile a column of stacked squares and grain each square of a pile. For example, if n = 10, r = 6, the configuration

(5)

is identified with the signed partition 433100 | 0113 [member of] P(10,6).

Let w = [a.sub.r]... [a.sub.1] | [b.sub.1]... [b.sub.n - r] [member of] P(n, r). We formally set [a.sub.0] = 0, [a.sub.r + 1] = r, and [b.sub.0] = 0. If 0 [less than or equal to] i [less than or equal to] r + 1, we call at the ith-plus pile of w, and if 0 [less than or equal to] j [less than or equal to] n - r, we call [b.sub.j] the jth-minus pile of w. We call [a.sub.i] plus singleton pile if [a.sub.i] = 1 and [b.sub.j] minus singleton pile if [b.sub.j] = -1. If 1 [less than or equal to] i [less than or equal to] r + 1, we say that w has a plus step at i if [a.sub.i] - [a.sub.i - 1] [greater than or equal to] 1. If 1 [less than or equal to] j [less than or equal to] n - r, we say that w has a minus step at j if [absolute value of [b.sub.j]] - [absolute value of [b.sub.j - 1]] [greater than or equal to] 1.

Remark 1. The choice to set [a.sub.0] = 0, [a.sub.r + 1] = r, and [b.sub.0] = 0 is a formal trick to decrease the number of rules necessary for our model. This means that when we apply the next rules to one element w [member of] P(n, r), we think that there is an "invisible" extra pile in the imaginary place r + 1 having exactly r grains, an "invisible" extra pile with 0 grains in the imaginary place to the right of a1 and to the left of |, and another "invisible" extra pile with 0 grains in the imaginary place to the left of [b.sub.1] and to the right of |. However, the piles corresponding, respectively, to [a.sub.0] = 0, [a.sub.r + 1] = r, and [b.sub.0] = 0 must not be considered as parts of w.

2.1. Evolution Rules.

Rule 1. If w has a plus step at i + 1, then one grain must be added on the ith-plus pile

(6)

Rule 2. One grain must be deleted from the jth-minus pile if w has a minus step at j

(7)

We write w [[right arrow].sup.k]w' (or w' = w [[right arrow].sup.k]) to denote that w' is an n-tuple of integers obtained from w applying the Rule k, for k = l, 2. We also set

[nabla](w) = {w' : w [[right arrow].sup.k] w', k = 1, 2}. (8)

Theorem 2. If w [member of] P(n, r), then [nabla](w) = {w' e P(n, r) : w > w}.

Proof. We start to show that [nabla](w) [subset or equal to] {w' [member of] P(n, r) : w' [??] w}. Let w = [a.sub.r]... [a.sub.1] | [b.sub.1]... [b.sub.n - r] [member of] P(n, r) and [a.sub.r +1 ] = rbe the invisible pile in the place r + 1. We distinguish the two possible cases related to the previous rules.

Case 1. Let us assume that r [greater than or equal to] i [greater than or equal to] 1, [a.sub.i] [not equal to] 0, and that w has a plus step at i + 1. If w' = w [[right arrow].sup.1], then w' = [a.sub.r]... [a.sub.i + 1] ([a.sub.i] + l) [a.sub.i - 1]... [a.sub.1] |[b.sub.1]... [b.sub.n - r]. Since there is a plus step at i + 1, we have [a.sub.i + 1] - [a.sub.i] [greater than or equal to] 1; hence, [a.sub.i + 1] [greater than or equal to] [a.sub.i] + 1 > [a.sub.i] [greater than or equal to] [a.sub.i - 1], and this implies that w' [member of] P(n, r). We must show now that w' covers w in P(n, r).Since w and w' differ between them only in the place i for [a.sub.i] and [a.sub.i] + 1, respectively, it is clear that there does not exist an element z [member of] P(n, r) such that w [??] z [??] w'. Hence, w' [??] w.

Case 2. If 1 [less than or equal to] j [less than or equal to] n - r and w has a minus step at j, we apply Rule 2 to w on the minus pile [b.sub.j], and we obtain w' = w [[right arrow].sup.2], where w' = [a.sub.r]... [a.sub.1] | [b.sub.1]... [b.sub.j - 1] ([b.sub.j] + 1) [b.sub.j + 1]... [b.sub.n - r]. Since w has a minus step at j, we have -[b.sub.j] + [b.sub.j - 1] = [absolute value of [b.sub.j]] - [absolute value of [b.sub.j - 1]] [greater than or equal to] 1, and therefore, w' [member of] P(n, r) because 0 [greater than or equal to] [b.sub.j - 1] [greater than or equal to] [b.sub.j] + 1 > [b.sub.j] [greater than or equal to] [b.sub.j + 1].

As in the Case 1, we note that w' covers w in P(n, r) because they differ between them only for a grain in the place j.

We must show now that {w' [member of] P(n, r) : w' [??] w} [subset or equal to] [nabla](w). Let w = [a.sub.n]... [a.sub.1] and w' = [a'.sub.n]... [a'.sub.1] be two (n, r)-signed partitions in P(n, r). We prove at first that w' covers w if and only if there exists exactly a place k where w and w' are different and that [a'.sub.k]-[a.sub.k] = 1. In fact, if [a'.sub.k]-[a.sub.k] = 1 and [a'.sub.i] = [a.sub.i] if i [not equal to] k, it is immediate to see that w' covers w. In order to prove the other implication, we assume that w' covers w, and we proceed by contradiction. We must distinguish three cases.

Case A. w and w' are equal in all their parts. In this case, w = w', against the hypothesis.

Case B. There exist at least two places k and h, with h > k, where w and w' differ, with [l'.sub.k] > [l.sub.k] and [l'.sub.h] > [l.sub.h]. We consider the signed partition

u + [a'.sub.n]... [a'.sub.h + 1][a'.sub.h][a.sub.h - 1]... [a.sub.k + 1][a.sub.k][a.sub.k - 1]... [a.sub.1]. (9)

Then, r [greater than or equal to] [a'.sub.n] [greater than or equal to]... [greater than or equal to] [a'.sub.h + 1] [greater than or equal to] [a'.sub.h] [greater than or equal to] [a.sub.h] [greater than or equal to] [a.sub.h-1] [greater than or equal to]... [greater than or equal to] [a.sub.k + 1] [greater than or equal to] [a.sub.k] [greater than or equal to] [a.sub.k - 1] [greater than or equal to]... [greater than or equal to] [a.sub.1] [greater than or equal to] -(n - r); therefore, u [member of] P(n, r), and since w [??] u [??] w', this is against the hypothesis that w' covers w.

Case C. There exists exactly one place k where w and w' are different, but [a'.sub.k] - [a.sub.k] > 1. This implies that [a.sub.k] < [a.sub.k] + 1 < [l'.sub.k]. We consider now the signed partition

u = [a.sub.n]... [a.sub.k + 1] ([a.sub.k] + 1)[a.sub.k - 1]... [a.sub.1]. (10)

Let us observe then that w [??] u [??] w' and u [member of] P(n, r), and this is absurd because w' covers w.

Therefore, if w = [a.sub.r]... [a.sub.1] | [b.sub.1]... [b.sub.n - r] and w' = [a'.sub.r]... [a'.sub.1] | [b'.sub.1] [b'.sub.n - r] are two (n, r)-signed partitions such that w [??] w', the condition that w' covers w can occur just by one of the following possibilities:

(i) there exists exactly an index i [member of] {1,..., r}, with [a'.sub.i] = [a.sub.i] + 1, and so w' = w [[right arrow].sup.1],

(ii) there exits exactly an index j [member of] {1,..., n - r}, with [b'.sub.j] = [b.sub.j] + 1, and so w' = w [[right arrow].sup.2].

According to the definition of [nabla](w), the thesis follows.

Now let us study the sequential and the parallel dynamic of the model P(n, r). In such a context, we call configuration an element of P(n, r). The initial configuration is [??] = 0... 0 | (r - n)... (r - n). Each configuration converges, in sequential and in parallel, toward the unique fixed point [??] = r... r | 0... 0 because of the lattice structure of the model. Let us note that if w is a configuration, when we use the evolution rules in parallel, on each column of w, we can apply (due to the nature of Rules 1 and 2) at most one evolution rule; hence, our model is deterministic. Obviously, [T.sub.seq](w) is independent of the order in which the sites are updated because P(n, r) is a finite distributive and hence also a graded lattice. From the previous theorem, we can easily obtain the rank function of P(n, r).

Proposition 3. Let one denote by q the rank function of the graded lattice P(n, r).Then, [??](w) = [summation](w) - [summation]([??]) for each w [member of] P(n, r) and [T.sub.seq]([??]) = [r.sup.2] + [(n - r).sup.2].

Proof. Let w, w' [member of] P(n, r) such that w' [??] w. From the previous theorem, w' is obtained from w with an application of Rules 1 or 2. If we take then the function [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we obtain [??](w') = [??](w) + 1 and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Hence, [??] is exactly the rank function of P(n, r). The second part of the thesis is followed by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For the sake of completeness, we recall that in [36] we have computed the rank of the sublattice S(n, r) of all the signed partitions of P(n, r) having positive and negative parts all distinct between them.

We recall now the concept of involution poset. An involution poset (IP) is a poset (X, [less than or equal to], c) with a unary operation c: x [member of] X [right arrow] [x.sup.c] [member of] X, such that

(I1) [([x.sup.c]).sup.c] = x, for all x [member of] X,

(I2) if x, y [member of] X and if x [less than or equal to] y, then [y.sup.c] [less than or equal to] [x.sup.c].

The map c is called complementation of X and [x.sup.c] the complement of x. Let us observe that if X is an involution poset, by it follows that c is bijective, and by (I1) and (I2) it holds that if x, y [member of] X are such that x < y, then [y.sup.c] < [x.sup.c]. If (X, [less than or equal to], c) is an involution poset and if Z [subset or equal to] X, we will set [Z.sup.c] = {[z.sup.c] :z [member of] Z}. We note that if X is an involution poset, then X is a self-dual poset because from and (I2) it follows that if x, y [member of] X we have that x [less than or equal to] y, if and only if [y.sup.c] [less than or equal to] [x.sup.c], and this is equivalent to say that the complementation is an isomorphism between X and its dual poset [X.sup.*].

Now, if w = [a.sub.r]... [a.sub.1] | [b.sub.1]... [b.sub.n - r] [member of] P(n, r), we set [w.sup.c] = (r - [a.sub.1])... (r - [a.sub.r])|([absolute value of [b.sub.n - r]] - (n - r))... ([absolute value of [b.sub.1]]-(n - r)), and let us note that [w.sup.c] is still a signed partition in P(n, r); therefore, we can define a unary operation c : P(n, r) [right arrow] P(n, r) such that w [right arrow] [w.sup.c]. Then, it is immediate to verify that (P(n, r), [??], c) is an involution poset. If w = [a.sub.r]... [a.sub.1] | [b.sub.1]... [b.sub.n - r] [member of] P(n, r), we also set [w.sup.t] = (-[b.sub.n - r])... (-[b.sub.1]) | (-[a.sub.1])... (-[a.sub.r]), and we call [w.sup.t] the transposed of w. Let us note that [w.sup.t] [member of] P(n, n - r).

Proposition 4. We have:

(i) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(ii) P(n, r) [congruent to] P(n, n - r).

Proof. (i) It is sufficient to observe that P(n, r) can be identified with the set of all the ordered pairs ([z.sub.1], [z.sub.2]), where [z.sub.1] is a decreasing string of length r on the ordered alphabet r >... > 1 > 0 and [z.sub.2] is a decreasing string of length n - r on the ordered alphabet 0 > -1 >... > - (n - r); therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(ii) We define the map [phi]: P(n, r) [right arrow] P(n, n-r) such that [phi](w) = [([w.sup.t]).sup.c], for all w [member of] P(n, r). We prove then that [phi] is an isomorphism of posets. By part (i), it follows that [absolute value of P(n, r)] = [absolute value of P(n, n - r)]; therefore, [phi] is bijective since it is easily seen that it is injective. If w, w' [member of] P(n, r), the condition w [??] w' [left and right arrow] [phi](w) [??] [phi](w') follows at once from the conditions (I2) and because the transposed map w [right arrow] [w.sup.t] is order-reversing and such that [([w.sup.t]).sup.t] = w.

Theorem 5. The parallel rank [T.sub.par]([??]) in P(n, r) is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (11)

The fundamental sequence of P(n, r) is equal to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (12)

Proof. By Proposition 4 (ii), we can consider r [greater than or equal to] n - r. The initial configuration is [??] = 0... 0 | (n - r)... (n - r). Since our model is deterministic, we can consider separately the action of the Rules 1 and 2.Onthe nonnegative part, Rule 1 is applied as in the sequence

(1, 2,..., r, (r - 1),..., 1) (13)

of length 2r - 1 and similarly Rule 2 on the nonpositive part as in the sequence

(1, 2,..., (n - r), (n - r - 1),..., 1), (14)

of length 2(n - r) - 1. It follows that the parallel rank of P(n, r) is equal to the maximum of the length of the two sequences (13) and (14) and that the fundamental sequence is the sum of the two sequences. The other parts follow easily by replacing r with n-r and conversely.

3. The Submodel P(n, d, r) with Three Evolution Rules

In this section, we consider a submodel of P(n, r) which presents an evolution rule which permits us to move one single grain from the right part of a configuration into its left part. Let d be a positive integer such that d [less than or equal to] n. We define P(n, d, r) as the set of all the (n, r)-signed partitions we P(n, r) such that [parallel]w[parallel] = d. It is immediate to see that P(n, d, r) is a sublattice of P(n, r). The lattice P(n, d, r) is related to some extremal combinatorial sum problems studied in [32-35]. The interesting problem is to determine some evolution rules which describe such a lattice as a discrete dynamical model. We consider then the following rules.

3.1. Evolution Rules.

Rule [R.sub.1]. If the ith-plus pile has at least one grain, and if w has a plus step at i + 1, the none grain must be added on the ith-plus pile

(15)

Rule [R.sub.2]. If there are some minus singleton piles, then the first from the left of them must be shifted to the side of the lowest not empty plus pile

(16)

Rule [R.sub.3]. One grain must be deleted from the jth-minus pile if w has a minus step at j and [absolute value of [b.sub.j]] > 1

(17)

Remark 6. (i) In the previous rule, the lowest not empty plus pile can also be the invisible column in the place r + 1. In this case, all the plus piles are empty, and an eventual minus singleton pile must be shifted in the place r.

(ii) We take implicitly for intended that the shift of one minus singleton pile into a plus singleton pile can be made if the number of plus piles (excluding [a.sub.r + 1] = r) with atl east a grain is less than r (otherwise we obtain a configuration that does not belong to P(n, d, r)).

We write w [[right arrow].sup.k] w'(or w' = w [[right arrow].sup.k]) to denote that w' is an n-tuple of integers obtained from w applying Rule [R.sub.k], for k = 1, 2, 3. We also set

[nabla](w) = {w' : w [right arrow] w, k = 1, 2, 3}. (18)

Theorem 7. If w [member of] P(n, d, r), then [nabla](w) = {w' [member of] P(n, d, r) : w' [??] w}.

Proof. We start to show that [nabla](w) [subset or equal to] {w' [member of] P(n, d, r) : w' [??] w}. Let w = [a.sub.r]... [a.sub.1]|[b.sub.1]... [b.sub.n - r] [member of] P(n, d, r) and [a.sub.r + 1] = r be the invisible pile in the place r + 1. We distinguish the three possible cases related to the previous rules.

Case 1. Let us assume that r [greater than or equal to] i [greater than or equal to] 1, [a.sub.i] [not equal to] 0 and that w has a plus step at i + 1. If w' = w [right arrow] 1, then w' = [a.sub.r]...[a.sub.i + 1] ([a.sub.i] + l)[a.sub.i-1]...[a.sub.1] | [b.sub.1]...[b.sub.n-r]. It is clear that [parallel]w'[parallel] = d because [a.sub.i] [not equal to] 0. Since there is a plus step at i + 1, we have [a.sub.i + 1] - [a.sub.i] [greater than or equal to] 1; hence, [a.sub.i + 1] [greater than or equal to] [a.sub.i] + 1 > [a.sub.i] > [a.sub.i - 1], and this implies that w' [member of] P(n, d, r). We must show now that w' covers w in P(n, d, r). Since w and w' differ between them only in the place i for [a.sub.i] and [a.sub.i] + 1, respectively, it is clear that there does not exist an element z [member of] P(n, d, r) such that w [??] z [??] w'. Hence, w [??] w.

Case 2. Let us assume that in w there is a minus singleton pile [b.sub.j], for some 1 [less than or equal to] j [less than or equal to] n - r. Since [a.sub.r+1] = r > 0, we can assume that [a.sub.i+1] > 0, [a.sub.i] = 0, for some 1 [less than or equal to] i [less than or equal to] r. This means that w has the following form: w = [a.sub.r]...[a.sub.i + 1] 00...0| 0...0(-1) [b.sub.j + 1]...[b.sub.n - r]. Applying Rule [R.sub.2] to w, we obtain w' = w [right arrow] [sup.2], where w' =[a.sub.r]...[a.sub.i+1]10...0 | 0...00[b.sub.j + 1]...[b.sub.n - r]. It is clear then that w' [member of] P(n, r) and [parallel]w'[parallel] = d since w' is obtained from w with only a shift of the pile -1 to the left in the place i. Let us note that the only elements [z.sub.1], [z.sub.2] [member of] P(n, r) such that w [??] [z.sub.1] [??] w', and w [??] [z.sub.2] [??] w' are [z.sub.1] = [a.sub.r]...[a.sub.i + 1]10...0 | 0...0(-1)[b.sub.j + 1]...[b.sub.n-r] and [z.sub.2] = [a.sub.r]...[a.sub. i +1]00...0 | 0...00[b.sub.j + 1]...[b.sub.n - r], but [parallel][z.sub.1][parallel] = d + 1 and [parallel][z.sub.2][parallel] = d - 1, hence [z.sub.1], [z.sub.2] are not elements of P(n, d, r). This implies that w' covers w in P(n, d, r).

Case 3. If 1 [less than or equal to] j [less than or equal to] n - r and w has a minus step at j, we apply Rule [R.sub.3] to w on the minus pile [b.sub.j], and we obtain w' = w [right arrow] [sup.3], where w' = [a.sub.r]...[a.sub.1] | [b.sub.1]...[b.sub.j-1]([b.sub.j] + 1)[b.sub.j + 1]...[b.sub.n-r]. Since w has a minus step at j, we have -[b.sub.j] + [b.sub.j-1] = [absolute value of ([b.sub.j])] - [absolute value of ([b.sub.j - 1])] [greater than or equal to] 1, therefore w' [member of] P(n, r) because 0 [greater than or equal to] [b.sub.j-1] [greater than or equal to] [b.sub.j] + 1 > [b.sub.j] [greater than or equal to] [b.sub.j+1] and [parallel]w'[parallel] = d since [b.sub.j] [less than or equal to] -2 implies [b.sub.j] + 1 < 0. As in Case 1, we note that w' covers w in P(n, d, r) because they differ between them only for a grain in the place j. We now must show that {w' [member of] P(n, d, r) : w [??] w} [subset or equal to] [nabla](w). Let w" = [a".sub.r]...[a".sub.1]...[b".sub.n-r] be a generic element of P(n, d, r) such that w" [??] w. If we show that there exists an element w' = [a'.sub.r]...[a'.sub.i] | [b'.sub.1]...[b'.sub.n - r] of P(n, d, r) such that w' [member of] [nabla](w) and w" [??] w', we complete the proof of the theorem. Since w" [??] w, there is a place where the corresponding component of w" is an integer strictly bigger than the integer component of w corresponding to the same place. We distinguish several cases.

Case A. We assume that [a".sub.i] > [a.sub.i] and [a.sub.i + 1] [greater than or equal to] [a.sub.i] + 1 for some i [member of] {r - 1,...,1}. In this case, we can apply Rule [R.sub.1] in the place i to obtain w' = w [right arrow][sup.1] such that w" [??] w'.

Case B. We assume that [a".sub.i] > [a.sub.i] and [a.sub.i+1] = [a.sub.i] for some i [member of] {r - 1,..., 1}. In this case, we have [a".sub.i + 1] [greater than or equal to] [a".sub.i] > [a.sub.i] = [a.sub.i + 1], that is, [a".sub.i + 1] [greater than or equal to] [a.sub.i+1] + 1; therefore if [a.sub.i + 2] [greater than or equal to] [a.sub.i + 1] + 1, we can apply Rule [R.sub.1] in the place i + 1 to obtain w', otherwise we have [a.sub.i + 2] = [a.sub.i + 1] = [a.sub.i]. Iterating this procedure, to each step k [greater than or equal to] 1 we can apply Rule [R.sub.1] in the place i + k to obtain w' or it necessarily results that [a.sub.i + k] = ... = [a.sub.i+1] = [a.sub.i]. Hence, if for no one k we can apply Rule [R.sub.1] in the place i + k, we necessarily arrive to the condition [a.sub.r] = ... = [a.sub.i + 1] = [a.sub.i]. Since r [greater than or equal to] [a".sub.i] > [a.sub.i], it must be [a.sub.r] < r; therefore, we can apply Rule [R.sub.1] in the place r to obtain [a'.sub.r] = [a.sub.r] + 1, with [a".sub.r] > [a'.sub.r] because [a".sub.r] [greater than or equal to] ... [greater than or equal to] [a".sub.i] > [a.sub.i] = ... = [a.sub.r].

Case C. We assume that [a".sub.r] > [a.sub.r]. In this case, we can apply Rule [R.sub.1] in the place r.

Case D. We assume that 0 > [b".sub.j] > [b.sub.j], for some j [member of] {1,..., n - r}. In this case, we can apply Rule [R.sub.3] in the place j.

Case E. We assume that 0 = [b".sub.j] > [b.sub.j] and [b.sub.j] [less than or equal to] - 2, for some j [member of] {1,..., n - r}. Also in this case, we can apply Rule [R.sub.3] in the place j.

Case F. We assume that 0 = [b".sub.j] > [b.sub.j] = -1, for some j [member of] {1,..., n - r}. In this case, the number of negative parts of w" is strictly lower than the number of negative parts of w, and since [parallel]w[parallel] = [parallel]w"[parallel] = d, it follows that there exists at least one index i [member of] {1,..., r} such that [a".sub.i] > 0 and [a.sub.i] = 0. We choose then such index i maximal, so that we have i = r or i [less than or equal to] r - 1 and [a.sub.i + 1] > 0.

We suppose at first that i = r. In this case, we have [a".sub.r] [greater than or equal to] 1 and 0 = [a.sub.r] = ... = [a.sub.1]; therefore, we can apply Rule [R.sub.2] to move the "negative" grain from the place j into the place r, so that the (n, r)-partition w' = l00...0 | 0...0[b.sub.j + 1]...[sub.n - r] is such that [parallel]w'[parallel] = d and w" [??] w'.

If i [less than or equal to] r - 1 and [a.sub.i + 1] > 0, we apply again Rule [R.sub.2] to move the "negative" grain from the place j into the place i, so that the (n, r)-partition w' = [a.sub.r]...[a.sub.i + 1]1...0 | 0...0[b.sub.j + 1]...[sub.n-r] is such that [parallel]w'[parallel] = d and w" [??] w'.

An analogous statement of the previous theorem was proven in [36] for the sublattice of all the signed integer partitions of P(n, d, r) having positive and negative parts all distinct between them. Below, we draw the Hasse diagram of the lattice P(4, 3, 2) by using the evolution Rules [R.sub.1], [R.sub.2] and [R.sub.3] starting from the minimum element of this lattice, which is l0 | 22. We label a generic edge of the next diagram with the symbol k if it leads to a production that uses the Rule [R.sub.k], for k [member of]{1, 2, 3}

(19)

4. Sequential and Parallel Dynamics in P(n, d, r)

In this section, we study the parallel dynamic of the model P(n, d, r). In such a context, we call configuration a generic element of P(n, d, r). The initial configuration is [??]. Each configuration converges, in sequential and in parallel, toward the unique fixed point [??] because of the lattice structure of the model. Let us note that if w is a configuration, when we use the evolution rules in parallel, on each column of w we can apply (due to the nature of the Rules [R.sub.1], [R.sub.2], and [R.sub.3]) at most one evolution rule, hence our model is deterministic. We denote by [T.sub.seq](w) and [T.sub.par](w) the number of time steps required to reach [??]. starting from the configuration abusing, respectively the sequential or the parallel updating scheme. Obviously [T.sub.seq](w) is independent of the order in which the sites are updated because P(n, d, r) is a finite distributive, and hence also a graded lattice (let us note that P(n, d, r) is distributive because it is a sublattice of the distributive lattice P(n, r). In the next proposition, we determine the rank function of P(n, d, r).

Proposition 8. The map [rho] : P(n, d, r) [right arrow] N such that [rho](w) = [summation](w) - [summation]([??]) - ([[absolute value of w].sub.>] - [[absolute value of [??]].sub.>]) is the rank function of P(n, d, r).

Proof. We denote by [??] the rank function of the graded lattice P(n, r). If w and w' are two (n, r)-signed partitions and w [??] w', then [summation](w) = [summation](w') + 1. It follows that [??](w) = [summation](w) [summation]([??]), for each w [member of] P(n, r). Let now w [??] [w.sub.t] [??]... [??] [w.sub.1] [??] [??] be any saturated chain from 0 to w in the lattice P(n, d, r). Let us assume that in this chain w is obtained from [??] with k applications of [R.sub.2], for some integer k [greater than or equal to] 0. To each step l [member of] {1,..., t} where we apply [R.sub.2], there is the following situation: [w.sub.l] [??] [u.sub.l] [??] [w.sub.l - 1], for one only element [u.sub.l] [member of] P(n, r)\P(n, d, r). This means that [??](w) = (t + l) + k, that is, [rho](w) = t + l = [??](u>) - k. The integer k is also the difference between the number of positive parts of w and the number of positive parts of [??]. Hence, the thesis follows.

By using the rank function, we can compute the sequential convergence time of any element w e P(n, d, r) as in the following:

[T.sub.seq](w) = p([??]) - [rho](w). (20)

In particular, if we denote by rank(P(n, d, r)) the rank of the lattice P(n, d, r), then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In the next proposition, we compute this number.

Proposition 9. the following result holds:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (21)

Proof. The minimal and maximal elements in P(n, d, r) are, respectively,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (22)

Then,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (23)

while the number of positive parts in [??] and [??] is, respectively,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (24)

The thesis follows then from simple arithmetic calculations and from Proposition 8, because rank (P(n, d, r)) = [rho]([??]).

The next theorem is the main result of this section. Here we determine the parallel rank of the lattice P(n, d, r), for all the values of n, d, and r. In the proof of the next theorem, we also determine the fundamental sequence of P(n, d, r) in almost all the values of n, d, and r. We do not provide the construction of the fundamental sequence for all the parameters n, d, and r because several cases have similar constructions. However, for completeness, in Tables 1 and 2 we provide a complete description of the parallel rank value and of the fundamental sequence for all the values n, d, and r.

Theorem 10.

(I) If d [less than or equal to] min{r, n - r}, [T.sub.par]([??]) = n + d - 2.

(II) If r [greater than or equal to] d [greater than or equal to] 2(n - r), [T.sub.par](0) = d + r - 2.

(III) If r [greater than or equal to] d [greater than or equal to] n - r and 2(n - r) [greater than or equal to] d [greater than or equal to] n - r, [T.sub.par] ([??]) = 2n - r - 2.

(IV) If n - r [greater than or equal to] d [greater than or equal to] 2r, [T.sub.par](0) = d + n - r - 2.

(V) If n - r [greater than or equal to] d [greater than or equal to] r and 2r [greater than or equal to] d [greater than or equal to] r, [T.sub.par](0) = n + r - 2.

(VI) If min{2r, 2(n - r)} [greater than or equal to] d [greater than or equal to] max{r, n - r}, [T.sub.par]([??]) = 2n - d - 2.

(VII) If 2r > d [greater than or equal to] 2(n - r) and d [greater than or equal to] max{r, n - r}, [T.sub.par]([??]) = 2r - 2.

(VIII) If 2(n - r) > d [greater than or equal to] 2r and d [greater than or equal to] max{r, n - r}, [T.sub.par]([??]) = 2(n - r) - 2.

(VIII.3) If d > 2n - 3r + 1 and 2d - 1 > 3(n - r), the fundamental sequence is

Proof. In all cases, let us denote the sequence of configurations as in (1).

Case I (d [less than or equal to] min{r, n - r}). If d [less than or equal to] min{r, n - r}, then [??] = 0...0 | 0...0 (n - r)...(n - r) and 1 = r...r 0...0 | 0...0.

Therefore,

[??] = i <(0, 0, 1), (0, 0, 2),...,(0, 0, d - 1)) 0...0 > 0...0 (n - r - d + 1)...(n - r) := [w.sub.1].

Starting from [w.sub.1], we obtain

[w.sub.1] [??] {(0, 0, d), (0, 0, d),..., (0, 0, d))0...0| 0...0 1...d := [w.sub.2], (26)

where (0, 0, d) is repeated n-r-d times. The next steps are

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (27)

where (d, 0, 0) is repeated r-d times. Finally, we have

[w.sub.4] [??] <(d - 1, 0, 0), (d-2, 0, 0)..., (2, 0, 0), (l, 0, 0)> r...r 0...0|0...0 = T. (28)

From the previous computations, it follows that the fundamental sequence of P(n, d, r) is

(1, 2,..., d - 1, d,..., d, d - 1,..., 1), (29)

where the integer d is repeated exactly n - d times; hence, [T.sub.par]([??]) = n + d - 2. Let us note that the sequence (29) is unimodal and symmetric.

Case II (r [greater than or equal to] d [greater than or equal to] 2(n - r)). In this case, [??] = 1...l 0...0 | (n - r) ... (n - r) and [??] = r...r 0...0 | 0...0. Since d [greater than or equal to] 2(n - r), we have d - n + r [greater than or equal to] n - r therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (30)

with [w.sub.1] := (n - r) (n - r - 1)... 1 1...1 0...0 | 1 2...(n - r), where 1 is repeated exactly d - 2n + 2r + 1 times. Since r [greater than or equal to] 2(n - r), by starting from [w.sub.1] we obtain

[w.sub.1] [??] {(n - r, 1, n - r - 1), (n - r + 1, 1, n - r - 2) (2n - 2r - 1, 1, 0))[w.sub.2], (31)

with [w.sub.2] := (2n - 2r) (2n - 2r - 1)...1 1...l 0...0 | 0...0, where 1 is repeated exactly d - 2n + 2r + 1 times.

Now, from [w.sub.2] we have

[w.sub.2] [??] <(2n - 2r, 0,0), (2n - 2r - l, 0, 0),...,(d - l, 0, 0)> d(d - 1)...l 0...0 | 0...0 := [w.sub.3]. (32)

At this point we obtain

[w.sub.2] [??] <(d, 0, 0),...,(d, 0, 0)>r (r - 1)...(r - d + 1) 0...0|0...0 := [w.sub.4], (33)

where (d, 0, 0) is repeated r - d times. Finally, we have

[w.sub.4] [??] <(d - 1, 0, 0),(d-2, 0, 0)..., (2, 0, 0), (1, 0, 0)> r...r 0...0|0...0 = 1. (34)

Thus, the parallel rank [T.sub.par](0) is equal to d + r - 2, and the fundamental sequence of P(n, d, r) is

(2, 4,..., 2(n - r - 1), 2(n - r),..., 2(n - r), 2(n - r) + 1,..., d - 1, d,..., d, d - 1,...1), (35)

and so P(n, d, r) in this case is parallel unimodal but not parallel symmetric.

In a similar way, we can compute in all other cases the parallel rank and the fundamental sequence. The details are left to the interested reader. Here are the results.

Case III (r [greater than or equal to] d [greater than or equal to] n - r and 2(n - r) [greater than or equal to] d [greater than or equal to] n - r). In this case, [T.sub.par](0) = 2n - r - 2, and the fundamental sequence is

(2, 4,..., 2(d - n + r - 1), 2(d - n + r), 2(d - n + r) + 1,..., d - 1, d,..., d, d - 1,...,1). (36)

It is unimodal and not symmetric.

Case IV (n - r [greater than or equal to] d [greater than or equal to] 2r). In this case, [T.sub.par]([??]) = d + n - r - 2 and the fundamental sequence is

(1, 2,..., d - 1, d,..., d, d - 1,..., d - 2r, d - 2r - 1,..., 1). (37)

It is unimodal, and if r = 0, it is not symmetric.

Case V (n - r [greater than or equal to] d [greater than or equal to] r and 2r [greater than or equal to] d [greater than or equal to] r). In this case, [T.sub.par](0) = n + r - 2. The fundamental sequence is

(1, 2,..., d - 1, d,..., d, d - 2,..., 2r - d, 2r - d - 1,..., 1). (38)

It is unimodal, and if d [not equal to] r, it is not symmetric.

Case VI (min{2r, 2(n - r)} [greater than or equal to] d [greater than or equal to] max{r, n - r}). In this case, [T.sub.par]([??]) = 2n - d - 2. The fundamental sequence depends on the relations between r, n - r, and d in the following way.

(VI.1) If r [greater than or equal to] n - r and 2d - 1 [less than or equal to] 3(n - r), the fundamental sequence is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (39)

(VI.2) If r [greater than or equal to] n - r, 2d - 1 > 3(n - r), and d [less than or equal to] 3(n - r) - r + 1, the fundamental sequence is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (40)

(VI.3) If r [greater than or equal to] n - r, 2d - 1 > 3(n - r) and d > 3(n - r) - r + 1, the fundamental sequence is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (41)

(VI.4) If r [less than or equal to] n - r and d [less than or equal to] 2n - 3r + 1, the fundamental sequence is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (42)

(VI.5) If r [less than or equal to] n - r, d > 2n - 3r + 1, and 2d - 1 [less than or equal to] 3(n - r), the fundamental sequence is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (43)

(VI.6) If r [less than or equal to] n - r, d > 2n - 3r + 1, and 2d - 1 > 3(n - r), the fundamental sequence is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (44)

In those cases P(n, d, r) is parallel unimodal but not parallel symmetric.

Case VII (2r > d [greater than or equal to] 2(n - r) and d [greater than or equal to] max{r, n - r}). In this case, the parallel rank is [T.sub.par]([??]) = 2n - d - 2. The fundamental sequence depends on the relations between r, n - r, and d in the following way.

(VII.1) If 3r [less than or equal to] 2(n - r), the fundamental sequence is

(2, 4,..., 2(n - r),..., 2(n - r), 2(n - r) - 1,..., 2(n - r) - 1, 2(n - r) -2, 2(n - r) -4,..., 4r - 2n, 4r - 2n - 1,...,1). (45)

In this case P(n, d, r) is parallel unimodal but not parallel symmetric.

(VII.2) If 3r > 2(n - r), the fundamental sequence is

(2, 4,..., 2(n - r),..., 2(n - r), 2(n - r)- 1,..., 2(n - r) -1, 2(n - r), 2(n - r) + 1,..., r - 1, r - 1,...,1). (46)

Therefore, in this case, P(n, d, r), it is not parallel unimodal and it is not parallel symmetric. This is the only case in which the fundamental sequence is not unimodal (see Example 11).

Case VIII (2(n - r) > d [greater than or equal to] 2r and d [greater than or equal to] max{r, n - r}). In this case, the parallel rank is [T.sub.par](0) = 2n - d - 2. The fundamental sequence depends on the relations between r, n - r, and d in the following way.

(VIII.1) If d [less than or equal to] 2n - 3r + 1, the fundamental sequence is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (47)

(VIII.2) If d > 2n - 3r + 1 and 2d - 1 [greater than or equal to] 3(n - r), the fundamental sequence is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (48)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (49)

In these cases P(n, d, r) is parallel unimodal but not parallel symmetric.

We summarize all the previous results in Tables 1 and 2.

Example 11. Let us consider the lattice P(n, d, r) with n = 7, d = 6, and r = 5. In this case, 2r > d [greater than or equal to] 2(n - r), d [greater than or equal to] max{r, n - r}, and 3r > 2(n - r).The fundamental chain is the following:

(50)

5. Conclusions and Future Research Directions

In this work, we have introduced a refinement of the concept of parallel time convergence for a finite deterministic discrete dynamical model X which also has a lattice structure. This new concept is the fundamental sequence of X. In particular, the length of the fundamental sequence is exactly the parallel time of convergence from the minimum to the maximum of X. In this paper, we have computed the fundamental sequence for two models whose configurations are signed integer partitions. The perspectives, for future research directions, are the following: to compute the fundamental sequence formore general models, to compare the properties of the fundamental sequence with the properties of other relevant combinatorial objects related to the order structure of X (e.g., the Whitney number sequence and the rank of X when X is graded), and to characterize the models whose fundamental sequence has some specific property (e.g., unimodality or symmetry).

http://dx.doi.org/ 10.1155/2013/292143

References

[1] E. Goles, M. Latapy, C. Magnien, M. Morvan, and H. D. Phan, "Sandpile models and lattices: a comprehensive survey," Theoretical Computer Science, vol. 322, no. 2, pp. 383-407, 2004.

[2] T. Brylawski, "The lattice of integer partitions," Discrete Mathematics, vol. 6, pp. 201-219, 1973.

[3] E. Goles, "Sand pile automata," Annales de l'Institut Henri PoincareA, vol. 56, no. 1, pp. 75-90, 1992.

[4] E. Goles and M. A. Kiwi, "Games on line graphs and sand piles," Theoretical Computer Science, vol. 115, no. 2, pp. 321-349, 1993.

[5] P. Bak, C. Tang, and K. Wiesenfeld, "Self-organized criticality," Physical Review A, vol. 38, no. 1, pp. 364-374, 1988.

[6] D. Dhar, "The abelian sandpiles and related models," Physica A, vol. 263, no. 1-4, pp. 4-25, 1999.

[7] E. Goles and M. Margenstern, "Universality of the chip-firing game," Theoretical Computer Science, vol. 172, no. 1-2, pp. 121-134, 1997.

[8] E. Goles, M. Morvan, and H. D. Phan, "Lattice structure and convergence of a game of cards," Annals of Combinatorics, vol. 6, no. 3-4, pp. 327-335, 2002.

[9] G. Cattaneo, M. Comito, and D. Bianucci, "Sand piles: from physics to cellular automata models," Theoretical Computer Science, vol. 436, pp. 35-53, 2012.

[10] A. Dennunzio, P. Guillon, and B. Masson, "Sand automata as cellular automata," Theoretical Computer Science, vol. 410, no. 38-40, pp. 3962-3974, 2009.

[11] E. Goles and M. A. Kiwi, "One-dimensional sand piles, cellular automata and related models," in Nonlinear Phenomena in Fluids, Solids and Other Complex Systems (Santiago, 1990), North-Holland Delta Series, pp. 169-185, North Holland, Amsterdam, The Netherlands, 1991.

[12] J. Cervelle and E. Formenti, "On sand automata," in Mathematical Foundations of Computer Science 2003, vol. 2607 of Lecture Notes in Computer Science, pp. 642-653, Springer, Berlin, Germany, 2003.

[13] J. Cervelle, E. Formenti, and B. Masson, "Basic properties for sand automata," in Mathematical Foundations of Computer Science 2005, vol. 3618 of Lecture Notes in Computer Science, pp. 192-211, Springer, Berlin, Germany, 2005.

[14] J. Cervelle, E. Formenti, and B. Masson, "Froms and pilesto sand automata," Theoretical Computer Science, vol. 381, no. 1-3, pp. 128, 2007.

[15] E. Formenti and B. Masson, "On computing the fixed points for generalized sandpiles," International Journal of Unconventional Computing, vol. 2, no. 1, pp. 13-25, 2005.

[16] E. Formenti and B. Masson, "A note on fixed points of generalized ice piles models," International Journal of Unconventional Computing, vol. 2, no. 2, pp. 183-191, 2006.

[17] E. Formenti, B. Masson, and T. Pisokas, "On symmetric sandpiles," in Cellular Automata, vol.4173 of Lecture Notes in Computer Science, pp. 676-685, Springer, Berlin, Germany, 2006.

[18] E. Formenti, B. Masson, and T. Pisokas, "Advances in symmetric sandpiles," Fundamenta Informaticae, vol. 76, no. 1-2, pp. 91-112, 2007.

[19] E. Goles, M. Morvan, and H. D. Phan, "Sandpiles and order structure of integer partitions," Discrete Applied Mathematics, vol. 117, no. 1-3, pp. 51-64, 2002.

[20] M. H. Le and T. H. D. Phan, "Strict partitions and discrete dynamical systems," Theoretical Computer Science, vol. 389, no. 1-2, pp. 82-90, 2007.

[21] M. Latapy, "Partitions of an integer into powers," in Discrete Models: Combinatorics, Computation, and Geometry (Paris, 2001), Discrete Mathematics and Theoretical Computer Science, pp. 215-228, 2001.

[22] M. Latapy, "Integer partitions, tilings of 2D-gons and lattices," RAIRO-Theoretical Informatics and Applications, vol. 36, no. 4, pp. 389-399, 2002.

[23] M. Latapy, R. Mantaci, M. Morvan, and H. D. Phan, "Structure of some sand piles model," Theoretical Computer Science, vol. 262, no. 1-2, pp. 525-556, 2001.

[24] M. Latapy and H. D. Phan, "The lattice structure of chip firing games and related models," Physica D, vol. 155, no. 1-2, pp. 69-82, 2001.

[25] M. Latapy and T. H. D. Phan, "The lattice of integer partitions and its infinite extension," Discrete Mathematics, vol. 309, no. 6, pp. 1357-1367, 2009.

[26] K. Perrot and E. Remila, "Transduction on Kadanoff sand pile model avalanches, application to wave pattern emergence," in Mathematical Foundations of Computer Science 2011, vol. 6907 of Lecture Notes in Comput. Sci., pp. 508-519, Springer, Heidelberg, Germany, 2011.

[27] K. Perrot, T. H. D. Phan, andT. van Pham, "On the set of fixed points of the parallel symmetric sand pile model," in Automata 2011-17th International Workshop on Cellular Automata and Discrete Complex Systems, Discrete Mathematics and Theoretical Computer Science, pp. 17-28, Discrete Mathematics and Theoretical Computer Science Proceedings, 2011.

[28] T. H. D. Phan, "Two sided sand piles model and unimodal sequences," RAIRO-Theoretical Informatics and Applications, vol. 42, no. 3, pp. 631-646, 2008.

[29] P. T. H. Duong and T. T. T. Huong, "On the stability of sand piles model," Theoretical Computer Science, vol. 411, no. 3, pp. 594-601, 2010.

[30] G. E. Andrews, "Euler's 'de Partitio numerorum'," Bulletin of the American Mathematical Society, vol. 44, no. 4, pp. 561-573, 2007.

[31] W. J. Keith, "A bijective toolkit for signed partitions," Annals of Combinatorics, vol. 15, no. 1, pp. 95-117, 2011.

[32] G. Chiaselotti, "On a problem concerning the weight functions," European Journal of Combinatorics, vol. 23, no. 1, pp. 15-22, 2002.

[33] G. Chiaselotti, G. Infante, and G. Marino, "New results related to a conjecture of Manickam and Singhi," European Journal of Combinatorics, vol. 29, no. 2, pp. 361-368, 2008.

[34] G. Chiaselotti, G. Marino, and C. Nardi, "A minimum problem for finite sets of real numbers with nonnegative sum," Journal of Applied Mathematics, vol. 2012, Article ID 847958, 15 pages, 2012.

[35] G. Marino and G. Chiaselotti, "A method to count the positive 3-subsets in a set of real numbers with non-negative sum," European Journal of Combinatorics, vol. 23, no. 5, pp. 619-629, 2002.

[36] C. Bisi, G. Chiaselotti, and P. A. Oliverio, "Sand piles models of signed partitions with d piles," ISRN Combinatorics, vol. 2013, Article ID 615703, 7 pages, 2013.

G. Chiaselotti, T. Gentile, G.Marino, and P. A. Oliverio

Dipartimento di Matematica, Universita della Calabria, Via Pietro Bucci, 87036 Arcavacata di Rende, Italy

Correspondence should be addressed to G. Marino; gmarino@unical.it

Received 4 December 2012; Accepted 24 January 2013

Academic Editor: Filomena Cianciaruso

TABLE 1: Parallel rank in P(n, d, r).

Case         Relation between n, d, and r         Parallel rank
                                                 [T.sub.par]([??])

I      d [less than or equal to] min{r, n - r}        n + d-2
II     r [greater than or equal to] d [greater        d + r-2
             than or equal to] 2(n - r)
III    r [greater than or equal to] d [greater        2n - r - 2
        than or equal to] n - r and 2(n - r)
        [greater than or equal to] d [greater
               than or equal to] n - r
IV       n - r [greater than or equal to] d           d + n - r -2
            [greater than or equal to] 2r
V        n - r [greater than or equal to] d          n + r - 2
         [greater than or equal to] r and 2r
            [greater than or equal to] d
            [greater than or equal to] r
VI       min{2r, 2(n - r)} [greater than or          2n - d - 2
         equal to] d [greater than or equal
                  to] max{r, n - r}
VII       2r > d [greater than or equal to]            2r - 2
           2(n - r) and d [greater than or
               equal to] max{r, n - r}
VIII     2(n - r) > d [greater than or equal        2(n - r) - 2
         to] 2r and d [greater than or equal
                  to] max{r, n - r}

TABLE 2: Fundamental sequence in P(n, d, r).

Case           Fundamental sequence

Case I         (1,2,...,d - 1,d,d,...,d,d - 1,...1)
Case II          (2,4,...,2(n -r -1),2(n -r),...,2
                 (n - r),2(n -r) + 1,...,d -1,d,...,d,
                 d - 1,...1)
Case III       (2,4,...,2(d - n + r - 1),2(d - n +
                 r),2(d - n + r) + 1,...,d - 1,d,...,d,
                 d - 1,...,1)
Case IV        (1,2,...,d - 1,d,...,d,d - 2,...,
                 d - 2r,d - 2r - 1,...,1)
Case V         (1,2,...,d - 1,d,...,d,d - 2,...,2r -d,
                 2r - d - 1,...,1)
Case VI.1      (2,4,...,2(d - n + r),2(d - n + r) +
                 1,...,d,...,d,d - 1,...,n - r, ...,n -r,
                 n - r - 1, ...,n - d,...,n - d,
                 n - d - 1,...,1)
Case VI.2      (2,4,...,2(d - n + r),2(d - n + r) +
                 1,...,d,...,d,d - 1,...,2(d - n + r),
                 2(d - n + r - 1),... ...,4n - 4r - 2d,
                 4n - 4r - 2d - 1,...,n - d, ...,n - d,
                 n - d - 1,...,1)
Case VI.3      (2,4,...,2(d - n + r),2(d - n + r) +
                 1,...,d,...,d,d - 1,...,2(d - n + r),
                 2(d - n + r) - 1, 2(d - n + r) - 3,...,
                 4r - 2n - 1,4r - 2n - 2,...,n - d,...,
                 n - d,n - d - 1,...,1)
Case VI.4      (2,4,...,2(d - n + r),2(d - n + r) +
                 1,...,d - n + 2r - 1,...,d - n +
                 2r - 1,d - n + 2r,...,n - r,... ...,
                 n - r,n - r - 1,...,2n - d - 2r,
                 2n - d - 2r - 2,...,2r - d,
                 2r - d - 1,...,1)
Case VI.5      (2,4,...,2(d - n + r),2(d - n + r) +
                 1,...,d - n + 2r - 1,...,d - n + 2r - 1,
                 d - n + 2r - 2,... ... ,n - r,...,
                 n - r,n - r - 1,... ,2n - d - 2r,
                 2n - d - 2r - 2,... ,2r - d,
                 2r - d - 1,...,1)
Case VI.6      (2,4,...,2(d - n + r),2(d - n + r) +
                 1,...,d - n + 2r - 1,...,d - n + 2r - 1,
                 d - n + 2r - 2,... ... ,n - r,... ,n - r,
                 n - r - 1,... ,2n - d - 2r,
                 2n - d - 2r - 2,...,2r - d,
                 2r - d - 1,...,1)
Case VII.1     (2,4,...,2(n - r),...,2(n - r),
                 2(n - r) - 1,...,2(n - r) - 1, 2(n - r) - 2,
                 2(n - r) - 4,... ,4r - 2n, 4r - 2n - 1,...,1)
Case VII.2     (2,4,...,2(n - r),...,2(n - r),
                 2(n - r) - 1,...,2(n - r) - 1, 2(n - r),
                 2(n - r) + 1,...,r - 1, r - 1,...,1)
Case VIII.1    (2,4,...,2(d - n + r),2(d - n + r) +
                 1,...,d - n + 2r - 1,...,d - n + 2r - 1,
                 d - n + 2r,...,n - r, ...,n - r,
                 n - r - 1,...,2n - 2r - d,2n - 2r - d - 2...,
                 d - 2r,d - 2r - 1,...,1)
Case VIII.2    (2,4,,...,2(d - n + r),2(d - n + r) +
                 1,...,d - n + 2r - 1,...,d - n +
                 2r - 1,d - n + 2r - 2, ...,2{d - n + r),
                 2{d - n + r - 1),...,2(2n - 2r - d),
                 2(2n - 2r - d) - 1, ...,2n - 2r - d,
                 2n - 2r - d - 2...,d - 2r,d - 2r - 1,...,1)
Case VIII.3    (2,4,,...,2(d - n + r),2(d - n + r) +
                 1,...,d - n + 2r - 1,...,d - n +
                 2r - 1,d - n + 2r - 2, ...,n - r + 1,
                 n - r,...,n - r,n - r - 1, ...,2n - 2r - d,
                 2n - 2r - d - 2...,d - 2r,d - 2r - 1,...,1)
COPYRIGHT 2013 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Chiaselotti, G.; Gentile, T.; Marino, G.; Oliverio, P.A.
Publication:Journal of Applied Mathematics
Article Type:Report
Date:Jan 1, 2013
Words:11517
Previous Article:Efficient algorithms for optimal 4-bit reversible logic system synthesis.
Next Article:Computationally improved optimal control methodology for linear programming problems of flexible manufacturing systems.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters