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

9 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

Version 2.0 is out with major performance enhancements

I needed to run some simulations with large samples and SymPy.jl was unfeasible.

I changed some of the methods (SymPy :Sym expressions for Julia native functions and SymPy.series for TaylorSeries.series_expand).

Run times were 10 to 10^5 faster (no kidding) for some methods . I am quite happy with Julia at the moment. :grinning:

If this package seems interesting, stay in tune.
I’ll release SymbolicInference.jl soon. It uses AnalyticComb.jl to make inference on real problems (e.g. chaotic time-series). Nils (NilsToAn · GitHub) and Norbert Marwan (pucicu (Norbert Marwan) · GitHub) from Potsdam started contributing on a paper about this.

3 Likes

Symbolic interface should be a name used for symbolic interfaces

1 Like

“interface” vs “inference”

2 Likes

Indeed.

This comment made me think that “SymbolicMethods” would actually be a better name for what AnalyticComb.jl is at the moment.

I have did not implement much of the ‘second part’ of the book (with complex analysis) yet.

For example, knowing the generating function of a sequence, and therefore all its singular varieties, can your code provide assymptotics on the sequence itself ? I think the book provide results on both first and second order if I am right. Is that implemented or is that in the “second part” ?

Not yet for general cases, @lrnv.

That’s the focus of the 2nd part.

There are some assymptotics for specific problems though.

It would be interesting to see how close the implementation limits would be to the theory, I am impatient to look at it !

@lrnv

Take a look at this first application for time-series: