# Questions tagged [generating-functions]

The generating-functions tag has no usage guidance.

241
questions

**1**

vote

**1**answer

81 views

### Solving recurrence of a three variable function

I am fairly new to generating functions and have been trying to solve the following recurrence for a computer science problem.
$$ f(k,d,n) = \sum_{i=1}^{n-1} \binom{n-2}{i-1} \left(\frac{1}{2}\...

**1**

vote

**1**answer

118 views

### Solving recursion of a complex function

I am trying to find a closed form formula for the following recursive function:
$$f_n(h)= \sum_{i=1}^{n-1} \binom{n-2}{i-1} \cdot (0.5)^{n-2} \cdot [ (f_{n-i}(h-1)\cdot \sum_{j=0}^{h-1}f_i(j)) + (f_{i}...

**7**

votes

**1**answer

175 views

### Induction step in Bóna and Ehrenborg's proof that the generating function of the alternating runs has -1 as a root of a certain multiplicity

This is a crosspost of a question I asked on Mathematics SE four months ago. Periodically bumping it and placing a bounty on it to attract more attention were to no avail. There are some comments ...

**0**

votes

**0**answers

28 views

### Counting planar trees with the same underlying tree

$T$ be a tree, and $P_T$ denote the number of planar rooted trees whose underlying tree is $T$. Here, a planar rooted tree is a rooted tree such that the children of every vertex are totally ordered. ...

**1**

vote

**1**answer

186 views

### General upper bound of extinction probability

We consider here a Galton–Watson process with an offspring distribution $X$, where $\mathbb{E}X = \mu$ and $\operatorname{Var} X = \sigma^{2} < \infty$ and $q = \mathbb{P}(\text{extinction})$, i.e.,...

**3**

votes

**2**answers

114 views

### Meinardus theorem at use: problems with conditions

I am working on an enumerative problem related to knot theory, and I have found the following generating function
$$F(z)=\prod_{n\geq 1} \frac{1}{(1-z^{2n+1})^2}.$$
I am interested on getting ...

**0**

votes

**0**answers

62 views

### About counting the number of graphs by the maximum degree $D$

This is another way of attacking the problem that I posted on the link: What is the number of connected graphs with $n$ vertices of max. degree up to $D$? Leaving $F(x) = x + x^2 + 2x^3 + 6x^4 + 21x^5 ...

**8**

votes

**3**answers

438 views

### Looking for a “cute” justification for a Catalan-type generating function

The Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$ have the generating function
$$c(x)=\frac{1-\sqrt{1-4x}}{2x}.$$
Let $a\in\mathbb{R}^+$. It seems that the following holds true
$$\frac{c(x)^a}{\sqrt{1-...

**2**

votes

**0**answers

174 views

### Riesz equivalent of Riemann hypothesis and Hadamard product

First define Hadamard product :
Conider two power series is definded as follows :
$$ f(x) = \sum_{n=0}^\infty f_n x^n $$
$$ g(x) =\sum_{n=0}^\infty g_n x^n $$
Then , Hadamard product of $f$ and $g$:...

**7**

votes

**0**answers

142 views

### A diagonal generating function for Fibonacci: Part II

In my earlier MO question, I mentioned although we have for the Fibonacci numbers that
$$F_n=[x^n]\left(\frac1{1-x-x^2}\right),$$
is there a function $F(x)$ such that $F_n=[x^n]\left(F(x)\right)^n$?
...

**14**

votes

**7**answers

2k views

### A special type of generating function for Fibonacci

Notation. Let $[x^n]G(x)$ be the coefficient of $x^n$ in the Taylor series of $G(x)$.
Consider the sequence of central binomial coefficients $\binom{2n}n$. Then there two ways to recover them:
$$\...

**0**

votes

**1**answer

58 views

### Ordered $m$-tuples with fixed number of changes

Given $1\leq k\leq m$, $2\leq d\leq c i\ln i$ and $2\leq i\leq c'\ln(mi\ln i)$ at some $c,c'>0$ how many sequences (lower and upper bounds) are of form $$z_1,\dots,z_m$$ on the condition that
$$0\...

**7**

votes

**7**answers

534 views

### Important combinatorial and algebraic interpretations of the coefficients in the polynomial $[n]!_q = (1+q)(1+q+q^2) \ldots (1+q+\cdots + q^{n-1})$

What are some important combinatorial and algebraic interpretations of the coefficients in the polynomial
$$[n]!_q = (1+q)(1+q+q^2) \ldots (1+q+\cdots + q^{n-1})?$$
As motivation, I will give ...

**3**

votes

**1**answer

80 views

### Asymptotics for an exponential generating function from an ordinary

I'm interested in taking an ordinary generating function $$F(x)=\sum_{n\geq 1}m_nx^n$$ and converting it to an exponential generating function $$M(x)=\sum_{n\geq 1}m_n\frac{x^n}{n!}.$$ I would then ...

**1**

vote

**1**answer

113 views

### Distribution of non-overlapping words in randomly generated text

The question can be described in the following way:
Suppose I have a finite language $\mathcal{L}$ over alphabet $\Sigma$.
I have a string that is composed of a concatenated series of $n$ instances ...

**6**

votes

**0**answers

173 views

### A class of symmetric functions

When attacking a symmetric problem via an asymmetric method, I encountered the following function: $$U_2(n, m) = \sum_{a = 0}^n\binom na (2^a + 2^{n - a})^m.$$
It is easy to see that this function is ...

**5**

votes

**1**answer

318 views

### Convergence of the series of Legendre polynomials

Consider the generating function of Legendre polynomials:
$$\frac{1}{\sqrt{1 - 2xt + t^2}} = \sum\limits^{\infty}_{n=0} P_n(x)t^n$$
Is it true that for $0<x<1, t=1$ series of Legendre ...

**2**

votes

**0**answers

62 views

### Closure of the space of holomorphic functions on the open disk in $\mathbb{C}$ with respect to a Hardy-space-like semi-norm

Let $\mathcal{A}\left(\mathbb{D}\right)$ denote the vector space over $\mathbb{C}$ of all holomorphic functions $f:\mathbb{D}\rightarrow\mathbb{C}$. Define the following semi-norm:$$\left\Vert f\right\...

**4**

votes

**0**answers

43 views

### Complexity of calculating $f^{(n)}(0)$/extracting a coefficient of a functions taylor-series

Many combinatorial problems can be solved using generating functions.
In such a case, we obtain a function $f(x)$, which (for usual) has a taylor-expansion:
$$
f(x) = \sum_{n\ge 0 } a_n x^n
$$
So ...

**0**

votes

**0**answers

96 views

### If the coefficient of the polynomial positive

I want to know what is following sum coefficient looks like. We sum over all integers $p$, $q$ also we put the condition that $q$ is even. Also, it should depend on the parity of $k$
$$\bar{S}(k)=\...

**1**

vote

**0**answers

38 views

### Generalization of Lagrange-Burmann to system of self-consistency equations

In my research, I have come across a system of probability generating functions of the following form:
$$H_1(x) = x A(H_1(x))B(H_2(x)) \text{,}$$
$$H_2(x) = x C(H_1(x))D(H_2(x)) \text{,}$$
and I am ...

**2**

votes

**0**answers

56 views

### Annihilator of the of the generating function not holonomic

The following is a generating function in $x,h$ with infinite parameters
$q_1,q_2\ldots,$ and $w_1, w_2,\ldots$.
$$\Psi(x, h)= \sum_{d=0}^{\infty} s_{(d)} (q_1, q_2, \ldots) \exp \bigg( \sum_{r=1}^{\...

**6**

votes

**0**answers

94 views

### Number of Dyck paths up to stable equivalence

Acyclic (connected) Nakayama algebras can be identified with Dyck paths via their top boundary Auslander-Reiten quivers.
Now two Nakayama algebras $A$ and $B$ should be stable equivalent in case ...

**2**

votes

**0**answers

225 views

### Karamata's proof of Hardy-Littlewood Tauberian theorem

I understand Karamata's proof of the Hardy-Littlewood Tauberian theorem as in http://individual.utoronto.ca/jordanbell/notes/karamata.pdf, but what on earth is the motivation behind Lemma 4 - i.e, ...

**3**

votes

**2**answers

188 views

### One generating function, two-fold sums

This comes out of a series of transformations, so I'll just get to the main focus here.
Define the functions
$$F_n(x)=\frac12\left(x+2+2\sqrt{x+1}\right)^n+\frac12\left(x+2-2\sqrt{x+1}\right)^n. \...

**2**

votes

**0**answers

81 views

### What is the relation between the different generating functions thought as finite approximations of action functionals

In the book Introduction to symplectic topology by MC Duff and Salamon, a discrete analogue of the action functional is defined on $\mathbb{R}^{2n}$. The idea is that a Hamiltonian isotopy can be ...

**0**

votes

**0**answers

144 views

### Generating function with essential singularities

I was recently introduced to analytic combinatorics, and found the method of removing poles astonishing. More precisely, I was reading the last chapter of the popular "generatingfunctionology", in ...

**5**

votes

**0**answers

85 views

### Hooks, monomers, dimers and Young diagrams: Part II

As promised, I've upgraded my last question.
Consider the $k$-by-$n$ partition $\lambda_n=(n,\dots,n)$ and its corresponding Young diagram $Y_{n,k}$, which is a $k\times n$ rectangle of cells. Now, ...

**4**

votes

**0**answers

130 views

### Hooks, monomers, dimers and Young diagrams: Part I

Following Richard Stanley's pointers regarding my earlier MO question, I decided to "scale-down" the problem and add a slight "twist" to it.
Consider the one-line partition $\lambda_n=(n)$ and its ...

**6**

votes

**1**answer

156 views

### Sufficient conditions for the coefficients of a generating function to dominate those of its square

Let $f(z)$ be a generating function (so in particular, its power series coefficients are nonnegative). I am interested in conditions which would ensure that for every $n$, the coefficient of $z^n$ in $...

**2**

votes

**1**answer

212 views

### Meaningful interpretation for fixed point of a probability generating function

Suppose $f$ is the probability generating function for the Galton-Watson branching process.
What intuition makes the fact that $f(s) = s$ is the probability of extinction obvious? Moreover, can one ...

**4**

votes

**1**answer

162 views

### A 2nd order recursion with polynomial coefficients

I'm hoping to find "exact" an solution to the following simple recursion:
$q_m(j+1) = m \cdot q_m(j) + j(j+m)\cdot q_m(j-1)$
with initial data $q_m(0) = 1$, $q_m(1)=m$, where $m \geq 0$ is an ...

**1**

vote

**0**answers

84 views

### One-point partition

Let following be the partition function in infinitely many variables $x_i$ the linear coordinates on the vector space $V$.
$$
\mathcal{Z}=exp\Big(\sum_{\substack{g\geq 0\\n\geq 1}}\frac{h^{g-1}}{n!}\...

**1**

vote

**0**answers

109 views

### Relate log concavity of sequence to convexity of 1/generating function

Let $Y$ be a random variable on the natural numbers, with $p_k = \mathbb{P}(Y = k)$ for $k \geq 0$.
Say that $Y$ is log-concave if $p_k^2 \geq p_{k-1} p_{k+1}$ for $k \geq 1$, and that $Y$ is log-...

**5**

votes

**1**answer

173 views

### Collapsed partitions and generating functions

Given $n\in\Bbb{N}$, the number of (unrestricted) integer partitions of $n$ are given by
$$\sum_{n\geq0}p(n)x^n=\prod_{j\geq1}\frac1{1-x^j}.$$
Define the collapsed partitions of $n$ to be the ...

**1**

vote

**1**answer

141 views

### Integer partitions with subset sums “not divisible” by p

I have the following questions: Let $N \in \mathbb{N}$ and
\begin{equation}
\sum_{i=1}^k n_i = N,
\end{equation}
with $n_i \in \mathbb{N}$ for $1 \le i \le k$ and some $k \in \mathbb{N}$, be an ...

**2**

votes

**2**answers

453 views

### Explicit formula for a generating function

In an enumeration problem the sequence of number of Dyck paths semilength n having no UUDD's starting at level 0 with generating function $$\frac{2}{(1+2z^2+\sqrt{1-4z})}$$ showed up, see also https://...

**0**

votes

**0**answers

66 views

### Generating function for number of r-disjoint subsets each of size k

Fix $n, k$. Let
$$
C^{n,k}_r =\frac{1}{r!} \binom{n}{\underbrace{k, \ldots, k}_{\text{r times}}, n-rk} = \frac{n!}{r!(k!)^r(n - kr)!}
$$
be the number of ways to form $r$ disjoint subsets each of ...

**17**

votes

**1**answer

680 views

### Congruences Ramanujan-style

Let $t\in\Bbb{N}$ and consider the sequences $p_t(n)$ defined by
$$\sum_{n\geq0}p_t(n)x^n=\prod_{i\geq1}\frac1{(1-x^i)^t}=(x;x)_{\infty}^{-t}.$$
The numbers $p_t(n)$ can be regarded as enumerating ...

**3**

votes

**2**answers

274 views

### Seeking proof to an asymptotics of a recursion or functional equation

My question on math.stackexchange.com and the continuation by an answer to it gives the two summation expressions for the recursion
$$a_n = 1+\frac1{2^n}\sum_{k=0}^n {n\choose k}a_k,\, \forall n\in\...

**5**

votes

**1**answer

201 views

### Second order recurrence relation for third order polynomial root

Consider this recurrence relation:
$$
\begin{eqnarray*}
f_0&=&1\\
f_n&=&
\sum_{m=0}^{n-1} \frac{\left(\frac{m+3}{2}\right)_{m-1}}{\left(\frac{m+2}{2}\right)_m} f_{n-m-1} f_m\ \ \ \...

**3**

votes

**0**answers

117 views

### How to use this generalised 'generating function' for the Gegenbauer polynomials

Cohl (2011) gives a generalisation of the standard generating function for the Gegenbauer polynomials $C_n^\mu(x)$:
$(1 -2tx + t^2)^{-\nu} = A_{\mu,\nu} \frac{(1-t^2)^{-\nu+\mu+1/2}}{t^{\mu+1/2}} \...

**12**

votes

**0**answers

386 views

### Wherefore art thou a Borcherds Product?

This question essentially asks how can one recognize (or rule out) that a generating function of combinatorial origin may be given as a Borcherds type product. I'll start with a motivational example: ...

**0**

votes

**1**answer

159 views

### Is this a Borel summable $ S = \sum_{k=0}^\infty (-1)^k (k!)a_k $ with $ a_k$ alternating sequence?

let $ S = \sum_{k=0}^\infty (-1)^k (k!)a_k $ a divergent series such that $b_k=(-1)^k (k!)a_k >0 $ for $k>1$ , and $b_k$ signed this from $k=1$ to $20$ ,The asymptotic of the titled series ...

**2**

votes

**1**answer

181 views

### What can we know about “the half” of the generating series of Bessel function

I am interested in the series
$$\sum_{n\geq 1}I_n(x)\lambda^n$$
which is not the full generating series of the modified Bessel function of the first kind because it starts from $n=1$ and not at $-\...

**-2**

votes

**1**answer

177 views

### What are the patterns of the sequence of polynomials? [closed]

In my research, I obtained a sequence of polynomials (I am only able to compute the first 4 of them):
\begin{align}
& f(2) = 1+t, \\
& f(3) = 1+4t+3t^2, \\
& f(4) = 1+6t+12t^2+7t^3, \\
&...

**18**

votes

**8**answers

3k views

### Generating function in graph theory

I am looking for a simple illustration of generating functions in graph theory.
So far, the matching polynomial seems to be the best. But I want something bit richer; at least a derivative should ...

**5**

votes

**1**answer

435 views

### A generalization of binary Krawtchouk polynomials

I am looking for orthogonal polynomials $P_{d,m,n}$ that have their values at integers $i$ specified by the following generating function
$(1-z)^i (1+z+z^2+ \ldots + z^d)^{n-i} = \sum_{m=0}^{i+d(n-i)}...

**1**

vote

**0**answers

219 views

### Asymptotic behavior of coefficient of a complicated generating function

Given a generating function
$$H(z)=\sum_{m=0}^\infty h_m z^m =\frac{P F(z)}{1-(1-P)F(z)}$$
where $0<P\leq 1$ and
$$F(z)=1-\frac{\pi z\sqrt{c}}{6\boldsymbol{\mathrm{K}}(k')} $$
in which $\...

**2**

votes

**0**answers

193 views

### Inverse of partial sums of general harmonic series

I would like to understand better the scaling of the following summation as a function of $r$ and $p > 1$:
$$
S_r(p) := \sum_{m=1}^{r} \left( \sum_{k=r-m+1}^{r} \left( \frac{k^q}{\sum_{k'=1}^{r}...