+>E=JHE= EJAHFHAJ=JEI B =?>E5JEHEC K>AHI

Combinatorial interpretations of Jacobi-Stirling numbers

Yoann Gelineau

Universit´e Claude Bernard Lyon 1, France

September 29th, 2009 - 63th SLC

Yoann Gelineau Jacobi-Stirling numbers

The Jacobi polynomialsPn^(𝛼,𝛽)(t) satisfy the Jacobi equation : (1−t²)y^′′(t)+(𝛽−𝛼−(𝛼+𝛽+2)t)y^′(t)+n(n+𝛼+𝛽+1)y(t) = 0.

Letℓ_𝛼,𝛽[y](t) be the Jacobi differential operator : ℓ_𝛼,𝛽[y](t) = 1

(1−t)^𝛼(1 +t)^𝛽

(−(1−t)^𝛼+1(1 +t)^𝛽+1y^′(t))′

So,Pn^(𝛼,𝛽)(t) is a solution of

ℓ𝛼,𝛽[y](t) =n(n+𝛼+𝛽+ 1)y(t)

Yoann Gelineau Jacobi-Stirling numbers

The Jacobi polynomialsPn^(𝛼,𝛽)(t) satisfy the Jacobi equation : (1−t²)y^′′(t)+(𝛽−𝛼−(𝛼+𝛽+2)t)y^′(t)+n(n+𝛼+𝛽+1)y(t) = 0.

Letℓ_𝛼,𝛽[y](t) be the Jacobi differential operator : ℓ_𝛼,𝛽[y](t) = 1

(1−t)^𝛼(1 +t)^𝛽

(−(1−t)^𝛼+1(1 +t)^𝛽+1y^′(t))′

So,Pn^(𝛼,𝛽)(t) is a solution of

ℓ𝛼,𝛽[y](t) =n(n+𝛼+𝛽+ 1)y(t)

Yoann Gelineau Jacobi-Stirling numbers

Everitt and al. gave the expansion of then-th composite power of ℓ𝛼,𝛽, involving a sequence of positive integersP^(𝛼,𝛽)S(n,k) :

(1−t)^𝛼(1 +t)^𝛽ℓⁿ_𝛼,𝛽[y](t) = n

∑

k=0 (−1)^k(

P^(𝛼,𝛽)S(n,k)(1−t)^𝛼+k(1 +t)^𝛽+ky^(k)(t) )_(k)

Actually,P^(𝛼,𝛽)S(n,k) depends only onz =𝛼+𝛽+ 1. We denote it byJS_n^k(z), theJacobi-Stirling number of the second kind.

Yoann Gelineau Jacobi-Stirling numbers

Everitt and al. gave the expansion of then-th composite power of ℓ𝛼,𝛽, involving a sequence of positive integersP^(𝛼,𝛽)S(n,k) :

(1−t)^𝛼(1 +t)^𝛽ℓⁿ_𝛼,𝛽[y](t) = n

∑

k=0 (−1)^k(

P^(𝛼,𝛽)S(n,k)(1−t)^𝛼+k(1 +t)^𝛽+ky^(k)(t) )_(k)

Actually,P^(𝛼,𝛽)S(n,k) depends only onz =𝛼+𝛽+ 1. We denote it byJS_n^k(z), theJacobi-Stirling number of the second kind.

Yoann Gelineau Jacobi-Stirling numbers

TheJS_n^k(z) numbers are the relation coefficients in the following formula :

Xⁿ=

n

∑

k=0

JS^k_n(z)

k−1

∏

i=0

(X −i(z+i))

Equivalently, these numbers can be defined by the recurrence relation :

JS^k_n(z) = JS^k−1_n−1(z) +k(k+z)JS^k_n−1(z), n,k ≥1 JS⁰₀(z) = 1, JS^k_n(z) = 0 if k ∕∈ {1, . . . ,n}

Yoann Gelineau Jacobi-Stirling numbers

TheJS_n^k(z) numbers are the relation coefficients in the following formula :

Xⁿ=

