## BigCombinatorics.jl

Combinatorial functions that always return a BigInt
Author scheinerman
Popularity
0 Stars
Updated Last
6 Months Ago
Started In
August 2018

# BigCombinatorics  This is an implementation of various combinatorial functions. These functions always return `BigInt` values. This convention is signaled by the fact that these functions' names begin with a capital letter.

## Rationale

If we want to calculate 20!, it's easy enough to do this:

```julia> factorial(20)
2432902008176640000```

However, for 100!, we see this:

```julia> factorial(100)
ERROR: OverflowError: 100 is too large to look up in the table
Stacktrace:
 factorial_lookup(::Int64, ::Array{Int64,1}, ::Int64) at ./combinatorics.jl:19
 factorial(::Int64) at ./combinatorics.jl:27
 top-level scope at none:0```

The problem is that 100! is too big to fit in an `Int` answer. Of course, we could resolve this problem this way:

```julia> factorial(big(100))
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000```

We take a different approach. We shouldn't have to worry about how large our arguments may be before a combinatorial function overflows. Instead, let's assume the result is always of type `BigInt` so the calculation will not be hampered by this problem.

## Functions

• `Fibonacci(n)` returns the `n`-th Fibonacci number with `Fibonacci(0)==0` and `Fibonacci(1)==1`.
• `Factorial(n)` returns `n!` and `Factorial(n,k)` returns `n!/k!`.
• `FallingFactorial(n,k)` returns `n*(n-1)*(n-2)*...*(n-k+1)`.
• `RisingFactorial(n,k)` returns `n*(n+1)*(n+2)*...*(n+k-1)`.
• `DoubleFactorial(n)` returns `n!!`.
• `Catalan(n)` returns the `n`-th Catalan number.
• `Derangements(n)` returns the number of derangements of an `n`-element set.
• `Binomial(n,k)` returns the number of `k`-element subsets of an `n`-element set.
• `MultiChoose(n,k)` returns the number of `k`-element multisets that can be formed using the elements of an `n`-element set. Warning: This is not the same as `Multinomial`.
• `Multnomial(vals)` returns the multinomial coefficient where the top index is the sum of `vals`. Here, `vals` may either be a vector of integers or a comma separated list of arguments. In other words, both `Multinomial([3,3,3])` and `Multinomial(3,3,3)` return the multinomial coefficient with top index `9` and bottom indices `3,3,3`. The result is `1680`. Warning: This is not the same as `MultiChoose`.
• `Bell(n)` returns the `n`-th Bell number, i.e., the number of partitions of an `n`-element set.
• `Stirling1(n,k)` returns the signed Stirling number of the first kind.
• `Stirling2(n,k)` returns the Stirling number of the second kind, i.e., the number of partitions of an `n`-element set into `k`-parts (nonempty).
• `Fibonacci(n)` returns the `n`-th Fibonacci number with `Fibonacci(0)==0` and `Fibonacci(1)==1`.
• `IntPartitions(n)` returns the number of partitions of the integer `n` and `IntPartitions(n,k)` returns the number of partitions of the integer `n` with exactly `k` parts.
• `IntPartitionsDistinct(n)` returns the number of partitions of `n` into distinct parts and `IntPartitionsDistinct(n,k)` returns the number of partitions of `n` into `k` distinct parts.
• `Euler(n)` returns the `n`-th Euler number.
• `Eulerian(n,k)` returns the number of permutations of `1:n` with `k` ascents.
• `PowerSum(n,k)` returns the sum `1^k + 2^k + ... + n^k`.

## Implementation

These function have nice recursive properties that we exploit to make the code as simple as possible. In many (but not all) of these functions we cache the result of the calculation to avoid combinatorial explosion in the recursion. In those cases, we don't compute the same result twice.

The following functions can be used to manage the saved values.

• `BigCombinatorics.cache_report()` prints out the number of values stored in the cache for each function.
• `BigCombinatorics.cache_clear(func)` clears all values stored for a specific function.
• `BigCombinatorics.cache_clear()` clears all values in the cache.

### Used By Packages

No packages found.