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.
378
questions
0
votes
0
answers
33
views
Solving non-linear recursion with linear and exponential terms
I encountered the recursion $$\frac{a[n+2]}{a[n+1]}-e^{-\frac{a[n+1]}{a[n]}}=0$$ when trying to explain why points are apparently arranged along an exponential curve in the scatter plot of an empiric ...
2
votes
5
answers
448
views
Finding $\sum_i x_i$ given $\{\sum_i x_i^{2n}\}_{n\in \mathbb{N}}$
Can we find $\sum_i x_i$ given $\{\sum_i x_i^{2n}\}_{n\in \mathbb{N}}$, assuming $\{x_i\}_{i\in\mathbb{N}}$ is a set of positive real numbers?
Perhaps an easier question is, can we find $\sum_i x_i$ ...
4
votes
0
answers
204
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 ...
2
votes
1
answer
126
views
Weak compositions with no subcomposition adding to (more than) $j$
Here is a solution to a problem from Stanley's Enumerative Combinatorics (it's listed as a difficulty 2, so I imagine what I'm about to ask is likely a 2+ or 3-) about the number $\kappa(N,k,j)$ of ...
8
votes
2
answers
278
views
Counting $m\times n$ $\bigl({1\atop1}{1\atop0}\bigr)$-free $(0,1)$-matrices
Let $G_{m,n}$ denote the number of $m\times n$ $(0,1)$-matrices that avoid the submatrix $\bigl({1\atop1}{1\atop0}\bigr)$. (Submatrices need not be contiguous.) Here are some small values (not yet on ...
3
votes
1
answer
391
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$
$...
0
votes
2
answers
286
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
2
answers
771
views
Product of three or more independent sub-Gaussian varibles
A random variable $X$ is called subgaussian of order $\sigma^2$ if $\log E[exp\{\theta X\}]\leq \frac{1}{2}\theta^2\sigma^2$ for every $\theta\in\mathbb R$.
Given a sequence of independent subgaussian ...
7
votes
1
answer
605
views
Generating functions with all non-zero coefficients equal to one
I have been wondering if there are any useful generating functions with all non-zero coefficients equal to one. Obviously, the trivial generating function $\frac{1}{1-x}$ has significant applications, ...
0
votes
0
answers
28
views
Moment generating function for product states
In the sequel $B=M_\ell(\mathbb{C})$.
For $M\in\mathbb{N}$ fixed and $N\geq M$ I consider the symmetrizer $\pi_{M,N}(x_M)\in B^{\otimes N}$, which is the symmetrized tensor product of $a_1$,...,$a_M$ ...
5
votes
1
answer
117
views
Identities for the generating functions of a sort of convolution powers of the Narayana numbers
Let $c(x)=\frac{1-\sqrt{1-4x}}{2x}$ be the generating function of the Catalan numbers.
It satisfies $$\frac{1}{c(x)^k}+x^k c(x)^k=L_k(1,-x),$$
where $L_n(x,s)$ denote the Lucas polynomials defined by $...
2
votes
1
answer
244
views
The probability that iid draws from a mean zero random variable sum to zero
Suppose we have a probability distribution $p(\cdot)$ supported on the integers between $-m$ and $m$ for some positive integer $m$, with $\sum_k kp(k) = 0$. Suppose furthermore that all $p(k)$ are ...
12
votes
1
answer
817
views
How are Sheffer polynomials related to Lie theory?
Sheffer polynomials $\{P_n(x)\}$ have generating function $P(x,t) = \sum_{n=0}^{\infty}P_n(x)t^n=A(t)e^{xu(t)}$.
This form reminds me of the Lie group–Lie algebra correspondence. Is there any ...
1
vote
2
answers
314
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 ...
5
votes
1
answer
715
views
Meaningful interpretation for fixed point of a probability generating function
Suppose $f$ is the probability generating function for the Galton-Watson branching process.
What intuition makes the fact that $f(s) = s$ is the probability of extinction obvious? Moreover, can one ...
0
votes
0
answers
45
views
$R$-recursion for the A007165
Let $a(n)$ be A007165 i.e. number of $P$-graphs with $2n$ edges. Here ordinary generating function $A(x)$ satisfies
$$
A(x) = \frac{(1 + xA(x))(1 + 2xA(x))}{1 + 2xA(x) - (xA(x))^2}
$$
Let
$$
R(n, q) = ...
1
vote
0
answers
48
views
$R$-recursion for the A036765
Let $a(n)$ be A036765 i.e. number of ordered rooted trees with $n$ non-root nodes and all outdegrees $\leqslant 3$. Here
$$
a(n) = \frac{1}{n+1}\sum\limits_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\...
1
vote
1
answer
85
views
$R$-recursion for the A307389
Let $a(n)$ be A307389 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A(x)=\exp\left(\frac{\exp(2x)-2\exp(x)+2x+1}{2}\right)
$$
The sequence begins with
$$
1,...
1
vote
1
answer
91
views
General case of the some $R$-recursions
Let $f(n)$ be an arbitrary function.
Let $a(n)$ be an integer sequence such that its ordinary generating function satisfies
$$
A(x)=\sum\limits_{i=0}^{\infty}\frac{x^i}{\prod\limits_{j=0}^{i}(1-f(j)x)...
16
votes
6
answers
1k
views
A Leibniz-like formula for $(f(x) \frac{d}{dx})^n f(x)$?
Let $f(x)$ be sufficiently regular (e.g. a smooth function or a formal power series in characteristic 0 etc.). In my research the following recursion made a surprising entrance
$$
f_1(x) = f(x),\ f_{n+...
2
votes
1
answer
668
views
Transfinite sums related to a sequence
Given a sequence $S$ indexed by the finite ordinals, a limit ordinal $\alpha$, and $k \in \mathbb{N}$, define $S_{\alpha+k}$(the extension of $S$ to $\alpha+k$) to be the sum over the products of all $...
3
votes
0
answers
69
views
$R$-recursion for the A249833 (similar to A235129)
Let $a(n)$ be A249833 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A(x) = 1 + \int A(x) + (A(x))^2\log A(x)\,dx
$$
The sequence begins with
$$
1, 1, 2, 7, ...
2
votes
0
answers
102
views
$R$-recursion for the A235129
Let $a(n)$ be A235129 i.e. an integer sequence such that its exponential generating function $A(x)$ satisfies
$$
A'(x) = 1 + A(x)\exp(A(x))
$$
The sequence begins with
$$
1, 1, 3, 12, 64, 424, 3358, ...
4
votes
2
answers
181
views
How to diagonalize this tridiagonal difference operator with unbounded coefficients?
Problem: I have a self-adjoint operator in $\ell^2(\mathbb{Z})$ which acts as
$$T g(x)=q^{-2 x -3/2} g(x+1)+(1+q) q^{-2 x-1} g(x)+q^{-2 x +1/2} g(x-1),$$
and I am looking to diagonalize it. The ...
0
votes
1
answer
158
views
A self-consistent equation that turns into a differential equation
Suppose the function $f(x,y)$ is defined on a small neighbourhood of $(0,0)$ in $\mathbb{R} \times [0,\infty)$ and satisfies the self consistent equation
\begin{align*}
& f(x,y) = \frac{1}{1-y} + ...
1
vote
2
answers
248
views
Recurrence relation with two variables
I am stuck on a recurrence relation with two variables. I'm familiar with techniques to solve recurrence relations with one variable and looked into ways to solve recurrence relations with multiple ...
2
votes
1
answer
202
views
Generating function over primes in an arithmetic progression
Given a newform $\sum_{n=1}^{\infty}a(n)q^n$. Is the generating function
$$
\sum_{p\equiv a\pmod{m}}a(p)q^p
$$
over the primes $p\equiv a\pmod{m}$ still a modular form? Any help is highly appreciated! ...
16
votes
1
answer
437
views
Types of generating functions (ordinary, exponential, ???) closed under substitution
A nice feature of ordinary and exponential generating functions is that they are closed under substitution: if $F(z)$ and $G(z)$ both have integer coefficients, then $F(G(z))$ also has integer ...
2
votes
1
answer
189
views
Slicing bivariate exponential generating functions on x and y
Let $F(x, y) = e^{y D(x)}$ be a generating function for sets of objects enumerated by $D(x)$ that also keeps track of the number of sets (enumerated by the variable $y$, while $x$ enumerates the total ...
1
vote
2
answers
346
views
A closed formula for a sum involving hypergeometric function
Let ${ }_1 F_1(a ; c ; z)$ be Kummer's function defined by the function, and all its analytic continuations, represented by the infinite series $\sum_{n=0}^{\infty} \frac{(a)_n}{(c)_n} \frac{z^n}{n !...
20
votes
2
answers
709
views
A rational function related to Fibonacci numbers
Let $F_n$ denote a Fibonacci number ($F_1=F_2=1$,
$F_{n+1}=F_n+F_{n-1}$ for $n\geq 2$). Define
$$\prod_{k=1}^n (1+x^{F_{k+1}}) = \sum_j f(n,j)x^j. $$
For a positive integer $r$ let
$$ v_r(n) = \sum_j ...
2
votes
1
answer
330
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*}
...
7
votes
0
answers
267
views
A conjecture about Hankel determinants of path generating functions
Let $a_{n,k}=a_{n,k}(x,c)$ be the generating function $\sum_P w(P),$ where $P$ runs over all paths from $(0,0)$ to $(n,k)$ consisting of horizontal steps $(1,0)$, up-steps $(1,1)$ and down-steps $(1,-...
74
votes
9
answers
15k
views
What is Lagrange Inversion good for?
I am planning an introductory combinatorics course (mixed grad-undergrad) and am trying to decide whether it is worth budgeting a day for Lagrange inversion. The reason I hesitate is that I know of ...
1
vote
0
answers
75
views
How to calculate the Integral with confluent hypergeometric function
How to prove this.Thank you in advance
Let $\delta,\beta>0$ How to prove this
\begin{align}
& \int^1_0 \frac{w^{1-\beta}}{(1-w)^{1+\delta}} (-t.s w)^{\frac{-\delta}{2}} e^{-\frac{w}{1-w}(s+t)}...
7
votes
1
answer
475
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
213
views
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,\...
6
votes
0
answers
252
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
1
answer
152
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
85
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
151
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
77
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
68
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
118
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
100
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
78
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
0
answers
169
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(...
4
votes
0
answers
200
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+\...
0
votes
0
answers
63
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)=...
1
vote
1
answer
332
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 ...