Questions tagged [generating-functions]
A generating function is a way of encoding an infinite sequence of numbers by treating them as the coefficients of a formal power series. Tag questions involving generating functions in this.
374
questions
2
votes
1
answer
584
views
Radius of convergence of cumulant generating function
Recall that for a random variable $X$ with a moment generating function $M_X(t)$ the cumulant generating function is defined as
\begin{align}
K_X(t)=\log M_X(t)
\end{align}
The Taylor expansion of $...
4
votes
2
answers
679
views
Number of ways of distributing indistinguishable balls into distinguishable boxes with extra givens
What is the number of ways to distribute $m$ indistinguishable balls to $k$ distinguishable boxes given no box can be a unique number of balls?
for example: ($m=19$ and $k=5$)
$$x_1 + x_2 + \dots + ...
0
votes
1
answer
134
views
Is there a closed form of $\sum_{i=1}^{n-k} {n-1-i\choose k-1}x^i$ in $x$?
I'm looking for the generating function of the sum $\sum_{i=1}^{n-k} {n-1-i\choose k-1}x^i$. One can compute this using the Euler-MacLauren formula but the remainder term is a little messy. Is there ...
0
votes
1
answer
154
views
How to probe the recursiveness order of a sequence $\{S_n\}$ whose generating function is known
How to probe the recursiveness order of a sequence $\{S_n\}$ whose generating function is known:
$$ \sum_{n\geq0} S_n z^n= \frac{4 z \left(\sqrt{49 z^2-18 z+1}+7 z-1\right)}{\sqrt{49
z^2-18 z+1} \...
11
votes
1
answer
300
views
Software for recognizing algebraic or D-finite formal power series
I have a formal power series in one variable that I think might be algebraic (or perhaps just D-finite). Is there software that could help me explore this?
By way of comparison, there’s a very simple ...
17
votes
3
answers
487
views
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
484
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
194
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
338
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
889
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)...
12
votes
2
answers
707
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
43
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
204
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
258
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
1k
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}\...
6
votes
1
answer
464
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 ...
6
votes
1
answer
161
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
125
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} \...
5
votes
1
answer
286
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
144
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
249
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-...
1
vote
1
answer
214
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
473
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. ...
11
votes
1
answer
1k
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
71
views
Extend sum function for not integers [closed]
Is it possible to extend function for any not integer y ?
4
votes
0
answers
169
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, ...
10
votes
1
answer
481
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
307
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
107
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
181
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
117
views
Transcendence of Euler series
Is the Euler series $\sum_{n\ge0}n!X^n\in\mathbb C[[X]]$ transcendental over $\mathbb C(X)$?
6
votes
2
answers
1k
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
444
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
123
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$ ...
10
votes
1
answer
295
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
256
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
205
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
200
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}...
10
votes
1
answer
346
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 ...
2
votes
1
answer
273
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
192
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
526
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
171
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
3k
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
61
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\...
9
votes
7
answers
723
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
213
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
142
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
184
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 ...