Questions tagged [generating-functions]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
12
votes
2answers
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
1answer
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
1answer
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
1answer
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
1answer
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
2answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
58 views

Extend sum function for not integers [closed]

Is it possible to extend function for any not integer y ?
4
votes
0answers
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
2answers
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
3answers
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
0answers
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
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
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
7answers
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
1answer
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
1answer
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
0answers
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
1answer
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 ...

1
2 3 4 5 6