MODERATE GROWTH TIME SERIES FOR

DYNAMIC COMBINATORICS MODELISATION

Luaï JAFF, Gérard H.E. DUCHAMP, LIPN, Paris XIII University 99, avenue Jean-Baptiste Clément 93430 Villetaneuse, France

                          luai.jaff@gmail.com, gheduchamp@gmail.com

Hatem HADJ KACEM, MIRACL, Sfax University Route de l’Arodrome - BP 559 3029 Sfax, Tunisia

                                hatem.hadjkacem@fsegs.rnu.tn

Cyrille BERTELLE, LITIS, Le Havre University 25 rue Ph. Lebon - BP 540 76058 Le Havre Cedex, France

                              cyrille.bertelle@univ-lehavre.fr

Abstract

Here, we present a family of time series with a simple growth constraint. This family can be the basis of a model to apply to emerging computation in business and micro-economy where global functions can be expressed from local rules. We explicit a double statistics on these series which allows to establish a one-to-one correspondence between three other ballot-like strunctures.

Keywords: Time series; Complex system; Growth constraint; local rules; Dyck words; Permutations; Codes.

1 Introduction

In this paper, we are interested with time series with moderate growth but possibly sudden decay. We will focus ourselves on a very simple model (a “toy model” as physicists may say), the combinatorics of which is completely mastered. This feature is important as one may use simulations and estimates over “all the possible configurations”, as it is the case, for example, for other combinatorial models (Cox-Ross-Rubinstein, for instance). The model is that of sequences with integer values and growth bounded by a unit (local rule). Surprisingly, there is one-to-one correspondences between the possible configurations and planar combinatorial objects which are endowed with a special dynamics which we describe here. The structure of the paper is the following. Section 2 presents an applicative economic problem which leads to generate the studied growth time series from local rules. On section 3, we propose a non exhaustive review concerning emerging computation in economic domain and how our work relates corresponding of this body of knowledge. Section 4 develops the dynamic combinatorics computation which leads to establish one-to-one correspondences between three other ballot-like structures. We conclude on section 5.

2 From Micro-Economy Local Rules To Dynamic Combinatorics

Our aim is to describe here a toy-model of the benefit in the following situation. A capital owner possesses two accounts, say P and R, P is the account where the principal (untouched) capital is deposited. This capital produces a constant return (one unit per unit of time) which is sent to a reserve R. From the account R can be with drawn arbitrary amounts of money and the account must stay positive. The possible configurations are described the sequences such that

• a_{1} = 0

• a_{i+1} ≤ a_{i} + 1

[figure: R; t; •; •; •; •; •; •; •; •; •; •; •; •; 012345678; •; •; •; •; •; •; •; •; •; 000000000; 011123012; 012012343; 0; 1; 2; 3; 4; 5; 6; 7; 8]

Figure 1: Maximal, minimal (dotted) and two intermediate trajectories. Their codes are on the right.

In this paper, we build combinatorial structures that allow to modelize and to compute the global behavior of the reserve R by some specific functions. We can consider this result as an emergent function from the basic local rules.

3 Emerging Computations

Emerging computation is nowadays a thrilling topic which concerns many developments in complex systems modeling. A brief review can allow to classify these emerging computations concerning economic domains in 3 spaces.

The first space is composed of emerging computations which lead to some universal laws. Per Bak’s sand pile is concerned by this class (6). In such model called Self-Organized Criticality, the phenomenon is crossed by transformation which make it evolve by avalanche. The Coton market trade follows such a law. For 1000 small price variations, there are only 100 middle price variations and only 10 major price variations. The general law which characterize such criticality phenomena is an exponential law.

The second space of emerging computation leads to some pattern formations without a complete knowledge of any law. Thomas Schelling’s segregation model for urban development is concerned by this class (7). In such model some local interaction between neighbours can lead to self-organized patterns which emerge from the whole interaction systems. Some areas become specialized to some people categories while other areas are devoted to others ones.

The third space of emerging computation described here, leads to some global functions expressions. It is typically what we will describe in our problem. The local rules concerned by the proposed economic toy-model will lead to define combinatorics structures allowing to compute a functional global approach. The detailed computation is describe in the following

4 Dynamics Combinatorics Computation

4.1 Trajectories and Codes

