Information Technology Reference
In-Depth Information
12
Proof of Entry 5 in Table 2
Follows from Three and Four. Details omitted.
13
Proof of Entry 8 in Table 2
The folowing theorem, which is a straightforward generalization of Stanley's
Thorem 5.1.4 [6], is nevertheless useful as a startign point for inverse multivari-
able multivariale Taylor series.
We begin by defining a
q
-chromatic partition of
n
to be a pair (
α, c
)con-
sisting of partition
α
=
{{
α
1
,...,α
k
}}
of
n
together with a coloring function
c
:
[
q
].
Note that repeated parts of the partition need not have the same color, but
that, for example the partition
{{
α
1
,...,α
k
}} →
of 2, could be 2-colored with one red 1
and one blue 1, both 1s red or both 1s blue, but that changing which 1 is red
and which 1 is blue does not make any distinction for a total of three possible
colorings.
Theorem.
Multi-variable Compositional Formula
{{
1
,
1
}}
Let
f
1
,...,f
q
:
be functions with exponential generating functions
F
1
,...,F
q
respectively. Assume that
f
1
[0] =
P
→
C
q
···
=
f
q
[0] = 0, and let
g
:
N
→
K
be such that
g
[0
,...,
0] = 0. Let
h
:
N
→
K
have
h
[0] = 0 and for all
n
≥
0,
l
(
α
)
h
[
n
]=
f
c
(
α
i
)
(
|
α
i
|
)
g
(
k
)
,
i
=1
where the sum is over all colored set partitions (
α, c
)of[
n
]and
k
=(
k
1
,...,k
q
)
is such that
k
j
is the number of parts of (
α, c
) of color
j
. Then,
H
(
z
)=
G
(
F
1
(
x
)
,...,F
q
(
x
))
.
q
, and assume (without loss of generality) that any colored
set partition is such that we have all parts of color 1 listed first, followed by all
parts of color 2 and so forth, ending with all parts of color
q
.Wecanthenuse
Table 2, entry 1, with
k
1
+
Proof:
Fix
k
∈
N
+
k
q
functions to prove the theorem. In table 2,
entry 1, let the functions that tell us the coecients of the exponential generating
functions be
a
1
,...,a
k
1
+
···
+
k
q
···
a
1
=
···
=
a
k
1
=
f
1
,
a
k
1
+1
=
···
=
a
k
1
+
k
2
=
f
2
,
and so on, up to
a
k
1
+
···
+
k
q−
1
=
···
=
a
k
1
+
···
+
k
q
=
f
q
.