Questions tagged [analytic-combinatorics]
Use for questions related to counting combinatorial objects.
109 questions
14
votes
2
answers
2k
views
Is this formula for cosine correct? (And is it significant) [closed]
I have recently found this formula for cosine that seems to work, yet I am unable to prove that it works. The formula in question is
$$\lim _{n\rightarrow \infty }\sum _{k=0}^{2n}\sum _{j=0}^{k}( -1)^{...
- 167
1
vote
2
answers
88
views
Exponential generating function for even Eulerian polynomials
Background
The Eulerian polynomials $A_{n}(\cdot) $ have the following exponential generating function (e.g.f.):
$$ \sum_{n=0}^{\infty} A_{n}(t) \frac{x^{n}}{n!} = \frac{t-1}{t-e^{(t-1)x}} \ . \tag{1}\...
- 7,778
8
votes
4
answers
319
views
Asymptotics of $\displaystyle\sum_{i=1}^k i^{-2} (1-i^{-2})^n$ as $k\to +\infty$
For fixed $n$ a non-negative integer, I tried deriving the complete asymptotic expansion of,
$$S_k :=\sum_{i=1}^k i^{-2} (1-i^{-2})^n$$
as $k\to+\infty$ using generating functions and complex analysis,...
- 3,129
3
votes
1
answer
104
views
Inductive form of the Eulerian polynomials
Background
The Eulerian numbers $A(n,k)$ satisfy the explicit formula
$$ A(n,k) = \sum_{i=0}^{k} (-1)^{i} \binom{n+1}{i} (k+1-i)^{n}. $$
The corresponding Eulerian polynomials are defined as $$A_{n} (...
- 7,778
2
votes
2
answers
249
views
Preferential sampling and balls form the urn
Consider an urn with an initial state of $n \ge 1$ red balls and $n$ white balls. Draw a ball from the urn, uniformly at random, and note its color. If the ball is white, do not replace it; if the ...
- 142
4
votes
0
answers
132
views
Asymptotics for balls-in-bins combinatorics
Using the inclusion-exclusion principle, we can derive the number of ways to put $m$ indistinguishable balls into $n$ distinguishable bins where each bin can hold up to $k$ balls as
$$
s(m,n,k):=\sum_{...
- 10.5k
1
vote
0
answers
43
views
Generating function of the element-wise quotient of two sequences
Suppose I have two sequences which are represented by their generating functions,
$A(z)=\sum_{n=0}^{\infty} a_n z^n$ and $B(z)=\sum_{n=0}^{\infty} b_n z^n$.
Suppose I know $A(z)$ and $B(z)$ exactly, ...
- 141
4
votes
2
answers
321
views
Distribution of coupons in the coupon collector problem
The coupon collector problem is well known: how long does it take me to collect $n$ coupons if a random coupon appears each day.
It is known that it takes me, on average, $n H_n$ days to collect all ...
- 541
2
votes
1
answer
101
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,414
1
vote
2
answers
128
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 ...
- 541
5
votes
2
answers
219
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,355
14
votes
1
answer
459
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)$ ...
- 25.7k
1
vote
0
answers
44
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,414
2
votes
0
answers
41
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,432
1
vote
1
answer
89
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,414