We can define the trajectories of our model by sequences (codes) a_{1}a_{2}a_{3}...a_{n} such that

• a_{1} = 1

• a_{j+1} ≤ a_{j} + 1

Example : For n = 4, we have 14 codes as described in the following table.

numbers codes
1  1111
2  1112
3  1121
4  1122
5  1123
6  1211
7  1212
8  1221
9  1222
10  1223
11  1231
12  1232
13  1233
14  1234

We remark that we have 5 codes which end by 1 or 2, 3 codes ending by 3 and one code ending by 4. Now if one sets l(n, k) to be the number of codes ending by k − 1, one can check that

• l(n, 0) = l(0, n) = 0 (∀n ≥ 1)

• l(0, 0) = 1 (the void sequence)

• l(n, k) = ∑_{j≥k+1} l(n − 1, j)

whence the easy computed table of the first values

\begin{matrix}n\ k & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 2 & 2 & 1 & 0 & 0 & 0 & 0 \\ 4 & 0 & 5 & 5 & 3 & 1 & 0 & 0 & 0 \\ 5 & 0 & 14 & 14 & 9 & 4 & 1 & 0 & 0 \\ 6 & 0 & 42 & 42 & 28 & 14 & 5 & 1 & 0 \\ 7 & 0 & 132 & 132 & 90 & 48 & 20 & 6 & 1 \end{matrix}

The values for n, k ≥ 1 can be even more easily computed with the (subdiagonal) local rule described by West + North = result. For instance, we remark that 9 + 5 = 14.

1 0 0 0 0 0 0
1 1 0 0 0 0 0
1 2 2 0 0 0 0
1 3 5 5 0 0 0
1 4 9 14 14 0 0
1 5 14 28 42 42 0

Remark that the preceding table gives the mirror images of the lines of the previous double statistics.

4.2 Permutations

We say that a permutation π of n letters has an increasing subsequences of length k if there are positions

1 ≤ i_{1} < i_{2} < i_{3} < ... < i_{k} ≤ n

such that

π(i_{1}) < π(i_{2}) < π(i_{3}) < ... < π(i_{k})

For example

π = ( \begin{matrix}1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 4 & 1 & 2 \end{matrix} )

has increasing subsequences of length 2, at points {2, 3} as well as at positions {4, 5}. Let π_{2}(n) be the number of permutations of n letters that have no increasing subsequences of length > 2. By direct enumeration we obtain the following table.

\begin{matrix}n & π_{2}(n) \\ 0 & 1 \\ 1 & 1 \\ 2 & 2 \\ 3 & 5 \\ 4 & 14 \\ 5 & 42 \\ 6 & 132 \\ 7 & 429 \\ 8 & 1430 \end{matrix}

Proposition 1. |π_{2}(n)| = C_{n}, where π_{2}(n) the number of permutations of n letters that have no increasing subsequences of length > 2 and C_{n} is the n-th Catalan number.

C_{n} = \frac{1}{n + 1} ( \begin{matrix}2n \\ n \end{matrix} )

4.3 Young Tableaux

Definition 1. A partition of n, written λ ⊢ n, is a sequence,

λ = (λ_{1}, λ_{2}, λ_{3}, ..., λ_{k})

such that the λ_{i} are decreasing (weakly) and ∑_{i=1}^{k} λ_{i} = n. Let λ = (λ_{1}, λ_{2}, λ_{3}, ..., λ_{k}) ⊢ n. Then the Ferrers diagram, or shape, of λ is an array of n-squares into k left-justified rows with row i containing λ_{i} squares for 1 ≤ i ≤ k. For example, the partition (4,3,1)

Let λ be as above. A Young tableau of shape λ, is an array obtained by replacing the squares of the shape of λ by a bijection with the numbers 1,2,...,n. A tableau T is said to be a standard Young tableau if the rows and columns are increasing sequences. For example below the tableau is standard

A standard Young tableau of two lines is of the shape λ(l_{1}, l_{2}) ⊢ n where l_{1} ≥ l_{2} > 0. Let f^{(l_{1},l_{2})} be the number of standard tableaux of two lines. We have

f^{(l_{1},l_{2})} = \frac{l_{1} − l_{2} + 1}{l_{1} + 1} ( \begin{matrix}l_{1} + l_{2} \\ l_{1} \end{matrix} )

