combinat-0.2.4.1: Generation of various combinatorial objects.Source codeContentsIndex
Math.Combinat.Numbers.Series
Contents
"Coin" series
Reciprocals of products of polynomials
Reciprocals of polynomials
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
unitSeries :: Num a => [a]
convolve :: Num a => [a] -> [a] -> [a]
convolveMany :: Num a => [[a]] -> [a]
coinSeries :: [Int] -> [Integer]
coinSeries' :: Num a => [(a, Int)] -> [a]
convolveWithCoinSeries :: [Int] -> [Integer] -> [Integer]
convolveWithCoinSeries' :: Num a => [(a, Int)] -> [a] -> [a]
productPSeries :: [[Int]] -> [Integer]
productPSeries' :: Num a => [[(a, Int)]] -> [a]
convolveWithProductPSeries :: [[Int]] -> [Integer] -> [Integer]
convolveWithProductPSeries' :: Num a => [[(a, Int)]] -> [a] -> [a]
pseries :: [Int] -> [Integer]
convolveWithPSeries :: [Int] -> [Integer] -> [Integer]
pseries' :: Num a => [(a, Int)] -> [a]
convolveWithPSeries' :: Num a => [(a, Int)] -> [a] -> [a]
data Sign
= Plus
| Minus
signValue :: Num a => Sign -> a
signedPSeries :: [(Sign, Int)] -> [Integer]
convolveWithSignedPSeries :: [(Sign, Int)] -> [Integer] -> [Integer]
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 :: [Int] -> [Integer] -> [Integer]Source
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 :: [[Int]] -> [Integer] -> [Integer]Source
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
show/hide Instances
signValue :: Num a => Sign -> aSource
signedPSeries :: [(Sign, Int)] -> [Integer]Source
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)!

Produced by Haddock version 2.6.1