问题描述:

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)
相关阅读:
Top