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.
377
questions
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 ...
- 19.4k
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 ...
- 2,462
11
votes
1
answer
1k
views
How to extract the diagonal from a bivariate generating function
Let $ F(s,t)= \sum_{i,j} f(i,j) s^i t^j$, which is a bivariate generating funcion of the number $f(i,j)$ for some enumeration problem. Sometimes we know about $F(s,t)$, but what we really need is the ...
- 459
10
votes
2
answers
2k
views
Expressions involving Eulerian numbers of the second kind: trying to show $\sum_{m=0}^{n} (-1)^m(m)m!(2n-m-2)!\left\langle\left\langle n\atop m\right\rangle\right\rangle\neq0$ for even $n$.
Considering the success of a previous question involving Eulerian numbers, I thought I might throw this question into the mix. It comes from some localization computations in GW theory, but in this ...
- 103
10
votes
3
answers
975
views
A diagonal operation on power series
Given a formal power series $f(x,y)=\sum_{n,m\ge 0}f(n,m)\: x^n y^m$ in two variables $x$ and $y$ over some field of characteristic zero, e.g. the field of complex numbers $\mathbb C$, we define a new ...
- 349
10
votes
3
answers
652
views
Identifying the generating function $ G(a,z) = \sum_{n=0}^{\infty} a^n z^{(n+1)(n+2)/2}. $
I have computed a generating function for a problem involving a particular series, and would like to know if anyone has any references or a categorisation for it? It's
$$
G(a,z) = \sum_{n=0}^{\infty} ...
- 337
10
votes
2
answers
1k
views
Asymptotic growth rate of coefficients of generating function
how to calculate the asymptotic growth rate of coefficients generating function $T(z)$ satisfied this identity
$T(z)=z+\frac{T(z)^3}{6}+\frac{T(z^2)T(z)}{2}+\frac{T(z^3)}{3}$
- 443
10
votes
2
answers
1k
views
Can you find linear recurrence relation for dimensions of invariant tensors?
Let $V$ be a finite dimensional highest weight representation of a (semi)-simple Lie algebra. For each $n\ge 0$ take $a_n$ to be the dimension of the space of invariant tensors in $\otimes^n V$.
In ...
- 9,052
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$ ...
- 5,572
10
votes
1
answer
348
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 ...
user82537
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$...
- 10.8k
10
votes
1
answer
383
views
Laurent polynomials associated to partitions and a $Q$-deformation of $\sigma(d)$
Let $\alpha \vdash d$ be a partition of $d$, i.e. $\alpha = (\alpha_1 \geq \alpha_2 \geq …\geq \alpha_l)$, where $\sum_k \alpha_k = d$. Define a Laurent polynomial in $Q$ as follows:
$$
P_\alpha(Q) = ...
- 5,910
10
votes
1
answer
391
views
Elephant populations (and Dyck words)
Hello,
I'm relatively new to this forum so apologies if I have tagged my
question incorrectly.
I have been in contact with a wildlife biologist recently concerning
counting elephant populations and ...
- 133
9
votes
7
answers
724
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 ...
9
votes
3
answers
2k
views
Solving a general two-term combinatorial recurrence relation
What is known about explicit (not necessarily closed-form) solutions to the recurrence
$$R^n_k= (\alpha n) R^{n-1}_k + (\alpha' n + \beta' k) R^{n-1} _{k-1},$$
with initial condition $R_0^0 = 1$ and ...
- 3,253
9
votes
1
answer
480
views
Higher moments of information and Renyi entropy
For a given discrete probability distribution, Shannon entropy can be though as an expectation value $\langle - \log p \rangle$ (see also: What is entropy, really?, What is the role of the logarithm ...
- 1,592
9
votes
1
answer
2k
views
Finding recurrence relation for a sequence of polynomials
The sequence
A059710
starts 1,0,1,1,4,10,35,...
This satisfies the polynomial recurrence relation
$$ (n+5)(n+6)a(n)=2(n-1)(2n+5)a(n-1)+(n-1)(19n+18)a(n-2)+14(n-1)(n-2)a(n-3) $$
I have a $q$-analogue ...
- 9,052
9
votes
3
answers
619
views
Finite realization of irrational transfer functions
In the field of digital signal processing, linear time-invariant systems play a distinguished role. These are the systems for which there exists an impulse response, a function $h:\mathbb{Z}\to\...
- 8,403
9
votes
2
answers
631
views
Determining the Lambert series for $xq+x^2q^4+x^3q^9+...+x^nq^{n^2}+...$
I am trying to determine the polynomials $P_n(x)$ from
$$
xq+x^2q^4+x^3q^9+...+\ x^nq^{n^2}+...=\sum_{n\geqslant1}\frac{P_n(x)q^n}{1-xq^n};
$$
that is,
$$
\sum_{d|n}x^{\frac nd-1}P_d(x)=\begin{cases}x^...
- 17.5k
9
votes
0
answers
2k
views
Which Hadamard Products of Generating Functions Are Known?
The Hadamard product, Schur product, or entrywise product of two generating functions is computed as follows:
The Hadamard Product, $H(x)$, given two generating functions $f(x)$ and $g(x)$ where
$$ ...
- 97
8
votes
3
answers
530
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-...
- 41.8k
8
votes
2
answers
276
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 ...
- 490
8
votes
2
answers
3k
views
What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts?
For example, if $n = 10$ and $k = 3$, then the legal partitions are
$$10 = 7 + 2 + 1 = 6 + 3 + 1 = 5 + 4 + 1 = 5 + 3 + 2$$
so the answer is $4$. By choosing $k$ random elements of $\{1,\ldots,2n/k\}$, ...
- 195
8
votes
1
answer
337
views
Bijective proof of formula for rooted binary forests
For $n\ge 1$, let $f(n)$ be the number of rooted complete (unordered) binary trees with $n$ leaves labeled from $1$ to $n$ ("complete binary" means that every vertex has either $0$ or $2$ children and ...
- 78.3k
8
votes
1
answer
255
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
8
votes
1
answer
2k
views
Solving recurrence equation with indexes from negative infinity to positive infinity
In many cases, the recurrence equations that people are solving involves index of only non-negative values. Here I have a recurrence equation which arises from transport of light in an infinite 1D ...
- 571
8
votes
1
answer
358
views
generalizing Wilf's conjecture: Uppuluri-Carpenter numbers
The complementary Bell numbers have the exponential generating function
$$\sum_{n\geq0}\tilde{B}_nx^n=e^{1-e^x}.$$
Herb Wilf conjectured that $\tilde{B}_n=0$ only for $n=2$. By now, there are a few ...
- 41.8k
8
votes
1
answer
260
views
Asymptotics of a Bivariate Generating Function
I have the following generating function,
$$G(x,y)=\sum_{n,k \geq 0}a(n,k)x^ny^k = \frac{(y^2-y)x+1}{(y-y^3)x^2-(y+1)x+1}$$
and I am interested in obtaining an asymptotic for the sequence $a(n,k)$ i.e....
- 313
8
votes
1
answer
358
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 ...
- 151k
8
votes
0
answers
105
views
Number of occurrences of certain generators in expressions in Coxeter groups
Let $W$ be a Coxeter group (finite or infinite) with (finite) set $S$ of Coxeter generators, and let $I \subseteq S$ be some subset. If $w\in W$ then I call $m_I(w)$ the minimum total number of ...
- 30.1k
7
votes
2
answers
962
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}\...
- 838
7
votes
5
answers
1k
views
How to calculate one Cauchy type determinant
As we know, a Cauchy determinant of size n admits the following explicit formula:
$$\det \left(\frac{1}{x _i+y _j}\right) _{1\le i,j \le n}=\frac{\prod _{1\le i < j\le n} (x _j-x _i)(y _j-y _i)}{\...
- 113
7
votes
1
answer
837
views
Another formula for Bell numbers
Here is an observation (thanks to OEIS):
$$\sum_{i=0}^\infty \frac{i^k}{i!}= B_k e,$$ where $B_k$ is the $k$-th Bell number. I might be having reading comprehension issues, but I don't see this ...
- 95.6k
7
votes
2
answers
447
views
What is the number of noncrossing acyclic digraphs?
A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross ...
- 195
7
votes
3
answers
1k
views
What information do the roots of the generating function of the nontrivial zeroes of the Riemann zeta function encode.
Let $a_{m}$ be the imaginary part of the nontrivial roots of the Riemann zeta function $\zeta(s)$. Suppose we have their generating function $u(x)=\sum_{m=1}^{\infty} a_{m}x^{m}=14.134725\ldots{}x^{1}+...
- 975
7
votes
1
answer
191
views
Sufficient conditions for the coefficients of a generating function to dominate those of its square
Let $f(z)$ be a generating function (so in particular, its power series coefficients are nonnegative). I am interested in conditions which would ensure that for every $n$, the coefficient of $z^n$ in $...
- 2,329
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, ...
- 1,899
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 ...
- 181
7
votes
2
answers
237
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.3k
7
votes
1
answer
378
views
Counting some binary trees with lots of extra stucture
While working on some computations on Hilbert schemes, I came across the following combinatorial problem.
Let $D(k,n)$ be the weighted number of binary trees (children are left/right) with $n$ ...
- 1,469
7
votes
1
answer
490
views
Constructing a generating function using a series with all negative and positive powers of a variable
Trying to count certain combinatorial structures, I arrived at a construction of their generating function through a very inconvenient procedure.
I realize that anybody who will read this has right ...
- 17.5k
7
votes
1
answer
2k
views
Generating function for Random Walk Hitting Time, taking the wrong root
In a calculation of the hitting time for a Bernoulli random walk we have to calculate the hitting time $\tau(1)=\inf\{n\ge 0:S_n=1\}$ to reach $+1$ and the generating function has the recursion ...
- 71
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,-...
- 5,572
7
votes
0
answers
110
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 ...
- 16.5k
7
votes
0
answers
310
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 ...
- 373
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$?
...
- 41.8k
7
votes
0
answers
508
views
Can we define the Mandelbrot set in terms of the generating function of the Catalan numbers?
For each complex number $c$, define $P_{0}(c)=0$ and $P_{n+1}(c) = (P_{n}(c))^{2} + c$ . The Mandelbrot set is the set of complex numbers c for which $|P_{n}(c)|$ stays bounded as $n\rightarrow \...
7
votes
0
answers
858
views
Generating function for the characteristic function of prime numbers
What do we know about the generating function of $\chi(n)$ (A010051)
$$
f(x) = \sum_{n=0}^\infty \chi(n)x^n = \sum_{p\text{ prime}} x^p
$$
for $\chi(n)$ the characteristic function of the primes:
$$...
- 191
6
votes
3
answers
850
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
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 ...
- 212