combinat-0.2.5.0: Generation of various combinatorial objects.

Safe Haskell None

Math.Combinat.Numbers.Series

Description

Some basic 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

# Documentation

unitSeries :: Num a => [a]Source

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

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

Convolution of series. The result is always an infinite list. Warning: This is slow!

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

Convolution of many series. Still slow!

# "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)
```

data Sign Source

Constructors

 Plus Minus

Instances

 Eq Sign Show Sign

signValue :: Num a => Sign -> aSource

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)!