Proposition 2. If l_{1} = l_{2} then

f^{(l_{1},l_{1})} = \frac{1}{l_{1} + 1} ( \begin{matrix}2l_{1} \\ l_{1} \end{matrix} )

which is th n-th Catalan number C_{n}.

In general, we can represent a Young tableaux of two (equal) lines as follows :

Then

2n − k = h

will be the second parameter of the tableau.

Example :

A Young tableau of size six and height two

Then

6 − 4 = 2

we remark that 2 is the last letter of

σ_{2}(3) = 312

4.4 Dyck Words and Dyck Paths

Let w be a word and a a letter, the length of w will be denoted by |w|, and the number of occurrences of a in w by |w|_{a}. We denote the empty word by ϵ. If w = uv , then u is a prefix of w.

Definition 2. A Dyck word w is a word over the alphabet ∑ = {0, 1} with the following properties :

• For each prefix of u of w, |u|_{1} ≥ |u|_{0}

• |w|_{1} = |w|_{0}

A Dyck path is a path in the first quadrant, which begins at the origin (0, 0), ends at (2n, 0). A Dyck path consists North-east and South-east steps. The number of Dyck paths of length 2n is the Catalan number

C_{n} = \frac{1}{n + 1} ( \begin{matrix}2n \\ n \end{matrix} )

and thus,

∑_{n≥0} C_{n}x^{n} = \frac{1 − \sqrt{1 − 4x}}{2x}

Now, we can refine the number of Dyck words with respect to a parameter like k which is the number of factors in Dyck words. The number of Dyck words of length 2n which decompose into k (irreducible Dyck) factors is exactly l(n, k) and their sum (over k) equal to the Catalan numbers. For example

a a a a b b b b

is a Dyck word of length 4 which has one factor.

4.5 Bijections

In this chapter we will describe the links between some combinatorial famillies and we try to give certain properties that help us to understand the connection.

Codes ↔ σ_{2}(n) ↔ Y oungtableaux ↔ Dyckwords

Theorem 1. Let Φ = {a} ∪ Φ^{+} be a data structure with a bi-variate statistics

l : Φ → N^{2}
s → l(s) = (n, k)

such that

l(Φ^{+}) ⊂ N^{+} × N

Suppose that We suppose that there exist a function d : Φ^{+} → Φ such that

1. d : Φ_{n} → Φ_{n−1} (Φ_{n} = (pr_{1} ∘ l)^{−1}(n))

2. ϕ : Φ_{n} → Φ_{n−1} × N^{+} s → (d(s), k) is injective

3. define π = pr_{2} ∘ l. For all s ∈ Φ we define his code by

χ(s) = (π(d^{n−1}(s)), π(d^{n−2}(s)), ⋯ π(d(s)), π(s))

then χ is injective.

For example to pass a code 1 1 2 2 to σ_{2}(4), f^{(4,4)} and Dyck word of length 8 which decompose into one factor.

σ_{2}(2) : 1 → 1 2 → 3 1 2 → 3 4 1 2

Dyck words : a b → a a b b → a b a a b b → a a b a a b b b

Figure 2: Young tableau

5 Conclusion

We have presented an toy-model economic behaviour based on local rules and we propose some global function expression which can be also described by three combinatorics structures. By this application, we point out a one-to-one correspondence between three other ballot-like structures. The innovative aspect of this paper deals with a constructive development of the involved bijections.

References

[1] B.E. Sagan, The symmetric group, 1991 .

[2] C. Schensted, Longest increasing and decreasing subsequences, Canad.J.Math, 13(1961), 179-191.

[5] M.P. Schtzenberger, Quelques remarques sur une construction de Schensted, Math. Scand., 12(1963), 117-128.

[5] Herbert S. Wilf, Ascending subsequences of permutations and the shape of tableaux, Journal of Combin. theory, series A 60(1992), 155-157.

[5] Herbert S. Wilf, The computer-aided discovery of a theorem about Young tableaux, J. Symbolic Computation, series 20 (1995), 731-735.

[6] Per Bak, How nature works - the science of self-organized criticality, Springer Verlag, 1996.

[7] Thomas Schelling, Dynamic models of segregation, J. of Math. Sociology, vol. 1, 1971.