Information Technology Reference
In-Depth Information
whose sum is
n
.A
weak
k
-partition
of
n
is an
unordered
list of
k
nonnegative
integers whose sum is
n
.
Example 2.
The 2-partitions of 4:
P
4
,
2
=
{{
3
,
1
}}
,
{{
2
,
2
}}
.
A
composition
of [
n
]=
is an
ordered
list of pairwise disjoint
nonempty
subsets of [
n
] whose union is
n
.A
weak composition
of [
n
]is
an
ordered
list of pairwise disjoint subsets of [
n
] whose union is [
n
]. A
k
-
composition of [
n
] is an ordered list of
k
nonempty subsets of [
n
] whose union
is [
n
]. A
weak
k
-composition of [
n
] is an ordered list of
k
disjoint subsets of [
n
]
whose union is
n
.
{
1
,...,n
}
Example 3.
The weak 2-compositions of [2]:
C
2
,
2
=(
{
1
,
2
}
,
∅
)
,
(
{
1
}
,
{
2
}
)
,
(
{
2
}
,
{
1
}
)
,
(
∅
,
{
1
,
2
}
)
.
Table 1.
Twelve Combinatorial Structures
1
2
3
4
5
6
S
:
C
n
C
n,k
C
n,k
P
n,k
S
:
P
P
(
−
1)
k−j
k
j
j
n
n
n,k
O
n
j
S
n,k
j
=1
S
n,j
|S|
:
k
n
|
S
|
:
B
n
7
8
9
10
11
12
C
n,k
P
n,k
S
:
C
n
C
n,k
S
:
P
n
P
n,k
n−
1
k
1
n
+
k−
1
1
p
k
(
n
)
j
=1
p
j
(
n
)
:
n−
1
|
S
|
|
S
|
:
p
(
n
)
−
k
−
Legend
:
C
n
compositions of [
n
]
P
n
partitions of [
n
]
C
n,k
k
-compositions of [
n
]
P
n,k
k
-partitions of [
n
]
C
n,k
weak
k
-compositions of [
n
]
P
n,k
weak
k
-partitions of [
n
]
C
n
compositions of
n
P
n
partitions of
n
C
n,k
k
-compositions of
n
P
n,k
k
-partitions of
n
C
n,k
weak
k
-compositions of
n
n,k
weak
k
-partitions of
n
p
(
n
)
number of partitions of
np
k
(
n
)number of
k
-partitions of
n
B
n
Number of partitions of [
n
]
S
n,k
number of
k
-partitions of [
n
]
(Bell number)
(Stirling Number second kind)
1)
k−j
j
j
n
O
n,k
j
(
O
n
ordered Bell number
−
