AnalyticComb.jl - Analytic Combinatorics in Julia

Hello, fellow Julia enthusiasts,

I started to implement symbolic methods for combinatorial problems ( GitHub - fargolo/AnalyticComb.jl: Solutions for combinatorial problems using symbolic methods. ) following Flajolet & Sedgewick’s textbook.

I am not well versed in symbolic computation, so I would love some help from more experienced developers.

This package implements solutions for combinatorial problems using analytic combinatorics. Check the text book by Flajojelt & Sedgewick ( https://algo.inria.fr/flajolet/Publications/book.pdf ) and Coursera’s full course by Robert Sedgewick ( https://www.coursera.org/learn/analytic-combinatorics ).

A brief intro to the subject:

In, 1751, Euler was studying the number of ways in which a given convex polygon could be decomposed into triangles by diagonal lines. (Flajolet & Sedgewick, p.20)

He realized that the progression of numbers in the solution (1, 2, 5, 14, 42, 132,…) was directly related to the coefficients of the series expansion of the polynomial fraction (1−2a−√(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.

Best regards,
Felipe

7 Likes

This seems like an interesting package. Unfortunately, I lack the expertise to help. Nonetheless, I wonder whether you can find any inspiration from Symbolics.jl.

2 Likes