Questions tagged [analytic-combinatorics]

Question 1

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)^{...

Question 2

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}\...

Question 3

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

Question 4

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} (...

Question 5

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

Question 6

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_{...

Question 7

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

Question 8

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

Question 9

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

Question 10

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

Question 11

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

Question 12

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)$ ...

Question 13

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

Question 14

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{\...

Question 15

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) \...

Stack Exchange Network

Questions tagged [analytic-combinatorics]

Is this formula for cosine correct? (And is it significant) [closed]

Exponential generating function for even Eulerian polynomials

Asymptotics of $\displaystyle\sum_{i=1}^k i^{-2} (1-i^{-2})^n$ as $k\to +\infty$

Inductive form of the Eulerian polynomials

Preferential sampling and balls form the urn

Asymptotics for balls-in-bins combinatorics

Generating function of the element-wise quotient of two sequences

Distribution of coupons in the coupon collector problem

Show that $\frac{1+z-\sqrt{z^2-6z+1}}{4}$ fits the Lagrangean framework

Number of unique numbers in a vector with replacement

Estimate a sum of binomial coefficients

Limiting growth ratio of $[x^n]f(x)^n$

Using the Singular Inverstion Theorem to count the number of $r$-ary trees

Find the average number of children at the root of a Cayley tree.

Understanding the conditions for the Lagrange Inversion Formula

Hot Network Questions