如何将两个生成级数相乘？

Question

如果这更适合 MathOverflow，请原谅我，但我的问题可能太简单了，无法放在那里。

我正在阅读 S.K Lando 的 生成函数讲座 ，其中给出了两个生成函数的乘积的定义 A 和 B:

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

我知道 s 只是正式的。但是——我知道这对我来说很迟钝——我不明白组合系数的模式应该如何继续。如果有人可以将定义扩展到一两个术语，那可能会对我有很大帮助。非常感谢！

对于奖励积分，Haskell 中用于将两个级数相乘的算法（表示为系数列表）也将非常受欢迎 - 但我只需要理解上述定义就足够了。

Answer 1

请注意，系数指数的总和在每一项中都是常数。例如 a0*b0 -> 0+0=0，而 a0*b1 -> 0+1=1 和 a1*b0 -> 1+0=1.

回想一下 story of young Gauss，他发现通过将连续数字列表与其倒数相加，我们得到一个 常数列表 。同样的技巧也适用于此。我们只取前 k 个 a_i 和 b_i 系数，反转 b_i 系数列表，然后取列表的分量乘积。

这里有一些 Haskell 代码，用于为 i>=0 生成 s^i 的系数，给定 i 以及 as=[a0,a1,...] 和 [=22= 的列表]:

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

要生成所有系数，我们只需将部分应用的函数 genCoeff as bs 映射到列表 [0,1,...]，即

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

Answer 2

这是一个不使用 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)

输出：

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

它源自以下身份：

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

对应关系是：

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

如何将两个生成级数相乘？

How do you multiply two generating series?

haskell

combinatorics