问题描述:

Forgive me if this is better suited to MathOverflow, but my question is probably too simple to put there.

I'm reading S.K Lando's *Lectures on Generating Functions*, which gives this definition of the product of two generating functions **A** and **B**:

`A(s)*B(s) = a0*b0 + (a0*b1 + a1*b0)*s + (a0*b2 + a1*b1 + a2*b0)*s^2 ...`

I understand that the ** s** is just formal. But - and I know it's obtuse of me - I can't understand how the pattern of terms combining coefficients should continue. If anyone could just extend the definition to one or two more terms, it would probably help me a lot. Many thanks!

For bonus points, an algorithm in Haskell for multiplying two series (represented as lists of coefficients) would be much appreciated too - but it'd be enough for me just to understand the above definition.

Notice that the sum of the coefficient indices is constant in each term. For example `a0*b0 -> 0+0=0`

, while `a0*b1 -> 0+1=1`

and `a1*b0 -> 1+0=1`

.

Recall the story of young Gauss, who discovered that by summing a list of consecutive numbers with its reverse, we obtain a list of *constants*. The same trick applies here. We'll just take the first k `a_i`

and `b_i`

coefficients, reverse the list of `b_i`

coefficients, and take the component-wise product of the lists.

Here's some Haskell code to generate the coefficient of `s^i`

for `i>=0`

, given `i`

and the list of `as=[a0,a1,...]`

and `bs=[b0,b1,...]`

:

```
genCoeff :: [Double] -> [Double] -> Int -> Double
genCoeff as bs i = sum $ zipWith (*) (take (i+1) as) (reverse (take (i+1) bs))
```

To generate all of the coefficients, we simply map the partially applied function `genCoeff as bs`

onto the list `[0,1,...]`

, i.e.

```
genAllCeoffs :: [Double] -> [Double] -> [Double]
genAllCoeffs as bs = map (genCoeff as bs) [0..]
```

Here is a solution which doesn't use `reverse`

:

```
add [] bs = bs
add as [] = as
add (a:as) (b:bs) = (a+b) : add as bs
mult :: [Int] -> [Int] -> [Int]
mult [] bs = [] -- note: [] = 0
mult as [] = []
mult (a:as) (b:bs) = (a*b) : add (add (map (*a) bs) (map (*b) as)) (0:mult as bs)
test1 = do
let as = [1,2,3]
bs = [4,5]
putStrLn $ "as = " ++ show as
putStrLn $ "bs = " ++ show bs
putStrLn $ "as * bs = " ++ show (mult as bs)
```

Output:

```
as = [1,2,3]
bs = [4,5]
as * bs = [4,13,22,15]
```

It was derived from the following identity:

```
(a0+a1*x) * (b0 + b1*x) = a0*b0 + a0*b1*x + b0*a1*x + a1*b1*x^2
```

The correspondences are:

```
a0*b0 <-> a*b
a0*b1*x <-> map (*a) bs
b0*a1*x <-> map (*b) as
a1*b1*x^2 <-> (0:mult as bs)
```