Information Technology Reference
In-Depth Information
However, finding the
n
th derivative of even the simplest
F
(
z
)maynotbeeasy
(try
F
(
z
)=
e
e
z
). Still, if
F
(
z
) is a hybrid of two or more simpler functions, a
divide and conquer approach can be helpful. For example, if
F
(
z
)=
F
1
(
z
)
F
2
(
z
),
the well-known rule of Leibniz shows how the Taylor coecients of
F
(
z
)canbe
obtained from those of
F
1
(
z
)and
F
2
(
z
):
n
k
f
1
[
k
]
f
2
[
n
n
f
[
n
]=
−
k
] or
n
≥
0.
.
(2)
k
=0
This formula requires
n
additions and
n
multiplications to compute
f
[
n
]. Another
expression for
f
[
n
]is
f
[
n
]=
S⊆
[
n
]
S
c
f
1
[
|
S
|
]
f
2
[
|
|
]
,
(3)
where the summation in 3 is over all 2
n
subsets of [
n
]=
{
1
,...,n
}
, thus requiring
2
n
additions and 2
n
multiplications to compute
f
[
n
]. To distinguish the two
expressions, let us call them
f
A
[
n
]and
f
B
[
n
].
f
A
[
n
] simpler but redundant;
f
B
[
n
]
is more complicated but compact. One suspects that expression
A
will be useful
for proving theorems but expression
B
will be preferable for computations. Note
also that both formulas seem sommehow combinatorial.
What is true for the Leibniz rule is true in considerable generality. We have
found many other “(
A
,
B
),” pairs, and in every case, the resulting formulae are
essentially combinatorial; thus the derived
calculus
problem becomes again a
combinatorial
problem. In this paper, which is mostlly, but not entirely, tutorial,
we will discuss a number of instances of this phenomenon (see Table 2).
2
Compositions and Partitions of Integers and Finite Sets
In this section we will define the combinatorial objects we need to describe our
formulae for inverse Taylor series. The impatient reader is invited to skip ahead
to Table 1 where this material is summarized.
Let
n
and
k
be positive integers. A
composition of
n
is an
ordered
list of
positive
integers whose sum is
n
.A
weak composition of
n
is an
ordered
list of
nonnegative
integers whose sum is
n
.A
k
-composition of
n
is a com-
position of
n
with exactly
k
parts A
weak
k
-composition of
n
is an ordered
list of
k
nonnegative integers whose sum is
n
.
Example 1.
The weak 2-compositions of 4 are:
C
4
,
2
=(4
,
0)
,
(3
,
1)
,
(2
,
2)
,
(1
,
3)
,
(0
,
4)
.
A
partition
of
n
is an
unordered
list (multiset) of
positive
integers whose
sum is
n
.A
weak partition
of
n
is an
unordered
list of
nonnegative
integers
whose sum us
n
.A
k
-partition
of
n
is an
unordered
list of
k
positive
integers