n

∑

k=0

JS^k_n(z)

k−1

∏

i=0

(X −i(z+i))

Equivalently, these numbers can be defined by the recurrence relation :

JS^k_n(z) = JS^k−1_n−1(z) +k(k+z)JS^k_n−1(z), n,k ≥1 JS⁰₀(z) = 1, JS^k_n(z) = 0 if k ∕∈ {1, . . . ,n}

Yoann Gelineau Jacobi-Stirling numbers

TheStirling numbers (of the second kind)S_n^k are defined by the relation :

S_n^k =S_n−1^k−1+kS_n−1^k

They count the number of :

partitions of [n] :={1,2, . . . ,n} ink non-empty blocks. supdiagonal quasi-permutations of [n] :={1,2, . . . ,n} withk empty lines.

Yoann Gelineau Jacobi-Stirling numbers

TheStirling numbers (of the second kind)S_n^k are defined by the relation :

S_n^k =S_n−1^k−1+kS_n−1^k They count the number of :

partitions of [n] :={1,2, . . . ,n}in k non-empty blocks.

supdiagonal quasi-permutations of [n] :={1,2, . . . ,n} withk empty lines.

Yoann Gelineau Jacobi-Stirling numbers

For example,

𝜋 ={

{1,3,6},{2,5},{4}} is a partition of [6] in 3 blocks.

It corresponds to the following quasi-permutation :

Yoann Gelineau Jacobi-Stirling numbers

For example,

𝜋 ={

{1,3,6},{2,5},{4}} is a partition of [6] in 3 blocks.

It corresponds to the following quasi-permutation :

Yoann Gelineau Jacobi-Stirling numbers

Thecentral factorial numbers (of the second kind) U_n^k are defined by the relation :

U_n^k =U_n−1^k−1+k²U_n−1^k

They count the number of :

ordered pairs (𝜋1, 𝜋2) of partitions of [n] ink blocks, with min(𝜋₁) = min(𝜋₂).

ordered pairs (Q₁,Q₂) of supdiagonal quasi-permutations of [n], withQ₁ andQ₂ which havek same empty lines.

Yoann Gelineau Jacobi-Stirling numbers

Thecentral factorial numbers (of the second kind) U_n^k are defined by the relation :

U_n^k =U_n−1^k−1+k²U_n−1^k They count the number of :

ordered pairs (𝜋1, 𝜋2) of partitions of [n] ink blocks, with min(𝜋₁) = min(𝜋₂).

ordered pairs (Q₁,Q₂) of supdiagonal quasi-permutations of [n], withQ₁ andQ₂ which havek same empty lines.

Yoann Gelineau Jacobi-Stirling numbers

For example, if we note 𝜋1 ={

{1,3,6},{2,5},{4}}

, 𝜋2 ={

{1},{2,3,5},{4,6}} , 𝜋1 and𝜋2 are partitions of [6] in 3 blocks, with min(𝜋1) = min(𝜋2)

The ordered pair (𝜋1, 𝜋2) corresponds to the folloqing ordered pair of supdiagonal quasi-permutations :

Yoann Gelineau Jacobi-Stirling numbers

For example, if we note 𝜋1 ={

{1,3,6},{2,5},{4}}

, 𝜋2 ={

{1},{2,3,5},{4,6}} , 𝜋1 and𝜋2 are partitions of [6] in 3 blocks, with min(𝜋1) = min(𝜋2) The ordered pair (𝜋1, 𝜋2) corresponds to the folloqing ordered pair of supdiagonal quasi-permutations :

Yoann Gelineau Jacobi-Stirling numbers

⇒Let’s come back to the Jacobi-Stirling numbers :

JS^k_n(z) = JS^k−1_n−1(z) +k(k+z)JS^k_n−1(z), n,k ≥1

JS^k_n(z) is a polynomial in z of degreen−k :

JS^k_n(z) =a⁽⁰⁾_n,k+a⁽¹⁾_n,kz+⋅ ⋅ ⋅+a^(n−k)_n,k z^n−k Moreover,

