# Questions tagged [generating-functions]

The generating-functions tag has no usage guidance.

273
questions

**12**

votes

**2**answers

257 views

+100

### What alternatives are there to the binomial poset theory of generating function families?

A natural question in combinatorics is, why are certain families of generating functions combinatorially useful, like $\Sigma_n a_n x^n$ and $\Sigma_na_n\frac{x^n}{n!}$, why are other families are not,...

**3**

votes

**1**answer

346 views

### Conjecture on bernoulli numbers and binomial coefficients

Crossposted from
https://math.stackexchange.com/questions/4116414/conjecture-on-bernoulli-numbers-and-binomial-coefficients
In playing around with some formulas, I have come up with the following ...

**2**

votes

**1**answer

120 views

### Fibonacci-Motzkin paths and J-type continued fractions

Recall that a Motzkin path is a piece-wise linear planar path
connecting points in the integer lattice quadrant
$\Bbb{Z}_{\geq 0} \times \Bbb{Z}_{\geq 0}$ beginning at the origin $(0,0)$ and
ending at ...

**1**

vote

**1**answer

252 views

### Why $\lim_{n\rightarrow \infty}\frac{F(n,n)}{F(n-1,n-1)} =\frac{9}{8}$?

$$F(m,n)= \begin{cases}
1, & \text{if $m n=0$ }; \\
\frac{1}{2} F(m ,n-1) + \frac{1}{3} F(m-1,n )+ \frac{1}{4} F(m-1,n-1), & \text{ if $m n>0$. }%
\end{cases}$$
Please a proof of:
$$\lim_{...

**1**

vote

**1**answer

164 views

### What is the inverse Laplace transform of $\frac{(1/s)_{n}}{s} $?

Introduction
So far, I have found (p. 5) the following generating functions of the unsigned Stirling numbers of the first kind:
\begin{equation} \tag{1} \label{1} \sum_{l=1}^{n} |S_{1}(n,l)|z^{l} = (z)...

**11**

votes

**2**answers

531 views

### Alternating sum of hook lengths: Part I

Given $\lambda$ an integer partition of $n$, let $h_{ij}(\lambda)$ denote the hook length of cell $(i,j)$ in the Young diagram of $\lambda$.
Is there a closed formula or a generating function for the ...

**1**

vote

**0**answers

33 views

### Correspondence between monomer-dimer heaps and words in 2 alphabets

For background and some illustrative pictures, refer to this preprint by A M Grasia and G Ganzberger: Fibonacci polynomials. For the present purpose, it suffices to read into pages 4 and 5.
The part ...

**6**

votes

**0**answers

167 views

### Parameter independence of Stanley's “content formula”. Why?

For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively.
R. Stanley remarked following ...

**3**

votes

**1**answer

149 views

### Generating function for parity in hooks

Let $\lambda\vdash n$ denote an integer partition of $n$ and $\frak{H}_{\lambda}$ be the multiset of hook lengths of $\lambda$. Further, let $o(\lambda)=\#$ of odd entries and $e(\lambda)=\#$ of even ...

**3**

votes

**1**answer

285 views

### Special permutations of $\{1,2,3,\ldots,n\}$

How do you show that number of permutations of $\{1,2,3,\ldots,n\}$ such that image of no two consecutive numbers is consecutive is
$$n! + \sum_{k = 1}^{n}(-1)^k\sum_{i = 1}^{k}\dbinom{k - 1}{i - 1}\...

**4**

votes

**1**answer

363 views

### $a^{th}$-root of exponential generating functions

This is a quick follow up on R. Stanley's interesting post on MO in a different direction, which might be easier.
For positive integers $a$, define the family of functions (infinite series) given by
$$...

**51**

votes

**2**answers

5k views

### The “square root” of a graph?

The number $f(n)$ of graphs on the vertex set $\{1,\dots,n\}$,
allowing loops but not multiple edges, is $2^{{n+1\choose
2}}$, with exponential generating function $F(x)=\sum_{n\geq 0}
2^{{n+1\choose ...

**5**

votes

**0**answers

53 views

### An identity for rational functions leading to equations for multiple polylogarithms

The following identity is not hard to prove:
$$
\sum_{1\leq i_1<i_2<\ldots <i_{2n}\leq N} (-1)^{i_1+\ldots+i_{2n}}\frac{(1-x_{i_1})(1-x_{i_3})\ldots(1-x_{i_{2n-1}})}{(1-x_{i_2})(1-x_{i_4})\...

**2**

votes

**1**answer

106 views

### Analytical expressions for certain exponential generating functions

I am looking at
$$f_{j,k}(x) = \sum_{n=0}^\infty \frac{x^n}{(k+j\cdot n)!}$$
where $j$ is a positive integer, and $k = 0,\ldots, j-1$. The case $j = 1$ admits the expression
$$f_{1,k}(x) = e^x x^{-k} \...

**0**

votes

**0**answers

84 views

### Probability density on Riemannian manifold

Let $\mathcal{M}$ be a $d-$dimensional (Riemannian) manifold and $X$ be a random variable taking values in $\mathcal{M}$.
Assume that $X=f(Z)$ where $Z\sim \pi(z)$, and $f:\mathcal{Z}\subseteq \mathbb{...

**4**

votes

**1**answer

202 views

### Does the ordinary generating function of Bell numbers converge?

I am working in a field not really based on combinatorics, therefore I appologize if my question is in any kind invalid. Nevertheless, in my calculations, the Bell numbers appeared. I need to find ...

**4**

votes

**0**answers

125 views

### Generalized Catalan generating series

Let
$$
\mathscr{B}_k(z) = \sum_{n\geq 0}{kn+1\choose n}\frac{1}{kn+1}z^n\,,
$$
then it is well known that
$$
\tag{1}\label{1}
\text{log}\mathscr{B}_k(z)= \sum_{n\geq 1}{kn\choose n}\frac{1}{kn}z^n\,.
$...

**15**

votes

**1**answer

143 views

### A formula for this generating function that is similar to the $qt$-Catalan numbers

I came up with the following conjecture:
$$
\sum_{n \ge 0} z^n \sum_{\mu \vdash n} \frac{ t^{\sum l}q^{\sum a}}{\prod (q^a - t^{l+1})(t^l - q^{a+1})} = \exp\left(\sum_{n \ge 1} \frac{z^n}{n(q^n-1)(t^n-...

**0**

votes

**0**answers

86 views

### Generating function to continued fraction?

Assume $f_i \ne 0$. I want to convert a sequence:
$$F(z) = 1+f_1z+f_2z^2+f_3z^3+\ldots$$
to a Stieltjes continued fraction (S-fraction):
$$\frac{1}{1+\frac{g_1z}{1+ \cdots}}$$
See page 230 of these ...

**1**

vote

**1**answer

158 views

### Closed-form formula for a multivariate polynomial

Counting certain walks in threshold graphs, I came to the following independent problem. Assume that $x_1,\dots,x_a$ are independent variables and for $k\geq 2$ let
$$
P_k(x_1,\dots,x_a)=\sum_{(i_1,\...

**1**

vote

**1**answer

144 views

### The number of permutations of given order

I want to count the number of permutations of the given order $k$ in $S_n\;(\sigma^k=id,\sigma^l\neq id\;for\;l<k)$. I found some works about that problem, but they are more general than necessary. ...

**10**

votes

**1**answer

385 views

### Generating functions of Collatz iterates?

Let $C(n) = n/2$ if $n$ is even and $3n+1$ otherwise be the Collatz function.
We look at the generating function $f_n(x) = \sum_{k=0}^\infty C^{(k)}(n)x^k$ of the iterates of the Collatz function.
The ...

**-2**

votes

**1**answer

58 views

### Extend sum function for not integers [closed]

Is it possible to extend function for any not integer y ?

**4**

votes

**0**answers

154 views

### Can $ x \sum_{k=1}^{\infty} \frac{1}{k} \Big{(}- \gamma - \psi \big{(}1-\frac{x}{k} \big{)} \Big{)} $ be simplified?

I'm interested in sums of the form $$f_{p} (x) = \sum_{k=2}^{\infty} \zeta(k)^{p} x^{k} .$$
For $p=1$, the following result is known: $$f_{1} (x) = -x \big{(}\psi(1-x) + \gamma \big{)} .$$
(That is, ...

**8**

votes

**1**answer

352 views

### Number of bounded Dyck paths with “negative length”

Let $c(n,k)$ denote the number of Dyck paths of semilength $n$ which are contained in the strip $0 \leq y \leq 2k + 1.$
They satisfy the recursion $\sum_{j=0}^{k+1}(-1)^j \binom{2k+2-j}{j}c(n-j,k)=0$ ...

**7**

votes

**0**answers

202 views

### Estimating the alternating sum $\sum_{j \ge 1} (-1)^j e^{-j^2} j^k$

I have been trying to get a lower bound on the following alternating sum but without much success:
$$
\sum_{j=1}^T (-1)^j e^{-j^2} j^k .
$$
For small values of $k$, this is easy because the first term ...

**2**

votes

**0**answers

43 views

### Counting the number of simple labelled bipartite graphs 𝐺𝑛,𝑚 with 𝑘 edges such that 𝑑1 vertices have degree 1

I have tried to count the number of simple labelled bipartite graphs $G_{n,m}$ with $k$ edges such that $d_1$ vertices have degree 1.
Has this problem been studied?
So far the only related paper I ...

**3**

votes

**0**answers

129 views

### Two kinds of generating functions

Sorry for a possibly off-the-topic question, but I am afraid to gain the necessary overview to give an answer (supposed the question is not ill-posed) is beyond my capabilities.
In the course of ...

**0**

votes

**0**answers

20 views

### Moment-augment marginal distribution (not the exact name, given by myself)

Consider a joint distribution density function $f(x,y)$ of two random variables $x$ and $y$, and define $f_{n}(x)\equiv\int\!{\rm d}y\,y^n f(x,y)$. Do they have given name(s) in probability theory ?
I ...

**0**

votes

**0**answers

93 views

### Transcendence of Euler series

Is the Euler series $\sum_{n\ge0}n!X^n\in\mathbb C[[X]]$ transcendental over $\mathbb C(X)$?

**5**

votes

**2**answers

963 views

### Analyzing the decay rate of Taylor series coefficients when high-order derivatives are intractable

This could be a soft question. I am trying to show that the $n$-th Taylor series coefficient of a function is $O(n^{-5/2})$. However, because the function is a function composition of another function ...

**0**

votes

**1**answer

176 views

### How to solve this conditional recurrence relation?(two variable and conditions)

I am trying to solve the following recurrence relation
$4 \leq n \;\; \; \; \; \;$ and $\; \; \; \; 2\leq i \leq \lfloor{\frac{n}{2}}\rfloor$
$F(2i,n)=$
$\begin{cases}
\frac{1}{2(2i)-5}F(2i-2,...

**1**

vote

**0**answers

80 views

### Counting unions of unlabelled connected graphs

My question can be stated as follows: let $X$ be a hereditary family of unlabelled graphs closed under disjoint unions. Suppose we know, for each $n$, the number $c_n$ of connected graphs in X on $n$ ...

**11**

votes

**1**answer

260 views

### Is there a bijective proof of an identity enumerating independent sets in cycles?

Let $C_m$ be the cycle with $m$ vertices, defined so that $C_1$ has a self-loop on its unique vertex. Let $p_m$ be the generating function enumerating the number of ways to choose $k$ vertices in $C_m$...

**15**

votes

**0**answers

197 views

### Lie theoretic meaning to $e^{\text{cycle}} = \text{permutation}$?

It is well known that exponentiating the EGF(exponential generating function) for cycles gives the EGF for permutations: link here. Usually summarized under the catchy slogan ...

**1**

vote

**1**answer

98 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

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

**8**

votes

**1**answer

212 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

37 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

194 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

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

**8**

votes

**3**answers

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

**7**

votes

**0**answers

150 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

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

**8**

votes

**7**answers

583 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

105 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

126 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

179 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

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