AnalyticComb.jl
Introduction
In 1751, Euler was studying the number of ways in which a given convex polygon could be decomposed into triangles by diagonal lines.1
He realized that the progression of numbers in the solution $S = 1, 2, 5, 14, 42, 132,...$ was directly related to the coefficients of the series expansion of the polynomial fraction $\frac{1 − 2a − \sqrt{1−4a}}{2aa}$, that is: $1 + 2a + 5a^2 + 14a^3 + 42a^4 + 132a^5 + ...$
Given any constructable combinatorial structure, one can use a set of operators to find a generating function and then approach the problem analytically.
See the docs.
Check the text book by Flajolet & Sedgewick and Coursera's full course by Robert Sedgewick for more.
Kudos to Ricardo Bittencourt for his introductory texts on the subject and for helping in an initial implementation.
Quick start
Install
Python package sympy is required for some utilities.
$python -m pip install --upgrade pip
$pip install sympy
Then, from Julia:
pkg>add AnalyticComb
Example
This software can be used to solve problems such as Polya's problem of partitions with restricted summands 2. What is the number of ways of giving change of 99 cents using pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents)?
julia> using AnalyticComb
julia> restricted_sum_part_gf([1,5,10,25]) # examine the generating function from specification SEQ(z)*SEQ(z^5)*SEQ(z^10)*SEQ(z^25)
1
────────────────────────────────────
⎛ 5⎞ ⎛ 10⎞ ⎛ 25⎞
(1 - z)⋅⎝1 - z ⎠⋅⎝1 - z ⎠⋅⎝1 - z ⎠
julia>restricted_sum_part(99,[1,5,10,25]) # Counts for 99 as a sum of elements in (1,5,10,25).
213