HMath.Combinatorics¶
Module index · Numerical conventions
Description
Exact combinatorics. Indices and ranks are zero based; enumerations use
lexicographic order. Counts use unbounded Integer. Enumeration APIs take a
maximum output count and reject the request before constructing that output.
Scalar recurrences accept orders through 4096 (quadratic tables through 512).
On this page¶
| API | Purpose |
|---|---|
| permutationsCount | Given n,k in [0,4096], return n!/(n-k)! exactly, or zero when k>n. |
| combinationsCount | Given n,k in [0,4096], return the exact binomial coefficient, or zero when k>n. |
| multinomial | Given nonnegative group sizes whose sum is <=4096, return factorial(total)product(factorial sizes). |
| permutationsOf | Distinct positions, including when values compare equal. |
| combinationsOf | Given output budget, selection length k, then list, enumerate position-distinct k-element combinations in source order. |
| rankPermutation | A permutation of [0,n), in lexicographic Lehmer order. |
| unrankPermutation | Given size n in [0,4096] then zero-based rank in [0,n!), return the lexicographic permutation of [0..n-1]. |
| rankCombination | Given universe size n then strictly increasing distinct indices in [0,n), return the zero-based lexicographic combination rank. |
| unrankCombination | Given universe size n, selection size k, then zero-based rank, return the increasing index list. |
| derangementCount | Return exact number of permutations of n elements having no fixed points. |
| derangements | Enumeration uses the factorial upper bound, so a request may be rejected even if its filtered derangement output would fit. |
| integerPartitions | Nonincreasing positive parts. |
| setPartitions | Set partitions of [0,n), using restricted-growth order of block labels. |
| stirlingFirst | Signed first-kind Stirling numbers, coefficients of the falling factorial. |
| stirlingSecond | Given n,k, return the exact number of partitions into k nonempty unlabeled blocks. |
| bellNumber | Return the exact number of set partitions of n labeled objects, summing second-kind Stirling numbers. |
| eulerianNumber | Given n,k, return the Eulerian recurrence counting permutations by ascents. |
| lahNumber | Given n,k in [0,4096], return unsigned Lah number n!/k!*choose(n-1,k-1), with (0,0)=1 and impossible positive-size partitions giving zero. |
| catalanNumber | Return exact Catalan number choose(2*n,n)/(n+1), requiring n in [0,4096]. |
| fibonacci | Return exact zero-based Fibonacci number by fast doubling for n in [0,4096]. |
| lucas | Return zero-based Lucas number using neighboring Fibonacci numbers. n and n+1 must both satisfy the [0,4096] bound, so n<=4095. |
| pascalTriangle | Return Pascal rows zero through n inclusive, starting [[1]]. n must lie in [0,512]; invalid orders fail. |
| inclusionExclusion | Union cardinality from all nonempty intersection sizes, indexed by subset bit mask 1 through 2^n-1. |
| subsets | Given maximum output count then list, enumerate its position-based powerset. |
| cartesianProduct | Given output budget then a list of lists, return all ordered choices using sequence. |
| multisetPermutations | Given budget then ordered values, enumerate distinct multiset permutations in ascending lexicographic order. |
| multisetCount | Return the multinomial count of distinct permutations of a list, grouping equal values in sorted order. |
| linearRecurrence | a[n] = sum c[i]*a[n-i-1]; initial values have the same length as coefficients. |
| generatingCoefficients | Formal power-series division P(x)/Q(x) around zero, exact rationals. |
| convolveSeries | Given output length n then two coefficient lists, return the first n exact Integer convolution coefficients, treating absent coefficients as zero. n must lie in [0,4096]. |
| finiteDifferences | Return successive forward-difference rows beginning with the original list and ending at the last singleton. |
| finiteSum | Sum a finite list using its Num arithmetic. |
Documentation
permutationsCount
permutationsCount :: Int -> Int -> Either MathError Integer Source #
Given n,k in [0,4096], return n!/(n-k)! exactly, or zero when k>n. Invalid orders fail. Example: permutationsCount 4 2 == Right 12.
combinationsCount
combinationsCount :: Int -> Int -> Either MathError Integer Source #
Given n,k in [0,4096], return the exact binomial coefficient, or zero when k>n. Invalid orders fail. Example: combinationsCount 4 2 == Right 6.
multinomial
multinomial :: [Int] -> Either MathError Integer Source #
Given nonnegative group sizes whose sum is <=4096, return factorial(total)product(factorial sizes). Invalid sizestotal fail. Example: multinomial [2,1] == Right 3.
permutationsOf
permutationsOf :: Int -> Int -> [a] -> Either MathError [[a]] Source #
Distinct positions, including when values compare equal.
combinationsOf
combinationsOf :: Int -> Int -> [a] -> Either MathError [[a]] Source #
Given output budget, selection length k, then list, enumerate position-distinct k-element combinations in source order. Invalid order or insufficient budget fails before output construction.
rankPermutation
rankPermutation :: [Int] -> Either MathError Integer Source #
A permutation of [0,n), in lexicographic Lehmer order.
unrankPermutation
unrankPermutation :: Int -> Integer -> Either MathError [Int] Source #
Given size n in [0,4096] then zero-based rank in [0,n!), return the lexicographic permutation of [0..n-1]. Invalid size/rank fails.
rankCombination
rankCombination :: Int -> [Int] -> Either MathError Integer Source #
Given universe size n then strictly increasing distinct indices in [0,n), return the zero-based lexicographic combination rank. Invalid order/indices fail.
unrankCombination
unrankCombination :: Int -> Int -> Integer -> Either MathError [Int] Source #
Given universe size n, selection size k, then zero-based rank, return the increasing index list. Orders must be in [0,4096] and rank must be below choose(n,k); otherwise fail.
derangementCount
derangementCount :: Int -> Either MathError Integer Source #
Return exact number of permutations of n elements having no fixed points. Require n in [0,4096]; invalid orders fail. D0=1, D1=0. Example: derangementCount 3 == Right 2.
derangements
derangements :: Int -> Int -> Either MathError [[Int]] Source #
Enumeration uses the factorial upper bound, so a request may be rejected even if its filtered derangement output would fit.
integerPartitions
integerPartitions :: Int -> Int -> Either MathError [[Int]] Source #
Nonincreasing positive parts. The budget counts search nodes as well as outputs, preventing long searches with a tiny output limit.
setPartitions
setPartitions :: Int -> Int -> Either MathError [[[Int]]] Source #
Set partitions of [0,n), using restricted-growth order of block labels.
stirlingFirst
stirlingFirst :: Int -> Int -> Either MathError Integer Source #
Signed first-kind Stirling numbers, coefficients of the falling factorial.
stirlingSecond
stirlingSecond :: Int -> Int -> Either MathError Integer Source #
Given n,k, return the exact number of partitions into k nonempty unlabeled blocks. Require n<=512 and nonnegative bounded orders; k>n gives zero.
bellNumber
bellNumber :: Int -> Either MathError Integer Source #
Return the exact number of set partitions of n labeled objects, summing second-kind Stirling numbers. The triangular recurrence requires n in [0,512].
eulerianNumber
eulerianNumber :: Int -> Int -> Either MathError Integer Source #
Given n,k, return the Eulerian recurrence counting permutations by ascents. Require n<=512 and bounded nonnegative orders; k>n gives zero.
lahNumber
lahNumber :: Int -> Int -> Either MathError Integer Source #
Given n,k in [0,4096], return unsigned Lah number n!/k!*choose(n-1,k-1), with (0,0)=1 and impossible positive-size partitions giving zero. Invalid orders fail.
catalanNumber
catalanNumber :: Int -> Either MathError Integer Source #
Return exact Catalan number choose(2*n,n)/(n+1), requiring n in [0,4096]. Example: catalanNumber 3 == Right 5.
fibonacci
fibonacci :: Int -> Either MathError Integer Source #
Return exact zero-based Fibonacci number by fast doubling for n in [0,4096]. Invalid index fails. Example: fibonacci 10 == Right 55.
lucas
lucas :: Int -> Either MathError Integer Source #
Return zero-based Lucas number using neighboring Fibonacci numbers. n and n+1 must both satisfy the [0,4096] bound, so n<=4095. Invalid index fails.
pascalTriangle
pascalTriangle :: Int -> Either MathError [[Integer]] Source #
Return Pascal rows zero through n inclusive, starting [[1]]. n must lie in [0,512]; invalid orders fail.
inclusionExclusion
inclusionExclusion :: Int -> [Integer] -> Either MathError Integer Source #
Union cardinality from all nonempty intersection sizes, indexed by subset bit mask 1 through 2^n-1. The caller supplies consistent intersection counts.
subsets
subsets :: Int -> [a] -> Either MathError [[a]] Source #
Given maximum output count then list, enumerate its position-based powerset. Reject input order >4096 or a budget smaller than 2^length. Equal input values can yield equal-valued subsets.
cartesianProduct
cartesianProduct :: Int -> [[a]] -> Either MathError [[a]] Source #
Given output budget then a list of lists, return all ordered choices using sequence. Reject negative/insufficient budget before constructing results. Empty outer list yields one empty choice.
multisetPermutations
multisetPermutations :: Ord a => Int -> [a] -> Either MathError [[a]] Source #
Given budget then ordered values, enumerate distinct multiset permutations in ascending lexicographic order. Invalid size or insufficient output budget fails before enumeration.
multisetCount
multisetCount :: Ord a => [a] -> Either MathError Integer Source #
Return the multinomial count of distinct permutations of a list, grouping equal values in sorted order. Group sizes and total must satisfy the 4096-element combinatorial bound.
linearRecurrence
linearRecurrence :: Int -> [Integer] -> [Integer] -> Either MathError [Integer] Source #
a[n] = sum c[i]*a[n-i-1]; initial values have the same length as
coefficients. A finite exact prefix of at most 4096 coefficients is returned.
generatingCoefficients
generatingCoefficients :: Int -> [Rational] -> [Rational] -> Either MathError [Rational] Source #
Formal power-series division P(x)/Q(x) around zero, exact rationals.
The denominator constant must be nonzero; no analytic convergence is claimed.
convolveSeries
convolveSeries :: Int -> [Integer] -> [Integer] -> Either MathError [Integer] Source #
Given output length n then two coefficient lists, return the first n exact Integer convolution coefficients, treating absent coefficients as zero. n must lie in [0,4096].
finiteDifferences
finiteDifferences :: Num a => [a] -> [[a]] Source #
Return successive forward-difference rows beginning with the original list and ending at the last singleton. Empty input yields no rows. Example: finiteDifferences [1,4,9] == [[1,4,9],[3,5],[2]].