# Touchard Polynomials, Stirling Numbers and Random Permutations Touchard Polynomials, Stirling...

date post

22-Jul-2020Category

## Documents

view

0download

0

Embed Size (px)

### Transcript of Touchard Polynomials, Stirling Numbers and Random Permutations Touchard Polynomials, Stirling...

Touchard Polynomials, Stirling Numbers and Random Permutations

Ross Pinsky

Department of Mathematics, Technion 32000 Haifa, ISRAEL

September 3, 2018

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Notation:

[n] = {1, 2, · · · , n}

Sn = permutations of [n]

|Sn| = n!

S6 3 σ1 = (

1 2 3 4 5 6 2 4 6 1 5 3

) = (124)(36)(5),

S6 3 σ2 = (

1 2 3 4 5 6 3 4 6 5 1 2

) = (136245) = (624513)

σ2 is a 6-cycle in S6. There are 5! different 6-cycles in S6.

There are (n − 1)! different n-cycles in Sn.

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Notation:

[n] = {1, 2, · · · , n}

Sn = permutations of [n]

|Sn| = n!

S6 3 σ1 = (

1 2 3 4 5 6 2 4 6 1 5 3

) = (124)(36)(5),

S6 3 σ2 = (

1 2 3 4 5 6 3 4 6 5 1 2

) = (136245) = (624513)

σ2 is a 6-cycle in S6. There are 5! different 6-cycles in S6.

There are (n − 1)! different n-cycles in Sn.

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Notation:

[n] = {1, 2, · · · , n}

Sn = permutations of [n]

|Sn| = n!

S6 3 σ1 = (

1 2 3 4 5 6 2 4 6 1 5 3

) = (124)(36)(5),

S6 3 σ2 = (

1 2 3 4 5 6 3 4 6 5 1 2

) = (136245) = (624513)

σ2 is a 6-cycle in S6. There are 5! different 6-cycles in S6.

There are (n − 1)! different n-cycles in Sn.

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Notation:

[n] = {1, 2, · · · , n}

Sn = permutations of [n]

|Sn| = n!

S6 3 σ1 = (

1 2 3 4 5 6 2 4 6 1 5 3

) = (124)(36)(5),

S6 3 σ2 = (

1 2 3 4 5 6 3 4 6 5 1 2

) = (136245) = (624513)

σ2 is a 6-cycle in S6. There are 5! different 6-cycles in S6.

There are (n − 1)! different n-cycles in Sn.

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Notation:

[n] = {1, 2, · · · , n}

Sn = permutations of [n]

|Sn| = n!

S6 3 σ1 = (

1 2 3 4 5 6 2 4 6 1 5 3

) = (124)(36)(5),

S6 3 σ2 = (

1 2 3 4 5 6 3 4 6 5 1 2

) = (136245) = (624513)

σ2 is a 6-cycle in S6. There are 5! different 6-cycles in S6.

There are (n − 1)! different n-cycles in Sn.

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Notation:

[n] = {1, 2, · · · , n}

Sn = permutations of [n]

|Sn| = n!

S6 3 σ1 = (

1 2 3 4 5 6 2 4 6 1 5 3

) = (124)(36)(5),

S6 3 σ2 = (

1 2 3 4 5 6 3 4 6 5 1 2

) = (136245) = (624513)

σ2 is a 6-cycle in S6. There are 5! different 6-cycles in S6.

There are (n − 1)! different n-cycles in Sn.

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Rising Factorials

x (n) := x(x +1) · · · (x +n−1)

( ≡

n∑ k=1

ankx k ) , x ∈ R, n ≥ 1. (1)

Unsigned Stirling Numbers of the First Kind: |s(n, k)| := the number of permutations in Sn with exactly k cycles, 1 ≤ k ≤ n Recurrence relation

|s(n, n)| = 1, |s(n, 1)| = (n − 1)!, n ≥ 1; |s(n + 1, k)| = n|s(n, k)|+ |s(n, k − 1)|, 2 ≤ k ≤ n.

(2)

It is easy to check that the coefficients {ank} in (1) also satisfy (2); thus, ank = |s(n, k)|. Therefore

x (n) = n∑

k=1

|s(n, k)|xk . (3)

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Rising Factorials

x (n) := x(x +1) · · · (x +n−1) ( ≡

n∑ k=1

ankx k ) , x ∈ R, n ≥ 1. (1)

Unsigned Stirling Numbers of the First Kind: |s(n, k)| := the number of permutations in Sn with exactly k cycles, 1 ≤ k ≤ n Recurrence relation

|s(n, n)| = 1, |s(n, 1)| = (n − 1)!, n ≥ 1; |s(n + 1, k)| = n|s(n, k)|+ |s(n, k − 1)|, 2 ≤ k ≤ n.

(2)

It is easy to check that the coefficients {ank} in (1) also satisfy (2); thus, ank = |s(n, k)|. Therefore

x (n) = n∑

k=1

|s(n, k)|xk . (3)

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Rising Factorials

x (n) := x(x +1) · · · (x +n−1) ( ≡

n∑ k=1

ankx k ) , x ∈ R, n ≥ 1. (1)

