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

356
questions

6
votes

1
answer

419
views

### Combinatorial consequences of de Branges's Theorem?

I'm usually not a proponent of the mentality “here is a tool, what results can we prove with it?” (as I prefer to start at the other end with a well-motivated problem), but this famously entertaining ...

3
votes

0
answers

183
views

+50

### Number of partitions of set restricted by sum of square of part size

Let $p_1^{a_1}p_2^{a_2}\cdots$ denotes the integer partition of $n$, i.e. $a_1p_1+a_2p_2+\cdots=n$. Or equivalently $m_1+m_2+\cdots=n$. It is known that the number of partitions of set $\{x_1,x_2,\...

2
votes

0
answers

243
views

### Combinatorial meaning of a binomial expansion

Let $F$ be a generating function $F(x) = \sum_{i=0}^\infty f_i x^i$, and
suppose that we can do operations formally without worrying about
convergence issues.
Define the coefficients
\begin{gather*}
...

4
votes

0
answers

148
views

### Sum $f(n_1,n_2,\ldots,n_k) 1^{n_1} 2^{n_2} \ldots k^{n_k}$ over partitions

Use the notation $(n_1,n_2,\ldots,n_k) \vdash n$ to denote that $(n_1,n_2,\ldots,n_k)$ is a partition of the positive integer $n$, that is, $n_1+n_2+\ldots+n_k = n$ and $n_1 \ge n_2 \ge \ldots \ge n_k ...

3
votes

1
answer

141
views

### $q$-series and Stirling of the 1st kind

Denote the (unsigned) Stirling numbers of the $1^{st}$-kind by ${n \brack k}$ and define
$$\mathbf{F}_a(q)=\sum_{m\geq1}\frac{q^{am}}{(1-q^m)^{2a}} \qquad \text{and} \qquad
\mathbf{G}_b(q)=\sum_{m\...

1
vote

0
answers

78
views

### Suitable recursion for the A234289

Let $a(n)$ be A234289 i.e. integer sequence with exponential generating function
$$
A(x)=1+A(x)^2\int \frac{1}{A(x)}\,dx
$$
The sequence begins with
$$
1, 1, 3, 17, 147, 1729, 25827, 468593, 10012083, ...

1
vote

2
answers

143
views

### Transcendental functions with two prescribed values

Let $\alpha$ and $\beta$ two algebraic numbers lying in unit ball. Let $T:=(t_k)_k$ be an increasing sequence of positive integers such that $t_{k+1}/t_k$ tends to $1$ as $k\to \infty$.
I would like ...

1
vote

0
answers

72
views

### Recursion for the A006014 using difference of binomial coefficients

Let $a(n)$ be A006014 i.e.
$$
a(n)=na(n-1)+\sum\limits_{j=1}^{n-2}a(j)a(n-j-1), \\
a(1)=1
$$
Also generating function $A(x)$ satisfies
$$
A(x) = x(1 + A(x) + A(x)^2 + xA'(x))
$$
Let
$$
R(n,q)=\sum\...

0
votes

0
answers

58
views

### Recursion for a given series reversion

Define the operator $\operatorname{SR}$, which is associated with the series reversion.
Let $a(n,m,k)$ be an integer sequence with generating function
$$
\frac{1}{x}\operatorname{SR}(x\frac{1-mx}{1-kx}...

4
votes

0
answers

115
views

### Something (which might be called multi-continued fraction) for the A112487

Let $a(n)$ be A112487 i.e. an integer sequence with exponential generating function
$$
A(x)=\exp\left(\int (A(x)+A(x)^2)\,dx\right), \\
A(0)=1
$$
However, the definition in the name of the sequence is
...

0
votes

0
answers

95
views

### Recursion for the A266328 by analogy with non-standard recursion for factorials

Let $a(n)$ be A266328 i.e. an integer sequence with exponential generating function
$$
A(x)=\exp\int B(x) \,dx
$$
such that
$$
B(x)=\exp(-x)\exp\int A(x) \,dx
$$
where the constant of integration is ...

0
votes

0
answers

76
views

### Simple recursion for the A129179

Let $T(n,k)$ be A129179, i.e., an integer coefficient with generating function
$$
G(t,z) = 1 + zG(t,z) + tzG(t,t^2z)G(t,z)
$$
Other generating functions are $\frac{1}{G_1(t,z,0)}$ and $\frac{1}{G_2(t,...

0
votes

2
answers

190
views

### Simplification of hypergeometric Function

First of all I am not at all a math expert, but I have some working knowledge.
That said, please excuse "dumb" questions.
I am looking at the following process: Assume you are on the 2-...

0
votes

0
answers

146
views

### Expansion of continued fraction using recursion

Let $f(n)$ be an arbitrary function such that $f(n)\in\mathbb{Z}$.
Let $a(n)$ be an integer sequence with generating function $\frac{1}{G(0)}$ where
$$
G(j)=1-\frac{f(j)x}{G(j+1)}
$$
Here we have
$$
G(...

0
votes

0
answers

60
views

### General patterns for partial sums of generalized A341392, A284005 and A329369

Let
$$\ell(n)=\left\lfloor\log_2 n\right\rfloor$$
$$f(n)=n-2^{\ell(n)}$$
$$\operatorname{wt}(2n+1)=\operatorname{wt}(n)+1, \operatorname{wt}(2n)=\operatorname{wt}(n), \operatorname{wt}(0)=0$$
$$T(n,k)=...

4
votes

0
answers

196
views

### Extract this constant term

Given a Laurent polynomial $F$ in the variables $\mathbf{t}=(t_1,\dots,t_n)$, let $CT_{\vec{\mathbf{t}}}\,F$ denote its constant term.
For example, $CT_{t_1,t_2}((8t_1-\frac1{3t_1t_2})(5t_1t_2+t_2^2+\...

2
votes

1
answer

314
views

### Products involving exponents of tribonacci numbers

The Fibonacci numbers $F_n$ can be given by
$$\sum_{k\geq0}F_kx^k=\frac{x}{1-x-x^2}.$$
Among many many properties of this sequence, consider the following two results:
(1) the coefficients of the ...

0
votes

0
answers

68
views

### Sequences that sum up to possible generalization of Euler or up/down numbers (A000111)

Let $a(n,m,k)$ be an integer sequence with e.g.f.
$$A(x)=\operatorname{exp}\left(x + m\int\int (A(x))^k \, dx \, dx\right)$$
I don't know much about integrals, so here's a concrete example:
$a(n,1,3)$...

1
vote

0
answers

73
views

### Application of the series reversion

Let $f(n)$ be an arbitrary function such that $f(n)\in\mathbb{Z}$.
Let $a(n)$ be an arbitrary integer sequence such that $a(0)=1$.
Let $b(n)$ be an integer sequence such that
$$b(2^m(2n+1))=\sum\...

0
votes

1
answer

171
views

### Fibonacci and product polynomials

The motivation for my current question arises from this MO post by R. Stanley. Caveat. There's a slight alteration.
With the convention $F_1=F_2=1$ for the Fibonacci numbers, define the polynomials $...

0
votes

0
answers

34
views

### Representation theorem for multivariate homogeneous linear recurrences on Z^d?

Let $f:\mathbb{Z}^d \to \mathbb{C}$ satisfy a homogeneous linear recurrence for some coefficients $a_\Delta \in \mathbb{C}$,
$$\forall x \in \mathbb{Z}^d. \quad \sum_{\Delta \in B_k(0)}a_\Delta f(x+\...

0
votes

1
answer

170
views

### Closed formula for Hermite polynomials

Hermite polynomials $H_k(x), x \in \mathbb{R}, k \in \mathbb{N}$ are defined by the formula
$$
H_k(x)=(-1)^k e^{x^2} \frac{d^k}{d x^k}\left(e^{-x^2}\right) .
$$
Each $H_k(x)$ is a polynomial of exact ...

1
vote

1
answer

117
views

### How to interpret this result modulo $(y-1)^{n+1}$?

I recently discovered that the following identity is true:
$$
\boxed{\frac{\partial^{n+1}}{\partial x^{n+1}}\left(\frac{(xy-1)^n}{n!} \log \frac{1}{1-x}\right) \equiv \frac{y^{n+1}}{1-xy} \pmod{(y-1)^{...

0
votes

0
answers

70
views

### When is the logarithmic generating function of relative compositions negative at −1?

Suppose $f\colon \mathbb{N} \to \mathbb{R}$. Define the logarithmic generating function of $f$ to be
$$
L_{f}(x) = \sum_{k = 1}^\infty f(k) \frac{x^k}{k}.
$$
This is in contrast to the exponential ...

1
vote

0
answers

52
views

### Over a given finite field, how many couples of matrices there are, for which their minimal polynomials are co-prime?

Let ${\mathbb F}_{q}$ be a given finite field. How many couples of $n\times n$ matrices $\left(A,B\right)$ over ${\mathbb F}_{q}$, such that $\gcd\left(\mu_{A}\left(\lambda\right),\mu_{B}\left(\lambda\...

8
votes

1
answer

224
views

### Use of generating functions in logic

Are there any uses of generating functions within logic, in particular to count how many models exists for a given theory $T$, say in FOL?
The concrete problem I'm hoping to apply this to involves ...

3
votes

1
answer

236
views

### name for products of the form $\prod_i (1 + a_i t^i)$

In the context of generating functions, is there an established name for (infinite) products of the form $\prod_i (1+a_it^i)$, or perhaps more generally $\prod_i (1+f_i(t))$, assuming that the ...

4
votes

0
answers

383
views

### Explicit formula for tournament sequence

I am looking for an explicit formula for a sequence. The sequence is generated as follows:
There is a tournament with $10$ teams. In the beginning, all teams have a 0-0 win-loss record. The teams are ...

2
votes

0
answers

101
views

### Asking for a generating function for an arithmetic sequence

For fixed integer $n\geq1$, let $c_m(n)$ be the number of divisors $d$ of $m$ such that $n<d\leq 2n$. Here is an experimental generating function for which I ask:
QUESTION. Is this true?
$$\sum_{m\...

0
votes

0
answers

79
views

### Arithmetic triangles and unimodality of its rows

Let's consider the sequence of coefficients of $\prod_{i}\frac {1-x^{d_i}} {1-x}$, where $d_i$ is a monotonically increasing nonnegative integer sequence.
How to prove that the coefficients form an ...

5
votes

0
answers

215
views

### Usefulness of total algebras and exotic generating series

In his first Algebra volume, Bourbaki [1] defines the structure of a “total algebra” i.e. the space of functions on a monoid $M$ (to a ring $k$) with the convolution product ( a function $f:\ M\to k$ ...

3
votes

0
answers

249
views

### Ask for a generating function or an explicit expression of a triangle of positive integers

Preliminaries
I encountered the following triangle of positive integers:
$c_{n,k}$
$n=1$
$n=2$
$n=3$
$n=4$
$n=5$
$n=6$
$n=7$
$n=8$
$k=0$
$1$
$3$
$15$
$105$
$315$
$3465$
$45045$
$45045$
$k=1$
$5$
$...

2
votes

0
answers

174
views

### Which combinatorial class do noncrossing partitions belong to?

Let $n$ be a nonnegative integer. The set $\lbrace 1,2,\ldots, n\rbrace$ is partitioned into blocks, with $p\left(n\right)$ possibilities (e.g., for permutations $p\left(n\right)=n!).$ For each block ...

14
votes

0
answers

246
views

### A conjectured rational generating function

In regard to my question here, let $G_n$
be a sequence of positive integers satisfying
$\lim_{n\to\infty}G_n=\infty$, such that the generating function
$\sum_{n\geq 1} G_nx^n$ is rational. Let
$$ P_n(...

2
votes

1
answer

144
views

### Reference for asymptotic estimates

In the way of studying an enumerative problem I have found that I have to estimate the Taylor coefficients of functions of the following form. For two polynomials $P(x)$ and $Q(x)$ with $P(0)=Q(0)=1$, ...

16
votes

2
answers

531
views

### Number of coefficients equal to $k$ in certain "Fibonacci polynomials"

Let $F_i$ denote the $i$th Fibonacci number (with $F_1=F_2=1$). Define
$$ P_n(x) = \prod_{i=1}^n (1+x^{F_{i+1}}). $$
Let $\nu_k(n)$ denote the number of coefficients of the polynomial $P_n(x)$
that ...

7
votes

2
answers

219
views

### Congruences of binomial sums

Let $a_n$ is a binomial sum, for example
$$
a_n := \sum_{k} \binom{n-k}{k} \quad \text{or} \quad \sum_{k=0}^n\binom{n+k}{n-k}\binom{2k}{k}
\quad \text{or} \quad \sum_{k=0}^n\sum_{\ell=0}^k\binom{n}{k}\...

1
vote

0
answers

96
views

### Recurrence relation of the form R(x,y)=yR(x-1,y)+(x-(y-1))R(x,y-1)

Consider the recurrence
$$
R(x,y)= yR(x-1,y)+ (x-(y-1))R(x,y-1)
$$
where for any $R(p,c)$, $c$ does not exceed $p$, and $R(p,p)=R(p,1)=1$.
I´ve tried to write $R(x,y)$ as a sum of coefficients of $R(...

8
votes

1
answer

336
views

### Two dice yielding uniform distribution, part 2

Since this question is on the front page again, a generalization.
Let $p$ be prime, and let $a$ and $b$ be positive integers with $a+b=p-1$. Is it possible to have two loaded dice, one with sides ...

3
votes

1
answer

181
views

### Representing PSET as species

In symbolic method, one often considers two operators on ordinary generating functions, namely
$$
\operatorname{PSET}F(x) = \exp\left(F(x)-\frac{F(x^2)}{2}+\frac{F(x^3)}{3}-\dots\right),
$$
and
$$
\...

3
votes

0
answers

314
views

### When does the Taylor coefficient of $e^{\sin x}$ vanish?

If $f(x)=\frac{a_1}{1!}x+\frac{a_2}{2!}x^2+\frac{a_3}{3!}x^3+\frac{a_4}{4!}x^4+\cdots$ is an exponential generating function for $\{a_k\}_{k\geq1}$ then
$$e^{f(x)}=1+\frac{a_1}{1!}x+\frac{a_1^2+a_2}{2!...

2
votes

0
answers

103
views

### A multi-variable "Fibonacci polynomial"?

There is a tremendous literature on the Fibonacci sequence, including its polynomial analogue $F_{-1}=0, F_0=1$ and
$$F_n(x)=xF_{n-1}(x)+F_{n-2} \qquad \text{for $n\geq1$}.$$
What I have found is the ...

1
vote

0
answers

56
views

### Combinatoric meaning of critical points of a generating function

In Fiore and Leinster's Objects of Categories as Complex Numbers, there's a notion of "high zero". For example, the set of triples of binary trees plus an extra point is a "high zero&...

6
votes

2
answers

737
views

### Recursion for generating functions

Suppose one has a generating function $$F(z) = \sum_{k\ge 0} f(k) z^k$$
for some $f:\mathbb{Z}\rightarrow \mathbb{Z}$. Is there a way to express an iteration of $f$ in terms of $F(z)$. E.g., $$G(z) = \...

7
votes

2
answers

796
views

### Is the Gauss hypergeometric series ${}_2F_1\bigl(\frac{1}{2},\frac{1}{2};2;t\bigr)$ an elementary function?

For $\alpha,\beta\in\mathbb{C}$ and $\gamma\in\mathbb{C}\setminus\{0,-1,-2,\dotsc\}$, Gauss' hypergeometric function ${}_2F_1(\alpha,\beta;\gamma;z)$ can be defined by the series
\begin{equation}\...

6
votes

3
answers

841
views

### Series involving power of the index

How to prove the following identity
$$ \sum_{n=1}^{\infty} \frac{n^{n-1} e^{-n}}{n!} = 1$$
analytically (which can be confirmed with $Mathematica$)? The standard trick for geometrical series does not ...

0
votes

0
answers

83
views

### What's the convergence condition for the generating function formula of Legendre polynomials?

What is the convergence condition of the next infinite series about the Legendre polynomials $P_n(x)$?
$$
\frac{1}{\sqrt{1-2xt+t^2}}=\sum_{n=0}^\infty P_n(x)t^n
$$
I know it is convergent at least ...

2
votes

1
answer

125
views

### Conjectural congruences for numbers related to Littlewood-Richardson coefficients

For $n \geq 0$, let $a_n$ be the square of the Euclidean length of the vector of Littlewood-Richardson coefficients of $\sum_{\lambda \vdash n} s_\lambda^2$, where $s_\lambda$ are the symmetric Schur ...

7
votes

0
answers

102
views

### Property of an integer sequence related to series reversion

Thinking of some questions of homotopical algebra for operads, I ended up with a following question, perhaps someone will recognize something here:
Let $\{a_n\}_{n\ge 2}$ be a sequence of nonnegative ...

3
votes

1
answer

246
views

### Analytic expression for the coefficient of a multivariate polynomial

Does there exist some method for finding an analytic expression for the coefficient of $z_1^kz_2^kz_3^k$ in:
$$[(1+z_1)(1+z_2)(1+z_3)(1+z_1z_2)(1+z_1z_3)(1+z_2z_3)(1+z_1z_2z_3)]^{k}$$
or is it ...