Partitions of Sets Mike Joseph University of Connecticut February 12, 2016

Partitions of Sets
Mike Joseph
University of Connecticut
February 12, 2016
Problems/topics to look forward to in the talk
Partitions of a set
A triangle of integers other than Pascal’s Triangle
Stirling numbers of the second kind
Where it arises in combinatorial problems and in other
areas of math
nth moment of a Poisson distribution
Number of rhyme schemes of a poem with n lines
Number of possible orders that a race with n people can
finish in (ties allowed)
Number of combinations on a simplex lock
Many other related problems
What is a Partition of a Set?
A partition of a set S is a collection of nonempty pairwise
disjoint subsets whose union is S.
What is a Partition of a Set?
A partition of a set S is a collection of nonempty pairwise
disjoint subsets whose union is S.
An equivalence relation on S induces a unique partition
on S.
What is a Partition of a Set?
A partition of a set S is a collection of nonempty pairwise
disjoint subsets whose union is S.
An equivalence relation on S induces a unique partition
on S.
In this talk the set S will be finite. So a partition on S is
a collection {A1 , . . . , Ak } satisfying
Ai 6= ∅ for every i.
Ai ∩ Aj = ∅ for i 6= j.
A1 ∪ · · · ∪ Ak = S.
The sets A1 , . . . , Ak are called blocks.
Example
{{1, 3, 6}, {2, 5}, {4}} is a partition of {1, 2, 3, 4, 5, 6}.
Notation
Instead of writing {{1, 3, 6}, {2, 5}, {4}}, we write this
partition as 136|25|4.
The order of the blocks is unimportant, so 25|136|4 and
4|25|136 refer to the same partition.
[n] = {1, 2, . . . , n}
1
2
6
3
5
4
Stirling Numbers of the Second Kind
The number of partitions
of [n] (or any n-element set) into k
blocks is denoted nk or S(n, k) and called Stirling numbers
of the second kind. These are named for James Stirling
(1692-1770).
Stirling Numbers of the Second Kind
The number of partitions
of [n] (or any n-element set) into k
blocks is denoted nk or S(n, k) and called Stirling numbers
of the second kind. These are named for James Stirling
(1692-1770).
4
1
=1
4
2
=7
4
3
=6
4
4
=1
1
2
4
3
1
2
1
2
1
2
1
2
1
2
1
2
1
2
4
3
4
3
4
3
4
3
4
3
4
3
4
3
1
2
1
2
1
2
1
2
1
2
1
2
4
3
4
3
4
3
4
3
4
3
4
3
1
2
4
3
Stirling Numbers of the Second Kind
n
= 1 for n ≥ 1
n1 n = 1 for n ≥ 0
Stirling Numbers of the Second Kind
n
= 1 for n ≥ 1
n1 = 1 for n ≥ 0
nn 2 =
Stirling Numbers of the Second Kind
n
= 1 for n ≥ 1
n1 = 1 for n ≥ 0
nn n−1
− 1 for n ≥ 1
2 = 2
Stirling Numbers of the Second Kind
n
= 1 for n ≥ 1
n1 = 1 for n ≥ 0
nn n−1
− 1 for n ≥ 1
2 = 2
n n−1 =
Stirling Numbers of the Second Kind
n
= 1 for n ≥ 1
n1 = 1 for n ≥ 0
nn n−1
− 1 for n ≥ 1
2 = 2
n(n−1)
n n
=
2 =
2
n−1
Stirling Numbers of the Second Kind
n
= 1 for n ≥ 1
n1 = 1 for n ≥ 0
nn n−1
− 1 for n ≥ 1
2 = 2
n(n−1)
n n
=
2 =
2
nn−1
= 0 if n 6= 0
n0 = 0 if k > n
nk 3 =???
Recursive Formula for
n
k
Consider a partition of [n] into k blocks.
Recursive Formula for
n
k
Consider a partition of [n] into k blocks.
Case 1: n is in a singleton block. Then when we remove n, we
get a partition of [n − 1] into k − 1 blocks. Start with a
partition of [n − 1] into k − 1 blocks and create
a new block
consisting of only n. Thus, there are n−1
such
partitions.
k−1
Recursive Formula for
n
k
Consider a partition of [n] into k blocks.
Case 1: n is in a singleton block. Then when we remove n, we
get a partition of [n − 1] into k − 1 blocks. Start with a
partition of [n − 1] into k − 1 blocks and create
a new block
consisting of only n. Thus, there are n−1
such
partitions.
k−1
Case 2: n is not in a singleton block. Then when we remove
n, we get a partition of [n − 1] into k blocks. Start with a
partition of [n − 1] into k blocks and choose any of the k
blocks to add the element n to. Thus, there are k n−1
such
k
partitions.
Recursive Formula for
n
k
Consider a partition of [n] into k blocks.
Case 1: n is in a singleton block. Then when we remove n, we
get a partition of [n − 1] into k − 1 blocks. Start with a
partition of [n − 1] into k − 1 blocks and create
a new block
consisting of only n. Thus, there are n−1
such
partitions.
k−1
Case 2: n is not in a singleton block. Then when we remove
n, we get a partition of [n − 1] into k blocks. Start with a
partition of [n − 1] into k blocks and choose any of the k
blocks to add the element n to. Thus, there are k n−1
such
k
partitions.
Altogether,
n
k
=
n−1 k−1
+k
n−1 k
.
Recursive Formula for
n
k
n
We
can
compute
the recurrence relation
k n−1from
n n−1 and initial conditions
+k k
=
k
0 k−1
= 1,
0n 0 = n = 0 for n ≥ 1.
0
Recursive Formula for
n
k
n
We
can
compute
the recurrence relation
k n−1from
n n−1 and initial conditions
+k k
=
k
0 k−1
= 1,
0n 0 = n = 0 for n ≥ 1.
0
The Stirling numbers can be put into a triangle similar to the
way that the binomial coefficients nk can be written in
Pascal’s Triangle. The binomial
satisfy a similar
coefficients
n−1
recurrence relation nk = n−1
+
with
similar initial
k−1
k
conditions
n
= 1 for n ≥ 0,
0
0
= 0 for n ≥ 1.
n
Where
n
k
Arises
∞
(ex − 1)k X n n o xn
=
k!
k n!
n=0
Where
n
k
Arises
∞
(ex − 1)k X n n o xn
=
k!
k n!
n=0
This is an example of an exponential generating
n function,
which can be used to derive formulas for k for fixed k.
Where
n
k
Arises
∞
(ex − 1)k X n n o xn
=
k!
k n!
n=0
This is an example of an exponential generating
n function,
which can be used to derive formulas for k for fixed k.
Example
k=1
∞ n o n
X
n x
n=0
1
n!
= ex − 1 =
∞
X
xn
n=1
n!
Where
n
k
Arises
∞
(ex − 1)k X n n o xn
=
k!
k n!
n=0
This is an example of an exponential generating
n function,
which can be used to derive formulas for k for fixed k.
Example
k=1
∞ n o n
X
n x
n=0
Conclusion:
n
1
1
n!
= ex − 1 =
= 1 except that
∞
X
xn
n=1
0
1
=0
n!
Where
n
k
Arises
∞
(ex − 1)k X n n o xn
=
k!
k n!
n=0
Example
k=3
∞ n o n
X
n x
n=0
3
n!
=
(ex − 1)3
e3x − 3e2x + 3ex − 1
=
3!
6
Where
n
k
Arises
∞
(ex − 1)k X n n o xn
=
k!
k n!
n=0
Example
k=3
∞ n o n
X
n x
n=0
3
n!
=
(ex − 1)3
e3x − 3e2x + 3ex − 1
=
3!
6
1
=
6
∞
X
3n xn
n=0
n!
−3
∞
X
2n xn
n=0
n!
+3
∞
X
xn
n=0
n!
!
−1
Where
n
k
Arises
∞
(ex − 1)k X n n o xn
=
k!
k n!
n=0
Example
k=3
∞ n o n
X
n x
n=0
3
n!
=
(ex − 1)3
e3x − 3e2x + 3ex − 1
=
3!
6
1
=
6
Conclusion:
n
3
=
∞
X
3n xn
n=0
n!
3n −3(2)n +3
6
−3
∞
X
2n xn
n=0
=
3n−1 +1
2
n!
+3
∞
X
xn
n=0
n!
!
−1
− 2n−1 for n ≥ 1.
Explicit Formula for
n
k
Expanding (ex − 1)k using the binomial theorem gives
nno
k
k
1 X
k−j k
=
(−1)
j n.
k! j=0
j
Explicit Formula for
n
k
Expanding (ex − 1)k using the binomial theorem gives
nno
k
k
1 X
k−j k
=
(−1)
j n.
k! j=0
j
The n = 0 case gives the well-known identity
k
P
(−1)j
j=0
for k ≥ 1.
k
j
=0
Where
n
k
Arises
Used to change from basis {1, x, x2 , x3 , . . . } to the basis
{1, x, x(x − 1), x(x − 1)(x − 2), . . . } for R[x].
Where
n
k
Arises
Used to change from basis {1, x, x2 , x3 , . . . } to the basis
{1, x, x(x − 1), x(x − 1)(x − 2), . . . } for R[x].
Example
x5 =
x
+ 15x(x − 1)
+ 25x(x − 1)(x − 2)
+ 10x(x − 1)(x − 2)(x − 3)
+
x(x − 1)(x − 2)(x − 3)(x − 4)
Poisson Distribution
For a random variable X with a Poisson distribution and
expected value λ, the nth moment of X is
n
E(X ) =
n n o
X
n
k=1
for n ≥ 1.
k
λk
Where
n
k
Arises
f (x) = ee
x
Where
n
k
Arises
x
f (x) = ee
x
f 0 (x) = ee (ex )
Where
n
k
Arises
x
f (x) = ee
x
f 0 (x) = ee (ex )
x
f 00 (x) = ee ex + e2x
Where
n
k
f (x)
f 0 (x)
f 00 (x)
f 000 (x)
Arises
=
=
=
=
x
ee
x
ee (ex )
x
ee ex + e2x
x
ee ex + 3e2x + e3x
Where
n
k
f (x)
f 0 (x)
f 00 (x)
f 000 (x)
Arises
=
=
=
=
x
ee
x
ee (ex )
x
ee ex + e2x
x
ee ex + 3e2x + e3x
f (4) (x) = ee
x
ex + 7e2x + 6e3x + e4x
Where
n
k
f (x)
f 0 (x)
f 00 (x)
f 000 (x)
Arises
=
=
=
=
x
ee
x
ee (ex )
x
ee ex + e2x
x
ee ex + 3e2x + e3x
f (4) (x) = ee
x
ex + 7e2x + 6e3x + e4x
f (5) (x) = ee
x
ex + 15e2x + 25e3x + 10e4x + e5x
Where
n
k
f (x)
f 0 (x)
f 00 (x)
f 000 (x)
Arises
=
=
=
=
x
ee
x
ee (ex )
x
ee ex + e2x
x
ee ex + 3e2x + e3x
f (4) (x) = ee
x
ex + 7e2x + 6e3x + e4x
f (5) (x) = ee
x
ex + 15e2x + 25e3x + 10e4x + e5x
f
(n)
(x) = e
ex
n n o
X
n
k=0
k
ekx
Bell Numbers
The sum
n P
n
k=0
k
counts all partitions of an n-element set.
This is called the nth Bell number, denoted Bn , named for Eric
Temple Bell (1883-1960).
B0 = 1
B1 = 1
B2 = 2
B3 = 5
B4 = 15
B5 = 52
B6 = 203
B7 = 877
B8 = 4140
B9 = 21147
What’s Counted by Bell Numbers?
Equivalence relations on an n-element set.
Ways to divide a class of n people into groups (a "group"
may have just one person).
Rhyme Schemes
Two roads diverged in a yellow wood,
And sorry I could not travel both
And be one traveler, long I stood
And looked down one as far as I could
To where it bent in the undergrowth;
(A)
(B)
(A)
(A)
(B)
From Robert Frost’s "The Road Not Taken" (1916)
Multiplicative Partitions
A multiplicative partition of an integer n is a way to write n as
a product of integers > 1, up to the order of the factors.
The number of multiplicative partitions of a squarefree integer
with k prime factors is Bk .
Example
30
2 · 15
3 · 10
5·6
2·3·5
Multiplicative Partitions
A multiplicative partition of an integer n in a way to write n
as a product of integers > 1, up to the order of the factors.
The number of multiplicative partitions of a squarefree integer
with k prime factors is Bk .
Example
30
2 · 15
3 · 10
5·6
2·3·5
←→
←→
←→
←→
←→
235
2|35
3|25
5|23
2|3|5
Recursive Formula for Bell Numbers
To make a partition of [n + 1], first choose which k elements of
[n] are in the same block as n + 1. It is clear that 0 ≤ k ≤ n.
Then choose any partition on the remaining n − k elements.
Recursive Formula for Bell Numbers
To make a partition of [n + 1], first choose which k elements of
[n] are in the same block as n + 1. It is clear that 0 ≤ k ≤ n.
Then choose any partition on the remaining n − k elements.
Bn+1 =
n X
n
k=0
k
Bn−k
Recursive Formula for Bell Numbers
To make a partition of [n + 1], first choose which k elements of
[n] are in the same block as n + 1. It is clear that 0 ≤ k ≤ n.
Then choose any partition on the remaining n − k elements.
Bn+1 =
n X
n
k=0
k
Bn−k
A simpler form of this
arises
from replacing k with n − k and
n
n
using the identity k = n−k .
Bn+1
n X
n
=
Bk
k
k=0
Together with the initial condition B0 = 1, the Bell numbers
are defined.
Exponential Generating Function for Bell Numbers
ex −1
e
=
∞
X
Bn
n=0
n!
xn
Exponential Generating Function for Bell Numbers
ex −1
e
=
∞
X
Bn
n!
xn
n=0
This can be shown directly from either one of the following
facts from earlier:
(ex −1)k
k!
=
dn
dxn
e
ex
∞ n
P
n x
k
n=0
=e
ex
n!
n P
n
k=0
k
ekx
Explicit Formulas for Bell Numbers
Explicit Formula #1: Bn =
n P
n
k=0
k
Explicit Formulas for Bell Numbers
Explicit Formula #1: Bn =
Explicit Formula #2: Bn =
n P
n
k
k=0
∞ n
P
1
k
e
k!
k=0
(Dobiński’s Formula)
A direct consequence of Dobiński’s Formula is that Bn is
the nth moment of a Poisson distribution with expected
value 1.
Ordered Set Partitions
Definition
An ordered partition of a finite set S is an ordered collection of
disjoint nonempty blocks A1 , . . . , Ak such that
S = A1 ∪ · · · ∪ Ak .
Ordered Set Partitions
Definition
An ordered partition of a finite set S is an ordered collection of
disjoint nonempty blocks A1 , . . . , Ak such that
S = A1 ∪ · · · ∪ Ak .
Example
13|2|45, 13|45|2, 2|13|45, 2|45|13, 45|13|2, 45|2|13 are
different ordered partitions of [5] corresponding to the same
(unordered) partition.
Ordered Set Partitions
Theorem
The numberofordered partitions of an n element set into k
blocks is k! nk .
Ordered Set Partitions
Theorem
The numberofordered partitions of an n element set into k
blocks is k! nk .
Example
14 ordered partitions of [4] into two blocks.
12|34
34|12
13|24
24|13
14|23
23|14
123|4
4|123
124|3
3|124
134|2
2|134
234|1
1|234
Counting Surjective Functions
Theorem
The number of surjective functions from [n] to [k] is k!
n
.
k
Example
The surjective function f : [9] → [4] defined by
1 7→ 2
4 7→ 1
7 7→ 2
2 7→ 3
5 7→ 3
8 7→ 4
3 7→ 3
6 7→ 4
9 7→ 3
corresponds to the ordered partition 4|17|2359|68 of [9]. The
surjectivity property is equivalent to the requirement that
blocks be nonempty.
If we didn’t require surjectivity, there would be k n functions.
Balls into Boxes
Theorem
The total number of ways to distribute n (distinguishable)
balls into k (distinguishable)
boxes such that every box has at
n
least one ball is k! k .
The Sequence of Fubini Numbers
The number of ordered partitions on [n] is Fubn =
n
P
k=0
k!
n
k
called the sequence of Fubini numbers (also called ordered Bell
numbers).
Fub0 = 1
Fub1 = 1
Fub2 = 3
Fub3 = 13
Fub4 = 75
Fub5 = 541
Fub6 = 4683
Fub7 = 47293
Fub8 = 545835
Fubini’s Theorem
Guido Fubini (1879-1943)
Z
B




