March2017 SylvieCorteelArthurNunge 2-speciesexclusionprocessesandcombinatorialalgebras

(1)

Introduction Combinatorics of the 2-ASEP Generalization ofSym Conclusion and perspectives

2-species exclusion processes and combinatorial algebras

Sylvie Corteel Arthur Nunge

IRIF, LIGM

March 2017

(2)

Non commutative symmetric functions

The algebra of noncommutative symmetric functionsSymis an algebra generalizing the symmetric functions. Its component of degreenhas dimention 2ⁿ⁻¹. One can index its bases by compositions.

A composition of sizenis a sequence of integersI= (i1,i2, . . . ,ir) of sumn. Complete basis (analog ofh_λ)

For alln, define

Sn= X

1≤j₁≤j₂≤···≤j_n

aj₁aj₂· · ·aj_n.

For any compositionI= (i1,i2, . . . ,ir),

S^I=Si₁Si₂· · ·Si_r.

For example,S2(a1,a2,a3) =a²₁+a1a2+a1a3+a₂²+a2a3+a²₃.

(3)

A composition of sizenis a sequence of integersI= (i1,i2, . . . ,ir) of sumn.

Complete basis (analog ofh_λ) For alln, define

Sn= X

1≤j₁≤j₂≤···≤j_n

(4)

Sn= X

1≤j₁≤j₂≤···≤j_n

(5)

Sn= X

1≤j₁≤j₂≤···≤j_n

(6)

Sn= X

1≤j₁≤j₂≤···≤j_n

(7)

Ribbon basis

RI=X

JI

(−1)^l(J)−l(I)S^J.

For example,R221=S²²¹−S⁴¹−S²³+S⁵.

Polynomial realization

RI = X

Des(w)=I

w. For example,R221(a1,a2) =a1a2a1a2a1+a2a2a1a2a1.

(8)

Ribbon basis

RI=X

JI

(−1)^l(J)−l(I)S^J.

For example,R221=S²²¹−S⁴¹−S²³+S⁵. Polynomial realization

RI = X

Des(w)=I

w. For example,R221(a1,a2) =a1a2a1a2a1+a2a2a1a2a1.

(9)

Tevlin’s bases

In 2007 L. Tevlin defined the monomial (MI) and fundamental (LI) that are analog of the monomial basis and elementary basis ofSym. They both have binomial structure coefficients.

Transition matrices

The transition matrices between the ribbon basis and the fundamental basis of size 3 and 4 are:

M3=







1 . . .

. 2 1 .

. . 1 .

. . . 1







M4=







1 . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . 2 1 .

. . . 1 .

. . . 1







(10)

Tevlin’s bases

In 2007 L. Tevlin defined the monomial (MI) and fundamental (LI) that are analog of the monomial basis and elementary basis ofSym. They both have binomial structure coefficients.

Transition matrices

The transition matrices between the ribbon basis and the fundamental basis of size 3 and 4 are:

M3=







1 . . .

. 2 1 .

. . 1 .

. . . 1







M4=







1 . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . 2 1 .

. . . 1 .

. . . 1







(11)

Statistics on permutations

• Rec(σ) is the composition associated with the values of recoils (i.e., the valuesksuch thatk+ 1 is on the left).

Forσ= 25783641

soRec(25783641) = .

• GC(σ) is the composition associated with the values of descents (i.e., the valuesk=σi such thatσi > σi+1) minus one.

Forσ= 25783641, GC(σ) = .

Combinatorial interpretation (F. Hivert, J.-C. Novelli, L. Tevlin, J.-Y. Thibon, 2009)







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(12)

Forσ=25783641, the recoils are{1}

soRec(25783641) = .

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(13)

Forσ=25783641, the recoils are{1}

soRec(25783641) = .

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(14)

Forσ= 25783641, the recoils are{1}

soRec(25783641) = .

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(15)

Forσ= 25783641, the recoils are{1,4}

soRec(25783641) = .

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(16)

Forσ= 25783641, the recoils are{1,4}

soRec(25783641) = .

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(17)

Forσ= 25783641, the recoils are{1,4,6}

soRec(25783641) = .

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(18)

Forσ= 25783641, the recoils are{1,4,6}

soRec(25783641) = .

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(19)

Forσ= 25783641, the recoils are{1,4,6}soRec(25783641) =1.

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(20)

Forσ= 25783641, the recoils are{1,4,6}soRec(25783641) = 13.

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(21)

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(22)

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(23)

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(24)

Forσ=25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(25)

Forσ= 25783641, GC(σ) = .







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(26)

Forσ= 25783641, GC(σ) =3.







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321

(27)

Forσ= 25783641, GC(σ) = 3.







1 . . . . . . .

. 3 2 . 1 1 . .

. . 2 . 1 . . .

. . 1 3 . 2 1 .

. . . . 1 . . .

. . . . . 2 1 .

. . . . . . 1 .

. . . . . . . 1







GC\Rec 4 31 22 211 13 121 112 1111

4 1234

31 ^1243,₄₁₂₃¹⁴²³ ¹³⁴²₃₄₁₂ 2341 2413

22 ¹³²⁴₃₁₂₄ 2314

211 3142 ^1432,₄₃₁₂⁴¹³² ²⁴³¹₄₂₃₁ 3241

13 2134

121 ²¹⁴³₄₂₁₃ 3421

112 3214

1111 4321