Information Technology Reference
In-Depth Information
where the sum is over all compositions (ordered partitions) of the set [
n
]=
{
|
C
n
|
is enormous — for
n
= 10 it is 102247563 — so we seek elsewhere (Table 2.2B)
for a computationally ecient formula.
g
[
n
]=
λ∈P
n
1
,...,n
}
, i.e.,
α
=(
α
1
,...,α
k
), where
∅⊂
α
i
⊆
[
n
],
α
i
∩
α
j
=
∅
. However,
1)
|λ|
(
(
−
|
λ
|
+1)
A
(
λ
)
B
(
λ
)
f
[
λ
1
]
···
f
[
λ
k
]
(5)
This formula is more manageable - exactly 42 terms for
n
= 10. We present a
Tableau for computing
g
[1], . . .
g
[4] below.
1)
|λ|
λ
(
−
|
λ
|
+1
A
(
λ
)
B
(
λ
)Coeff.
n
=1
(1)
−
2
1
1
−
2
f
[1]
n
=2
(2)
−
2
1
1
−
2
f
[2]
f
[1]
2
(1
,
1)
+
3
2
1
+6
n
=3
(3)
−
2
1
1
−
2
f
[3]
(2
,
1)
+
3
3
2
+18
f
[2]
f
[1]
f
[1
3
(1
,
1
,
1)
−
4
6
1
−
24
n
=4
−
−
2
f
[4]
(4)
2
1
1
(3
,
1)
+
3
4
2
24
f
[3]
f
[1]
f
[2]
2
(2
,
2)
+
3
6
1
18
f
[2]
f
[1]
2
(2
,
1
,
1)
−
4
12
3
−
144
f
[1]
4
(1
,
1
,
1
,
1)
+
5
24
1
120
Thus
g
[0] = 1
g
[1] =
−
2
f
[2] + 6
f
[1
,
1]
.
g
[4] =
−
2
f
[4] + 24
f
[3
,
1] + 18
f
[2
,
2]
−
144
f
[2
,
1
,
1] + 120
f
[1
,
1
,
1
,
1]
If more generally, we asked for the Taylor series for
F
(
x
)
x
where
x
is an arbitrary
real number, we obtain
g
[0] =
x
0
g
[1] =
x
1
f
[1]
g
[2] =
x
1
f
[2] + 2
x
2
f
[1
,
1]