combinat-0.2.7.2: Generate and manipulate various combinatorial objects.

Math.Combinat.Numbers.Series

Description

Some basic univariate power series expansions. This module is not re-exported by Math.Combinat.

Note: the "`convolveWithXXX`" functions are much faster than the equivalent `(XXX `convolve`)`!

TODO: better names for these functions.

Synopsis

# Trivial series

unitSeries :: Num a => [a] Source

The series [1,0,0,0,0,...], which is the neutral element for the convolution.

zeroSeries :: Num a => [a] Source

Constant zero series

constSeries :: Num a => a -> [a] Source

Power series representing a constant function

idSeries :: Num a => [a] Source

The power series representation of the identity function `x`

powerTerm :: Num a => Int -> [a] Source

The power series representation of `x^n`

# Basic operations on power series

addSeries :: Num a => [a] -> [a] -> [a] Source

subSeries :: Num a => [a] -> [a] -> [a] Source

negateSeries :: Num a => [a] -> [a] Source

scaleSeries :: Num a => a -> [a] -> [a] Source

mulSeries :: Num a => [a] -> [a] -> [a] Source

productOfSeries :: Num a => [[a]] -> [a] Source

# Convolution (product)

convolve :: Num a => [a] -> [a] -> [a] Source

Convolution of series (that is, multiplication of power series). The result is always an infinite list. Warning: This is slow!

convolveMany :: Num a => [[a]] -> [a] Source

Convolution (= product) of many series. Still slow!

# Reciprocals of general power series

reciprocalSeries :: (Eq a, Fractional a) => [a] -> [a] Source

Given a power series, we iteratively compute its multiplicative inverse

integralReciprocalSeries :: (Eq a, Num a) => [a] -> [a] Source

Given a power series starting with `1`, we can compute its multiplicative inverse without divisions.

# Composition of formal power series

composeSeries :: (Eq a, Num a) => [a] -> [a] -> [a] Source

`g `composeSeries` f` is the power series expansion of `g(f(x))`. This is a synonym for `flip substitute`.

We require that the constant term of `f` is zero.

substitute :: (Eq a, Num a) => [a] -> [a] -> [a] Source

`substitute f g` is the power series corresponding to `g(f(x))`. Equivalently, this is the composition of univariate functions (in the "wrong" order).

Note: for this to be meaningful in general (not depending on convergence properties), we need that the constant term of `f` is zero.

# Lagrange inversions

Coefficients of the Lagrange inversion

integralLagrangeInversion :: (Eq a, Num a) => [a] -> [a] Source

We expect the input series to match `(0:1:_)`. The following is true for the result (at least with exact arithmetic):

```substitute f (integralLagrangeInversion f) == (0 : 1 : repeat 0)
substitute (integralLagrangeInversion f) f == (0 : 1 : repeat 0)```

lagrangeInversion :: (Eq a, Fractional a) => [a] -> [a] Source

We expect the input series to match `(0:a1:_)`. with a1 nonzero The following is true for the result (at least with exact arithmetic):

```substitute f (lagrangeInversion f) == (0 : 1 : repeat 0)
substitute (lagrangeInversion f) f == (0 : 1 : repeat 0)```

# Power series expansions of elementary functions

expSeries :: Fractional a => [a] Source

Power series expansion of `exp(x)`

cosSeries :: Fractional a => [a] Source

Power series expansion of `cos(x)`

sinSeries :: Fractional a => [a] Source

Power series expansion of `sin(x)`

coshSeries :: Fractional a => [a] Source

Power series expansion of `cosh(x)`

sinhSeries :: Fractional a => [a] Source

Power series expansion of `sinh(x)`

log1Series :: Fractional a => [a] Source

Power series expansion of `log(1+x)`

dyckSeries :: Num a => [a] Source

Power series expansion of `(1-Sqrt[1-4x])/(2x)` (the coefficients are the Catalan numbers)

# "Coin" series

coinSeries :: [Int] -> [Integer] Source

Power series expansion of

`1 / ( (1-x^k_1) * (1-x^k_2) * ... * (1-x^k_n) )`

Example:

`(coinSeries [2,3,5])!!k` is the number of ways to pay `k` dollars with coins of two, three and five dollars.

TODO: better name?

coinSeries' :: Num a => [(a, Int)] -> [a] Source

Generalization of the above to include coefficients: expansion of

`1 / ( (1-a_1*x^k_1) * (1-a_2*x^k_2) * ... * (1-a_n*x^k_n) ) `

convolveWithCoinSeries' :: Num a => [(a, Int)] -> [a] -> [a] Source

# Reciprocals of products of polynomials

productPSeries :: [[Int]] -> [Integer] Source

Convolution of many `pseries`, that is, the expansion of the reciprocal of a product of polynomials

productPSeries' :: Num a => [[(a, Int)]] -> [a] Source

The same, with coefficients.

convolveWithProductPSeries' :: Num a => [[(a, Int)]] -> [a] -> [a] Source

This is the most general function in this module; all the others are special cases of this one.

# Reciprocals of polynomials

pseries :: [Int] -> [Integer] Source

The power series expansion of

`1 / (1 - x^k_1 - x^k_2 - x^k_3 - ... - x^k_n)`

convolveWithPSeries :: [Int] -> [Integer] -> [Integer] Source

Convolve with (the expansion of)

`1 / (1 - x^k_1 - x^k_2 - x^k_3 - ... - x^k_n)`

pseries' :: Num a => [(a, Int)] -> [a] Source

The expansion of

`1 / (1 - a_1*x^k_1 - a_2*x^k_2 - a_3*x^k_3 - ... - a_n*x^k_n)`

convolveWithPSeries' :: Num a => [(a, Int)] -> [a] -> [a] Source

Convolve with (the expansion of)

`1 / (1 - a_1*x^k_1 - a_2*x^k_2 - a_3*x^k_3 - ... - a_n*x^k_n)`

convolveWithSignedPSeries :: [(Sign, Int)] -> [Integer] -> [Integer] Source

Convolve with (the expansion of)

`1 / (1 +- x^k_1 +- x^k_2 +- x^k_3 +- ... +- x^k_n)`

Should be faster than using `convolveWithPSeries'`. Note: `Plus` corresponds to the coefficient `-1` in `pseries'` (since there is a minus sign in the definition there)!