Z
Z Z
ZZ
 f (x, y)dx dy =  f (x, y)dy  dx =
f (x, y)d(x×y)
A
A
B
A×B
Fubini’s Theorem
R
R R
R
R R
f (x, y, z)dx dy dz
f (x, y, z)dx dz dy
B C A
R R R
f (x, y, z)dy dx dz
f (x, y, z)dy dz dx
C A B
A C B
R R R
R R R
f (x, y, z)dz dx dy
f (x, y, z)dz dy dx
B A C
A B C
!
!
R RR
R RR
f (x, y, z)d(x × y) dz
f (x, y, z)d(x × z) dy
C A×B
B A×C
!
R RR
RR R
f (x, y, z)dz d(x × y)
f (x, y, z)d(y × z) dx
A×B C
A B×C
RR R
RR R
f (x, y, z)dy d(x × z)
f (x, y, z)dx d(y × z)
A×C B
B×C
A
RRR
f (x, y, z)d(x × y × z)
C
B A
R R R
A×B×C
Weak Orderings
Fubn counts the weak orderings on a set with n elements.
Weak Orderings
Fubn counts the weak orderings on a set with n elements.
a<b<c
a<c<b
b<a<c
b<c<a
c<a<b
c<b<a
a<b=c
b<a=c
c<a=b
a=b<c
a=c<b
b=c<a
a=b=c
Weak Orderings
Suppose there are n people (or teams, etc.) in a race.
Assuming no ties, there are n! possible orders they can finish
in (strict orderings).
What if ties are allowed?
Weak Orderings
Suppose there are n people (or teams, etc.) in a race.
Assuming no ties, there are n! possible orders they can finish
in (strict orderings).
What if ties are allowed? This is weak orderings!
2013 American League East Division Standings
Wins
Boston Red Sox
97
Tampa Bay Rays
92
Baltimore Orioles
85
New York Yankees
85
Toronto Blue Jays
74
Losses
65
71
77
77
88
Percent
.599
.564
.525
.525
.457
Recursive Formula for Fubn
Consider the first block in an ordered partition of [n].
Recursive Formula for Fubn
Consider the first block in an ordered partition of [n].
If the first block has k elements, then the rest of the
blocks can be any ordered partition on the set of n − k
remaining items.
Recursive Formula for Fubn
Consider the first block in an ordered partition of [n].
If the first block has k elements, then the rest of the
blocks can be any ordered partition on the set of n − k
remaining items.
Therefore, there are nk Fubn−k ordered partitions of [n]
in which the first block has k elements.
Recursive Formula for Fubn
Consider the first block in an ordered partition of [n].
If the first block has k elements, then the rest of the
blocks can be any ordered partition on the set of n − k
remaining items.
Therefore, there are nk Fubn−k ordered partitions of [n]
in which the first block has k elements.
Fubn =
n X
n
k=1
k
Fubn−k
More Formulas for Fubn
Exponential Generating Function:
∞
X
Fubn n
1
=
x
2 − ex
n!
n=0
Explicit Formula #1:
Fubn =
n
X
k=0
k!
nno
k
Explicit Formula #2:
∞
X
kn
Fubn =
2k+1
k=0
Asymptotic Formula:
Fubn ∼
n!
2(ln 2)n+1
More Formulas for Fubn
How good of approximation is
n!
?
2(ln 2)n+1
More Formulas for Fubn
How good of approximation is
n
1
2
3
4
5
6
7
n!
?
2(ln 2)n+1
n!
2(ln 2)n+1
1.0406845
3.0027807
12.996291
74.998735
541.00152
4683.0012
47292.999
Fubn
1
3
13
75
541
4683
47293
Simplex Lock Problem
Simplex Lock Problem
There are n ≥ 1 buttons.
A combination consists of pressing some sequence of
buttons, but some sets of buttons may need to be pressed
simultaneously.
No button may be pressed more than once in a
combination.
Simplex Lock Problem
There are n ≥ 1 buttons.
A combination consists of pressing some sequence of
buttons, but some sets of buttons may need to be pressed
simultaneously.
No button may be pressed more than once in a
combination.
How many combinations are there?
Simplex Lock Problem
It’s like ordered set partitions except that not every
button needs to be in a combination.
Simplex Lock Problem
It’s like ordered set partitions except that not every
button needs to be in a combination.
Pick a subset S of the buttons, and then pick one of the
Fub#S ordered partitions on S.
Simplex Lock Problem
It’s like ordered set partitions except that not every
button needs to be in a combination.
Pick a subset S of the buttons, and then pick one of the
Fub#S ordered partitions on S.
For simplicity, we allow S = ∅.
Simplex Lock Problem
It’s like ordered set partitions except that not every
button needs to be in a combination.
Pick a subset S of the buttons, and then pick one of the
Fub#S ordered partitions on S.
For simplicity, we allow S = ∅.
If S has k elements, then nk ways to choose S and then
Fubk combinations using all the buttons in S.
Simplex Lock Problem
It’s like ordered set partitions except that not every
button needs to be in a combination.
Pick a subset S of the buttons, and then pick one of the
Fub#S ordered partitions on S.
For simplicity, we allow S = ∅.
If S has k elements, then nk ways to choose S and then
Fubk combinations using all the buttons in S.
Thus, nk Fubk combinations that use exactly k buttons.
Simplex Lock Problem
Adding this up over 0 ≤ k ≤ n, the number of
combinations is
n X
n
Fubk .
k
k=0
Simplex Lock Problem
Adding this up over 0 ≤ k ≤ n, the number of
combinations is
n X
n
Fubk .
k
k=0
Let’s remember the recurrence relation for the Fubini
numbers.
n X
n
Fubn−k
Fubn =
k
k=1
Simplex Lock Problem
Adding this up over 0 ≤ k ≤ n, the number of
combinations is
n X
n
Fubk .
k
k=0
Let’s remember the recurrence relation for the Fubini
numbers.
n n X
X
n
n
Fubn−k =
Fubn =
Fubn−k
k
n−k
k=1
k=1
Simplex Lock Problem
Adding this up over 0 ≤ k ≤ n, the number of
combinations is
n X
n
Fubk .
k
k=0
Let’s remember the recurrence relation for the Fubini
numbers.
n n X
X
n
n
Fubn−k =
Fubn =
Fubn−k
k
n−k
k=1
k=1
n−1 X
n
=
Fubk
k
k=0
Simplex Lock Problem
The number of combinations of the n-button simplex lock is
n X
n
k=0
n−1 X
n
n
Fubk =
Fubn +
Fubk = 2 Fubn .
k
n
k
k=0
Simplex Lock Problem
The number of combinations of the n-button simplex lock is
n X
n
k=0
n−1 X
n
n
Fubk =
Fubn +
Fubk = 2 Fubn .
k
n
k
k=0
Question: Is there an intuitive reason for this formula?
Simplex Lock Problem
Split it up into two disjoint cases.
Case 1: All buttons are used. Then there are Fubn such
combinations.
Simplex Lock Problem
Split it up into two disjoint cases.
Case 1: All buttons are used. Then there are Fubn such
combinations.
Case 2: Not all buttons are used.
Simplex Lock Problem
Split it up into two disjoint cases.
Case 1: All buttons are used. Then there are Fubn such
combinations.
Case 2: Not all buttons are used. Then we can define a
bijection between combinations in which not every button
is used and ordered partitions of [n] by defining a new last
block consisting of the unused buttons. So there are
Fubn such combinations.
References
Sloane, N. J. A. "A000110 - OEIS." http://oeis.org/A000110
Sloane, N. J. A. "A000670 - OEIS." http://oeis.org/A000110
Sloane, N. J. A. "A008277 - OEIS." http://oeis.org/A008277
Stanley, Richard P. Enumerative Combinatorics. Second ed. Vol. 1. New
York: Cambridge UP, 2012. Print.
Weisstein, Eric W. “Dobiński’s Formula." From MathWorld–A Wolfram
Web Resource. http://mathworld.wolfram.com/DobinskisFormula.html
Weisstein, Eric W. “Stirling Number of the Second Kind." From
MathWorld–A Wolfram Web Resource.
http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html