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 ...
- 151
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,\...
- 261
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,648
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 ...
- 261
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\...
- 41k
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, ...
- 2,790
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 ...
- 485
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\...
- 2,790
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}...
- 2,790
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
...
- 2,790
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 ...
- 2,790
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,...
- 2,790
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-...
- 9
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(...
- 2,790
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)=...
- 2,790
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+\...
- 41k
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 ...
- 41k
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)$...
- 2,790
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\...
- 2,790
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 $...
- 41k
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+\...
- 210
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 ...
- 415
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)^{...
- 919
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 ...
- 2,209
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\...
- 21
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 ...
- 123
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 ...
- 5,343
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 ...
- 41
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\...
- 41k
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,656
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$
$...
- 716
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 ...
- 319
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(...
- 47.9k
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$, ...
- 1,483
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 ...
- 47.9k
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}\...
- 16.2k
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(...
- 11
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 ...
- 148k
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
$$
\...
- 919
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!...
- 41k
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 ...
- 41k
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&...
- 1,522
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) = \...
- 268
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}\...
- 716
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 ...
- 77
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 ...
- 1
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 ...
- 19k
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 ...
- 15.9k
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 ...
- 590