a^(n−k_n,k ⁾=S_n^k a⁽⁰⁾_n,k =U_n^k

Yoann Gelineau Jacobi-Stirling numbers

⇒Let’s come back to the Jacobi-Stirling numbers :

JS^k_n(z) = JS^k−1_n−1(z) +k(k+z)JS^k_n−1(z), n,k ≥1 JS^k_n(z) is a polynomial in z of degreen−k :

JS^k_n(z) =a⁽⁰⁾_n,k +a⁽¹⁾_n,kz+⋅ ⋅ ⋅+a^(n−k)_n,k z^n−k

Moreover,

a^(n−k_n,k ⁾=S_n^k a⁽⁰⁾_n,k =U_n^k

Yoann Gelineau Jacobi-Stirling numbers

⇒Let’s come back to the Jacobi-Stirling numbers :

JS^k_n(z) = JS^k−1_n−1(z) +k(k+z)JS^k_n−1(z), n,k ≥1 JS^k_n(z) is a polynomial in z of degreen−k :

JS^k_n(z) =a⁽⁰⁾_n,k +a⁽¹⁾_n,kz+⋅ ⋅ ⋅+a^(n−k)_n,k z^n−k Moreover,

a^(n−k_n,k ⁾=S_n^k a⁽⁰⁾_n,k =U_n^k

Yoann Gelineau Jacobi-Stirling numbers

Definition

A k-signed partitionof[±n]₀ ={0,±1,±2, . . . ,±n}is a partition of[±n]₀ in k+ 1non-empty blocks B0,B1, . . . ,B_k, such that

0∈B0 et ∀i ∈[n],{i,−i} ∕⊂B0

∀j ∈[k],∀i ∈[n],{i,−i} ⊂Bj ⇔i = minBj ∩[n]

For example, 𝜋={

{0,2,−5},{±1,−2},{±3},{±4,5}} is a 3-signed partition of [±5]₀.

Yoann Gelineau Jacobi-Stirling numbers

Theorem

a_n,k⁽ⁱ⁾ is equal to the number of k-signed partitions of[±n]₀ with i negative values in the block that contains0.

Proof :Since JS^k_n(z) verify the relation :

JS^k_n(z) = JS^k−1_n−1(z) +k(k+z) JS^k_n−1(z),

it suffices to check that the wanted numbers verify the recurrence :

Yoann Gelineau Jacobi-Stirling numbers

Theorem

a_n,k⁽ⁱ⁾ is equal to the number of k-signed partitions of[±n]₀ with i negative values in the block that contains0.

Proof :Since JS^k_n(z) verify the relation :

JS^k_n(z) = JS^k−1_n−1(z) +k(k+z) JS^k_n−1(z),

it suffices to check that the wanted numbers verify the recurrence : a_n,k⁽ⁱ⁾ =a⁽ⁱ_n−1,k−1⁾ +ka_n−1,k⁽ⁱ⁻¹⁾ +k²a⁽ⁱ_n−1,k⁾

Yoann Gelineau Jacobi-Stirling numbers

Theorem

a_n,k⁽ⁱ⁾ is equal to the number of k-signed partitions of[±n]₀ with i negative values in the block that contains0.

Proof :Since JS^k_n(z) verify the relation :

JS^k_n(z) = JS^k−1_n−1(z) +k(k+z) JS^k_n−1(z),

it suffices to check that the wanted numbers verify the recurrence : a⁽ⁱ_n,k⁾ =a⁽ⁱ⁾_n−1,k−1

| {z }

Bk={±n}

+ka_n−1,k⁽ⁱ⁻¹⁾

| {z }

−n∈B0

+k²a_n−1,k⁽ⁱ⁾

| {z }

other cases

Yoann Gelineau Jacobi-Stirling numbers

a_n,k⁽ⁱ⁾ =♯{k−signed partitions of [±n]₀with i values <0 inB₀}

⇒For i =n−k, we recover the interpretation ofS_n^k. 𝜋 ={

{0,−3,−5,−6},{±1,3,6},{±2,5},{±4}}

⇓ 𝜋^′ ={

{1,3,6},{2,5},{4}}

⇒For i = 0, we recover the interpretation of U_n^k. 𝜋={

{0,3,6},{±1,−3,},{±2,−5},{±4,5,−6}}

⇓ 𝜋₁={

{1,3},{2},{4,5,6}}

, 𝜋₂ ={

{1,3},{2,5},{4,6}}

Yoann Gelineau Jacobi-Stirling numbers

a_n,k⁽ⁱ⁾ =♯{k−signed partitions of [±n]₀with i values <0 inB₀}

⇒For i =n−k, we recover the interpretation ofS_n^k. 𝜋 ={

{0,−3,−5,−6},{±1,3,6},{±2,5},{±4}}

⇓ 𝜋^′ ={

{1,3,6},{2,5},{4}}

⇒For i = 0, we recover the interpretation of U_n^k. 𝜋={

{0,3,6},{±1,−3,},{±2,−5},{±4,5,−6}}

⇓ 𝜋₁={

{1,3},{2},{4,5,6}}

, 𝜋₂ ={

{1,3},{2,5},{4,6}}

Yoann Gelineau Jacobi-Stirling numbers

a_n,k⁽ⁱ⁾ =♯{k−signed partitions of [±n]₀with i values <0 inB₀}

⇒For i =n−k, we recover the interpretation ofS_n^k. 𝜋 ={

{0,−3,−5,−6},{±1,3,6},{±2,5},{±4}}

⇓ 𝜋^′ ={

{1,3,6},{2,5},{4}}

⇒For i = 0, we recover the interpretation of U_n^k. 𝜋={

{0,3,6},{±1,−3,},{±2,−5},{±4,5,−6}}

⇓ 𝜋₁={

{1,3},{2},{4,5,6}}

, 𝜋₂ ={

{1,3},{2,5},{4,6}}

Yoann Gelineau Jacobi-Stirling numbers

Definition

Asimply hooked k-quasi-permutation of [n](k-SHQP of [n]) is a part Q of a tableau[n]×[n]such that :

Q is contained in the graph of a permutation 𝜎 without fix points,

each diagonal hook contains at most one elemnt, there are k empty diagonal hooks.

For example, is a 2-SHQP of [8].

Yoann Gelineau Jacobi-Stirling numbers

Definition

Asimply hooked k-quasi-permutation of [n](k-SHQP of [n]) is a part Q of a tableau[n]×[n]such that :

Q is contained in the graph of a permutation 𝜎 without fix points,

each diagonal hook contains at most one elemnt, there are k empty diagonal hooks.

For example, is a 2-SHQP of [8].

Yoann Gelineau Jacobi-Stirling numbers

Definition

Asimply hooked k-quasi-permutation of [n](k-SHQP of [n]) is a part Q of a tableau[n]×[n]such that :

Q is contained in the graph of a permutation 𝜎 without fix points,

each diagonal hook contains at most one elemnt, there are k empty diagonal hooks.

For example, is a 2-SHQP of [8].

Yoann Gelineau Jacobi-Stirling numbers

Definition

Asimply hooked k-quasi-permutation of [n](k-SHQP of [n]) is a part Q of a tableau[n]×[n]such that :

Q is contained in the graph of a permutation 𝜎 without fix points,

each diagonal hook contains at most one elemnt, there are k empty diagonal hooks.

For example, is a 2-SHQP of [8].

Yoann Gelineau Jacobi-Stirling numbers

Definition

Asimply hooked k-quasi-permutation of [n](k-SHQP of [n]) is a part Q of a tableau[n]×[n]such that :

Q is contained in the graph of a permutation 𝜎 without fix points,

each diagonal hook contains at most one elemnt, there are k empty diagonal hooks.

For example, is a 2-SHQP of [8].

Yoann Gelineau Jacobi-Stirling numbers

Definition

Asimply hooked k-quasi-permutation of [n](k-SHQP of [n]) is a part Q of a tableau[n]×[n]such that :

Q is contained in the graph of a permutation 𝜎 without fix points,

each diagonal hook contains at most one elemnt, there are k empty diagonal hooks.

For example, is a 2-SHQP of [8].

Yoann Gelineau Jacobi-Stirling numbers

Definition

Asimply hooked k-quasi-permutation of [n](k-SHQP of [n]) is a part Q of a tableau[n]×[n]such that :

Q is contained in the graph of a permutation 𝜎 without fix points,

each diagonal hook contains at most one elemnt, there are k empty diagonal hooks.

For example, is a 2-SHQP of [8].

Yoann Gelineau Jacobi-Stirling numbers

Definition

Asimply hooked k-quasi-permutation of [n](k-SHQP of [n]) is a part Q of a tableau[n]×[n]such that :

Q is contained in the graph of a permutation 𝜎 without fix points,

each diagonal hook contains at most one elemnt, there are k empty diagonal hooks.

For example, is a 2-SHQP of [8].

Yoann Gelineau Jacobi-Stirling numbers

Definition

Asimply hooked k-quasi-permutation of [n](k-SHQP of [n]) is a part Q of a tableau[n]×[n]such that :

Q is contained in the graph of a permutation 𝜎 without fix points,

each diagonal hook contains at most one elemnt, there are k empty diagonal hooks.

For example, is a 2-SHQP of [8].

Yoann Gelineau Jacobi-Stirling numbers

Theorem

a_n,k⁽ⁱ⁾ counts also the number of ordered pairs (Q₁,Q₂) of k-SHQP of[n]such that

Q₁ and Q₂ have k empty lines (the same), Q₁ and Q₂ have identical subdiagonal parts,

Q1 and Q2 have i filled boxes in their subdiagonal parts.

Yoann Gelineau Jacobi-Stirling numbers

⇒Pour i =n−k, we recover the interpretation ofS_n^k.

⇒For i = 0, we recover the interpretation of U_n^k.

Yoann Gelineau Jacobi-Stirling numbers

⇒Pour i =n−k, we recover the interpretation ofS_n^k.

⇒For i = 0, we recover the interpretation of U_n^k.

Yoann Gelineau Jacobi-Stirling numbers

TheJacobi-Stirling numbers (of the first kind)js^k_n(z) are defined by inversing the relation on the JS^k_n(z) numbers :

Xⁿ=

n

∑

k=0

JS^k_n(z)

k−1

∏

i=0

(X −i(z+i))

n−1

∏

i=0

(X−i(z+i)) =

n

∑

k=0

(−1)^n−kjs^k_n(z)X^k

It follows that they verify the following relation :

js^k_n(z) = js^k_n−1⁻¹(z) + (n−1)(n−1 +z) js^k_n−1(z)

Yoann Gelineau Jacobi-Stirling numbers

TheJacobi-Stirling numbers (of the first kind)js^k_n(z) are defined by inversing the relation on the JS^k_n(z) numbers :

Xⁿ=

n

∑

k=0

JS^k_n(z)

k−1

∏

i=0

(X −i(z+i))

n−1

∏

i=0

(X−i(z+i)) =

n

∑

k=0

(−1)^n−kjs^k_n(z)X^k It follows that they verify the following relation :

js^k_n(z) = js^k_n−1⁻¹(z) + (n−1)(n−1 +z) js^k_n−1(z)

Yoann Gelineau Jacobi-Stirling numbers

TheStirling numbers (of the first kind) s_n^k are defined by the relation :

s_n^k =s_n−1^k−1+ (n−1)s_n−1^k

Thecentral factorial numbers (of the first kind) u_n^k are defined by the relation :

u_n^k =u_n−1^k−1+ (n−1)²u_n−1^k

s_n^k is the number of permutations of [n] withk cycles. u_n^k had still no interpretation until present.

Yoann Gelineau Jacobi-Stirling numbers

TheStirling numbers (of the first kind) s_n^k are defined by the relation :

s_n^k =s_n−1^k−1+ (n−1)s_n−1^k

Thecentral factorial numbers (of the first kind) u_n^k are defined by the relation :

u_n^k =u_n−1^k−1+ (n−1)²u_n−1^k

s_n^k is the number of permutations of [n] withk cycles.

u_n^k had still no interpretation until present.

Yoann Gelineau Jacobi-Stirling numbers

js^k_n(z) is a polynomial in z of degreen−k :

js^k_n(z) =b⁽⁰⁾_n,k +b_n,k⁽¹⁾z+⋅ ⋅ ⋅+b^(n−k)_n,k z^n−k

Moreover,

b_n,k^(n−k)=s_n^k b⁽⁰⁾_n,k =u_n^k

Yoann Gelineau Jacobi-Stirling numbers

js^k_n(z) is a polynomial in z of degreen−k :

js^k_n(z) =b⁽⁰⁾_n,k +b_n,k⁽¹⁾z+⋅ ⋅ ⋅+b^(n−k)_n,k z^n−k Moreover,

b_n,k^(n−k) =s_n^k b⁽⁰⁾_n,k =u_n^k

Yoann Gelineau Jacobi-Stirling numbers

Definition

Let w =w(1)w(2). . .w(ℓ) be a word on the alphabet[n]. A letter w(j) is a recordof w if

w(j)<w(k), ∀k = 1. . .j−1 We denote by rec(w) the number of records of w and rec0(w) =rec(w)−1.

For example, for

w = 5 7 4 8 6 2 3 1 9, the records are

5,4,2,1.

Thus, rec(w) = 4 and rec₀(w) = 3.

Yoann Gelineau Jacobi-Stirling numbers

Theorem

b⁽ⁱ_n,k⁾ is the number of ordered pairs (𝜎, 𝜏) with : 𝜎 is a permutation of[n]∪ {0} with k cycles, 𝜏 is a permutation of[n]with k cycles, 𝜎 and𝜏 have the same cyclic minimas, 1∈Orb𝜎(0)and rec0(w) =i

where w =𝜎(0). . . 𝜎^ℓ(0)with 𝜎^ℓ+1(0) = 0.

Idea : interpret the formula

b⁽ⁱ⁾_n,k =b_n−1,k−1⁽ⁱ⁾ + (n−1)b⁽ⁱ_n−1,k⁻¹⁾ + (n−1)²b⁽ⁱ⁾_n−1,k

Yoann Gelineau Jacobi-Stirling numbers

Theorem

b⁽ⁱ_n,k⁾ is the number of ordered pairs (𝜎, 𝜏) with : 𝜎 is a permutation of[n]∪ {0} with k cycles, 𝜏 is a permutation of[n]with k cycles, 𝜎 and𝜏 have the same cyclic minimas, 1∈Orb𝜎(0)and rec0(w) =i

where w =𝜎(0). . . 𝜎^ℓ(0)with 𝜎^ℓ+1(0) = 0.

Idea : interpret the formula

b⁽ⁱ⁾_n,k =b_n−1,k−1⁽ⁱ⁾ + (n−1)b⁽ⁱ_n−1,k⁻¹⁾ + (n−1)²b⁽ⁱ⁾_n−1,k

Yoann Gelineau Jacobi-Stirling numbers

⇒For i =n−k, we recover the interpretation ofs_n^k.

⇒For i = 0, we recover the interpretation of u_n^k.

u_n^k is the number of ordered pairs of permutations (𝜎₁, 𝜎₂) of [n] withk cycles, with same cyclic minimas.

Yoann Gelineau Jacobi-Stirling numbers

⇒For i =n−k, we recover the interpretation ofs_n^k.

⇒For i = 0, we recover the interpretation of u_n^k.

u_n^k is the number of ordered pairs of permutations (𝜎₁, 𝜎₂) of [n]

withk cycles, with same cyclic minimas.

Yoann Gelineau Jacobi-Stirling numbers

Thanks for your attention.

Yoann Gelineau Jacobi-Stirling numbers