Questions tagged [generating-functions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
0answers
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
3answers
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
0answers
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
0answers
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
7answers
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
1answer
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
7answers
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
1answer
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
1answer
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
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
2answers
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
1answer
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
8answers
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
1answer
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
0answers
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
0answers
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}...

1
2 3 4 5