Questions tagged [analytic-combinatorics]
Use for questions related to counting combinatorial objects.
103
questions
2
votes
1
answer
84
views
Show that $\frac{1+z-\sqrt{z^2-6z+1}}{4}$ fits the Lagrangean framework
Let $S(z)$ be the OGF of bracketings. Show that the Lagrangean framework holds for $S(z)$.
Remark: You can find the definition of Lagrangean framework below.
From the Flajolet & Sedgewick book (p....
- 4,222
1
vote
2
answers
86
views
Number of unique numbers in a vector with replacement
If I get a vector $x$ of length $\ell\geq n$ that contains random draws of $n$ numbers and know that all $n$ numbers appear at least once in such vector, how many numbers appear exactly once in this ...
- 521
5
votes
2
answers
164
views
Estimate a sum of binomial coefficients
I should know this by the time, but: can someone tell me how to rigorously compute the leading order (including the constant) of the following sum:
$$\sum_{ 1\leq k \leq n/3 } {2 k \choose k} {n-2k-1 ...
- 1,363
0
votes
0
answers
19
views
Combinatorics: How to use the tree dissymmetry theorem to find singularities?
Denote by $T(z)$ the exponential generating function of the class $\mathcal{T}$ of
labelled (unrooted) trees in which all vertices have degree $1$ or $3$. Use the tree dissymmetry theorem (see below) ...
- 4,222
14
votes
1
answer
391
views
Limiting growth ratio of $[x^n]f(x)^n$
Based on a few examples (mainly data from OEIS as well as a bit of theory) I've arrived at the following conjecture:
Conjecture: Let $f(x)$ be analytic at $0$ and nonlinear, and let $[x^n]f(x)$ ...
- 23.5k
1
vote
0
answers
29
views
Using the Singular Inverstion Theorem to count the number of $r$-ary trees
For $r \ge 2$ let $\mathcal{C}_r$ denote the class of $r$-ary trees, i.e. Cayley trees in which every vertex has at most $r$ children. We denote the EGF of $\mathcal{C}_r$ by $C_r(z)$. Show that the ...
- 4,222
2
votes
0
answers
29
views
Find the average number of children at the root of a Cayley tree.
I am just starting with analytic combinatorics and I came across this problem:
Find the average number of children at the root of a Cayley tree.
The solution goes as:
Specification:
$$\def\textsc#1{\...
- 5,352
1
vote
1
answer
61
views
Understanding the conditions for the Lagrange Inversion Formula
Lagrange Inversion Formula: Let $A(u) = \sum_{k \ge 0} a_k z^k$ be a power series in $\mathbb{C}[[z]]$ with $a_0 \ne 0$. Then the equation
$$B(z) = zA(B(Z)) \qquad (1)$$
has a unique solution $B(z) \...
- 4,222
1
vote
0
answers
21
views
$\sum_{j=0}^\infty(-1)^j\frac{1 -e^{(aj^2 + b)M}}{1-e^{aj^2 +b}}$?
I've recently come across the following series, and I am trying to figure out if there is a closed form solution, or an asymptotic behavior for large M:
$$
\sum_{j=0}^\infty(-1)^j\frac{1 -e^{(aj^2 + b)...
- 43
6
votes
1
answer
262
views
Computing Asymptotic Expansion of Coefficients of Implicitly Defined Power Series
Background:
I've been studying the text "Analytic Combinatorics" (amazing book!) and related papers in an effort to intuit the methods therein. My tangentially related background in spectral ...
7
votes
2
answers
137
views
How are combinatorial classes and combinatorial species related?
I am reading through Analytic Combinatorics by Flajolet and Sedgewick and I feel pretty confident with my understanding of classes and how they relate to EGFs. However recently I encountered the ...
- 305
2
votes
0
answers
77
views
Symbolic method, bijective proofs or double counting proofs?
As you can see, I have been studying analytic combinatorics, specifically Flajolet's symbolic method.
And while I was reading about how combinatorial structures are translated into generating ...
- 135
0
votes
1
answer
56
views
Express the class $\mathcal{R}$ of surjections in terms of $\text{Seq}$?
While studying these notes about two-level constructions in analytical combinatorics I noticed that the following is mentioned
$\mathcal{R}^{(2)}= 1\,\text{Seq}(1)\,2\,\text{Seq}(1+2)\cup 2\,\text{Seq}...
- 135
2
votes
0
answers
162
views
Doubts in $ \sum_{k=1}^{\infty}\frac{A^k(z)}{k}=\ln\left(\frac{1}{1-A(z)}\right) $
I'm trying to prove that $ \sum_{k=1}^{\infty}\frac{A^k(z)}{k}=\ln\left(\frac{1}{1-A(z)}\right)$, (for those who know about the topic of analytical combinatorics, you may notice that it is the ...
- 1,262
1
vote
1
answer
68
views
Distributing $m\cdot n$ identical items into $n$ distinct boxes, with $m$ distinct positions in box
There are $n$ boxes and $m\cdot n$ identical items. Each box has $m$ positions where an item can be placed. The order matters here. It is a difference if an item is placed in position 1, 2, or 3 or if ...
- 13