# 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