Math.Combinat.Numbers.Sequences

Some important number sequences.

See the "On-Line Encyclopedia of Integer Sequences", https://oeis.org .

Factorial

factorial :: Integral a => a -> Integer

The factorial function (A000142).

factorialSplit :: Integral a => a -> Integer

Faster implementation of the factorial function

factorialNaive :: Integral a => a -> Integer

Naive implementation of factorial

factorialSwing :: Integral a => a -> Integer

"Swing factorial" algorithm

factorialPrimeExponents :: Int -> [(Integer, Int)]

Prime factorization of the factorial (using the "swing factorial" algorithm)

factorialPrimeExponentsNaive :: forall a. Integral a => a -> [(Integer, Int)]

factorialPrimeExponents_ :: Int -> [Int]

swingFactorialExponents_ :: Int -> [Int]

Prime factorizaiton of the "swing factorial" function)

doubleFactorial :: Integral a => a -> Integer

The double factorial

doubleFactorialSplit :: Integral a => a -> Integer

Faster implementation of the double factorial function

doubleFactorialNaive :: Integral a => a -> Integer

Naive implementation of the double factorial (A006882).

Binomial and multinomial

binomial :: Integral a => a -> a -> Integer

Binomial numbers (A007318). Note: This is zero for n<0 or k<0; see also signedBinomial below.

binomialSplit :: Integral a => a -> a -> Integer

Faster implementation of binomial

binomialNaive :: Integral a => a -> a -> Integer

A007318. Note: This is zero for n<0 or k<0; see also signedBinomial below.

signedBinomial :: Int -> Int -> Integer

The extension of the binomial function to negative inputs. This should satisfy the following properties:

for n,k >=0 : signedBinomial n k == binomial n k
for any n,k : signedBinomial n k == signedBinomial n (n-k) 
for k >= 0  : signedBinomial (-n) k == (-1)^k * signedBinomial (n+k-1) k

Note: This is compatible with Mathematica's Binomial function.

pascalRow :: Integral a => a -> [Integer]

A given row of the Pascal triangle; equivalent to a sequence of binomial numbers, but much more efficient. You can also left-fold over it.

pascalRow n == [ binomial n k | k<-[0..n] ]

multinomial :: Integral a => [a] -> Integer

Catalan numbers

catalan :: Integral a => a -> Integer

Catalan numbers. OEIS:A000108.

catalanTriangle :: Integral a => a -> a -> Integer

Catalan's triangle. OEIS:A009766. Note:

catalanTriangle n n == catalan n
catalanTriangle n k == countStandardYoungTableaux (toPartition [n,k])

Stirling numbers

signedStirling1stArray :: Integral a => a -> Array Int Integer

Rows of (signed) Stirling numbers of the first kind. OEIS:A008275. Coefficients of the polinomial (x-1)*(x-2)*...*(x-n+1). This function uses the recursion formula.

signedStirling1st :: Integral a => a -> a -> Integer

(Signed) Stirling numbers of the first kind. OEIS:A008275. This function uses signedStirling1stArray, so it shouldn't be used to compute many Stirling numbers.

Argument order: signedStirling1st n k

unsignedStirling1st :: Integral a => a -> a -> Integer

(Unsigned) Stirling numbers of the first kind. See signedStirling1st.

stirling2nd :: Integral a => a -> a -> Integer

Stirling numbers of the second kind. OEIS:A008277. This function uses an explicit formula.

Argument order: stirling2nd n k

Bernoulli numbers

bernoulli :: Integral a => a -> Rational

Bernoulli numbers. bernoulli 1 == -1%2 and bernoulli k == 0 for k>2 and odd. This function uses the formula involving Stirling numbers of the second kind. Numerators: A027641, denominators: A027642.

Bell numbers

bellNumbersArray :: Integral a => a -> Array Int Integer

Bell numbers (Sloane's A000110) from B(0) up to B(n). B(0)=B(1)=1, B(2)=2, etc.

The Bell numbers count the number of set partitions of a set of size n

See http://en.wikipedia.org/wiki/Bell_number

bellNumber :: Integral a => a -> Integer

The n-th Bell number B(n), using the Stirling numbers of the second kind. This may be slower than using bellNumbersArray.