# 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.

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: