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.

Filter by
Sorted by
Tagged with
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 $...
Boby's user avatar
  • 631
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 + ...
Math Man's user avatar
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 ...
Benjamin L. Warren's user avatar
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} \...
José María Grau Ribas's user avatar
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 ...
James Propp's user avatar
  • 19.4k
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,...
Keshav Srinivasan's user avatar
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 ...
Fox Mulder's user avatar
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 ...
Jeanne Scott's user avatar
  • 1,847
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_{...
José María Grau Ribas's user avatar
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)...
Max Muller's user avatar
  • 4,485
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 ...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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}\...
BookWick's user avatar
  • 149
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 $$...
T. Amdeberhan's user avatar
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 ...
Richard Stanley's user avatar
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}) \...
Daniil Rudenko's user avatar
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} \...
tomate's user avatar
  • 503
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 ...
Daniela 's user avatar
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\,. $...
Arkadij's user avatar
  • 914
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-...
Drew's user avatar
  • 1,469
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,\...
Dragan Stevanovic's user avatar
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. ...
Ivan Molotov's user avatar
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 ...
mathoverflowUser's user avatar
-2 votes
1 answer
71 views

Extend sum function for not integers [closed]

Is it possible to extend function for any not integer y ?
Филипп Цветков's user avatar
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, ...
Max Muller's user avatar
  • 4,485
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$ ...
Johann Cigler's user avatar
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 ...
nichehole's user avatar
  • 373
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 ...
Helene's user avatar
  • 21
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 ...
Hans-Peter Stricker's user avatar
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)$?
joaopa's user avatar
  • 3,655
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 ...
Alex's user avatar
  • 212
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,...
Fatemeh's user avatar
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$ ...
Bogdan's user avatar
  • 183
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$...
Mark Wildon's user avatar
  • 10.8k
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 ...
Siddharth Bhat's user avatar
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}\...
Koko Nanahji's user avatar
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}...
Koko Nanahji's user avatar
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 ...
user avatar
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.,...
Math is like Friday's user avatar
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 ...
Johnny Cage's user avatar
  • 1,543
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-...
T. Amdeberhan's user avatar
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$? ...
T. Amdeberhan's user avatar
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: $$\...
T. Amdeberhan's user avatar
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\...
VS.'s user avatar
  • 1,816
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 ...
Colin Defant's user avatar
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 ...
user2679290's user avatar
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 ...
WhatsUp's user avatar
  • 3,232

1 2
3
4 5
8