Information Technology Reference
In-Depth Information
Similarly, a
partition
of [
n
]isan
unordered
list of
nonempty
disjoint subsets of [
n
]
whose union is [
n
], and a
weak partition
of [
n
]isan
unordered
list of disjoibt subsets
of [
n
] whose union is [
n
].
k
-partitions and
k
-compositions are defined as expected.
Example 4.
The weak 3-partitions of [2]:
P
2
,
3
=
.
Counting the (weak/strong)(compositions/partitions) of (integers/sets) is a
charming problem in elementary enumerative combinatorics, reminiscent of
Rota's “Twelvefold Way” [5]. Some of the solutions are given in Table 1.
{{
1
,
2
}
,
∅
,
∅}
,
{{
1
}
,
{
2
}
,
∅}
3
A Curious Class of Partitions
Finally, we define a curious class of weak integer partitions that arises in the study
of the Taylor series of inverse functions (the fourth and fifth lines of Table 2). It
can be defined recursively, as follows:
V
0
:=
∅
V
n
:=
P
n
∪
(
V
n−
1
∗
0)
for
n
≥
1
And nonrecursively:
V
0
=
∅
V
1
=
{
1
,
0
}
V
2
=
{
2
,
11
,
10
,
00
}
V
3
=
{
3
,
21
,
111
,
20
,
110
,
100
,
000
}
V
4
=
{
4
,
31
,
22
,
211
,
1111
,
30
,
210
,
1110
,
200
,
1100
,
1000
,
0000
}
.
V
n
=
n
0
j
P
n−j
∗
j
=0
4The
D
Operator
Definition.
If
λ
=
{{
λ
1
,...,λ
k
}}
is an integer partition, then
Dλ
=
{{λ
1
+1
,...,λ
k
+1
}}
DV
0
=
∅
DV
1
=
{
2
,
1
}
DV
2
=
{
3
,
22
,
21
,
11
}
DV
3
=
{
4
,
32
,
222
,
31
,
221
,
211
,
111
}
.
DV
n
=
DP
n
∪ DV
n
−
1
∗
1+
···
5
More Definitions and Notation
P
n,k
,andlet
m
be its multiplicity function:
m
p
(
λ
)=
|{i
:1
≤ i ≤ k, λ
i
=
p}|
Let
λ
=
{{
λ
1
,...,λ
k
}}
∈
for
p
∈
Z
=0
,...,n
.