Unsigned Stirling Numbers of the First Kind: |s(n, k)| := the number of permutations in Sn with exactly k cycles, 1 ≤ k ≤ n

Recurrence relation

|s(n, n)| = 1, |s(n, 1)| = (n − 1)!, n ≥ 1; |s(n + 1, k)| = n|s(n, k)|+ |s(n, k − 1)|, 2 ≤ k ≤ n.

(2)

It is easy to check that the coefficients {ank} in (1) also satisfy (2); thus, ank = |s(n, k)|. Therefore

x (n) = n∑

k=1

|s(n, k)|xk . (3)

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Rising Factorials

x (n) := x(x +1) · · · (x +n−1) ( ≡

n∑ k=1

ankx k ) , x ∈ R, n ≥ 1. (1)

Unsigned Stirling Numbers of the First Kind: |s(n, k)| := the number of permutations in Sn with exactly k cycles, 1 ≤ k ≤ n Recurrence relation

|s(n, n)| = 1, |s(n, 1)| = (n − 1)!, n ≥ 1; |s(n + 1, k)| = n|s(n, k)|+ |s(n, k − 1)|, 2 ≤ k ≤ n.

(2)

x (n) = n∑

k=1

|s(n, k)|xk . (3)

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Rising Factorials

x (n) := x(x +1) · · · (x +n−1) ( ≡

n∑ k=1

ankx k ) , x ∈ R, n ≥ 1. (1)

|s(n, n)| = 1, |s(n, 1)| = (n − 1)!, n ≥ 1; |s(n + 1, k)| = n|s(n, k)|+ |s(n, k − 1)|, 2 ≤ k ≤ n.

(2)

It is easy to check that the coefficients {ank} in (1) also satisfy (2); thus, ank = |s(n, k)|.

Therefore

x (n) = n∑

k=1

|s(n, k)|xk . (3)

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Rising Factorials

x (n) := x(x +1) · · · (x +n−1) ( ≡

n∑ k=1

ankx k ) , x ∈ R, n ≥ 1. (1)

|s(n, n)| = 1, |s(n, 1)| = (n − 1)!, n ≥ 1; |s(n + 1, k)| = n|s(n, k)|+ |s(n, k − 1)|, 2 ≤ k ≤ n.

(2)

x (n) = n∑

k=1

|s(n, k)|xk . (3)

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Falling Factorials

(x)n := x(x − 1) · · · (x − n + 1), x ∈ R, n ≥ 1. (4)

Substituting −x for x in (4), we have (−x)n = −x(−x−1) · · · (−x−n+1) = (−1)nx(x+1) · · · (x+n−1) = (−1)nx (n). Substituting above −x for x , we have

(x)n = (−1)n(−x)(n) from (3)

= (−1)n n∑

k=1

|s(n, k)|(−x)k =

n∑ k=1

(−1)n−k |s(n, k)|xk . (5)

Define s(n, k) := (−1)n−k |s(n, k)|. The s(n, k) are called the Stirling Numbers of the First Kind. From (5) we have

(x)n = n∑

k=1

s(n, k)xk . (6)

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Falling Factorials

(x)n := x(x − 1) · · · (x − n + 1), x ∈ R, n ≥ 1. (4) Substituting −x for x in (4), we have (−x)n = −x(−x−1) · · · (−x−n+1) =

(−1)nx(x+1) · · · (x+n−1) = (−1)nx (n). Substituting above −x for x , we have

(x)n = (−1)n(−x)(n) from (3)

= (−1)n n∑

k=1

|s(n, k)|(−x)k =

n∑ k=1

(−1)n−k |s(n, k)|xk . (5)

Define s(n, k) := (−1)n−k |s(n, k)|. The s(n, k) are called the Stirling Numbers of the First Kind. From (5) we have

(x)n = n∑

k=1

s(n, k)xk . (6)

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Falling Factorials

(x)n := x(x − 1) · · · (x − n + 1), x ∈ R, n ≥ 1. (4) Substituting −x for x in (4), we have (−x)n = −x(−x−1) · · · (−x−n+1) = (−1)nx(x+1) · · · (x+n−1)

= (−1)nx (n). Substituting above −x for x , we have

(x)n = (−1)n(−x)(n) from (3)

= (−1)n n∑

k=1

|s(n, k)|(−x)k =

n∑ k=1

(−1)n−k |s(n, k)|xk . (5)

Define s(n, k) := (−1)n−k |s(n, k)|. The s(n, k) are called the Stirling Numbers of the First Kind. From (5) we have

(x)n = n∑

k=1

s(n, k)xk . (6)

Ross Pinsky Touchard Polynomials, Stirling Numbers and Random Permutations

Falling Factorials

(x)n := x(x − 1) · · · (x − n + 1), x ∈ R, n ≥ 1. (4) Substituting −x for x in (4), we have (−x)n = −x(−x−1) · · · (−x−n+1) = (−1)nx(x+1) · · · (x+n−1) = (−1)nx (n).

Substituting above −x for x , we have

(x)n = (−1)n(−x)(n) from (3)

= (−1)n n∑

k=1

|s

Recommended

*View more*