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.
374
questions
2
votes
0
answers
177
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
267
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
148
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
546
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
236
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
104
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
356
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
202
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
315
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
113
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
58
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
741
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
943
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
849
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
127
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
127
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
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 ...
3
votes
1
answer
266
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 ...
17
votes
3
answers
737
views
Matrices of combinatorial sequences that are inverse in two ways
I'm interested in pairs $A=(a_{i,j})_{i,j=0,1,\ldots}$ and $B=(b_{i,j})_{i,j=0,1,\ldots}$ of infinite matrices for which:
They are uni-lower-triangular, i.e., $a_{i,i}=1$ for all $i$ and $a_{i,j}=0$ ...
1
vote
3
answers
269
views
Generating function of the square of Jacobi polynomial
The generating function of the Jacobi polynomials is given by
$$
\sum_{n=0}^{\infty} P_{n}^{(\alpha, \beta)}(z) t^{n}=2^{\alpha+\beta} R^{-1}(1-t+R)^{-\alpha}(1+t+R)^{-\beta}
$$
where
$$
R=R(z, t)=\...
3
votes
1
answer
454
views
Generating function of the product of Legendre polynomials
The generating function of the product of Legendre polynomials for the same $n$ is given by
\begin{aligned}
\sum_{n=0}^{\infty} z^{n} \mathrm{P}_{n}(\cos \alpha) \mathrm{P}_{n}(\cos \beta)&=\frac{\...
0
votes
1
answer
259
views
Bounds on the number of integer compositions with parts bounded from above and below
I'm looking for asymptotic bounds (as n goes to infinity) on the number of integer compositions of $n$ with parts in $[a,n]$ and separately for parts in $[a,b]$, with $1 < a < b < n$.
(To ...
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+...
12
votes
1
answer
813
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
0
answers
132
views
Hankel determinants of the sequence $(\binom{n}{m})_{n\ge0}$ and related sequences
I posted (https://math.stackexchange.com/questions/4363151/generating-functions-of-hankel-determinants-related-to-hoggatt-triangles) this question on Mathematics StackExchange but have not received a ...
6
votes
1
answer
256
views
Tanglegrams and functional equations of M. Somos
Recent references on the matter at hand include, a lecture slide The Konvalinka-Amdeberhan conjecture
and plethystic inverses and a preprint on Counting tanglegrams with species by I. Gessel; the ...
4
votes
1
answer
225
views
Ratio of the first squared and the second moment
Let $G(t)$ be a probability generating function of some integer and non-negative r. v. $X$. Suppose that
$$\lim_{t\to1}G'(t)=+\infty.$$
That is
$$
\mathbb{E}X=+\infty.
$$
Can you show that
$$
\lim_{t\...
5
votes
0
answers
191
views
An addition theorem for three functions similar to $\sin,\cos$ and $\sinh,\cosh$ and one / some questions?
Define the functions $t_k(x) = \sum_{n=0}^{\infty}{\frac{x^{3n+k}}{(3n+k)!}}$ for $k=0,1,2$. The functions then satisfy:
$
\begin{pmatrix}\exp(x) \\ \exp(\omega x) \\ \exp(\omega^2 x)\end{pmatrix} =
\...
11
votes
1
answer
656
views
Generating function for Schur polynomials
Consider the generating function
$$
G_n(x_1,x_2,\ldots,x_n, t_1,t_2,\ldots,t_n) =\sum_{\lambda}s_{\lambda}(x_1,x_2,\ldots, x_n) t_1^{\lambda_1}t_2^{\lambda_2} \cdots t_n^{\lambda_n},
$$
where the sum ...
2
votes
0
answers
50
views
Compact expression for triples of subsets with total sum zero
I am looking whether there is any compact way to write the following: Suppose we have an abelian group $G$. For a subset $A\subset G$ let $S_A$ be the sum of its elements. I want to find the number of ...
3
votes
2
answers
430
views
Ask for a reference or a proof of a combinatorial identity $\sum_{k=0}^n\binom{2n+1}{2k}\binom {k}{m} =2^{2(n-m)}\frac{2n+1}{2(n-m)+1}\binom{2n-m}{m}$
Could you please recommend a reference to or supply a proof of the following identity \eqref{combin-ID-Maclaurin}, or \eqref{first-equiv-form}, or \eqref{combin-ID-Mac-Equiv}, or \eqref{combin-ID-Mac-...
5
votes
1
answer
213
views
Coefficients obtained from ratio with partition number generating function
This is a question inspired by T. Amdeberhan's recent question, as well as another previos MO question.
For an integer partition $\lambda$, and $k\in \mathbb{N}\cup\{\infty\}$, let $|\lambda|_k$ ...
1
vote
1
answer
179
views
A continued J fraction for $a_n = \frac{1}{(n+1)^2}$?
The following is called a J continued fraction:
$$\cfrac{\alpha_0}{1+a_0x-\cfrac{b_1x^2}{1+a_1x-\cfrac{b_2x^2}{1+a_2x-\cdots}}}$$
where the constants are real numbers. Let $\alpha_n= \frac{1}{(n+1)^2}$...
0
votes
0
answers
133
views
A question on continued J-fraction
Consider the following two continued fractions $A$ and $B$:
$$\frac{\alpha_0}{1+a_0x-\frac{b_1x^2}{1+a_1x-\frac{b_2x^2}{1+a_2x-\cdots}}}$$
$$\frac{\beta_0}{1+c_0x-\frac{d_1x}{1+c_1x-\frac{d_2x}{1+c_2x-...
1
vote
1
answer
150
views
Log-concavity of sequence related to overpartitions
The number $p_1(n)$ of overpartitions of $n$ is generated by
$$\sum_{n\geq0}p_1(n)\,q^n=\prod_{k=1}^{\infty}\frac{1+q^k}{1-q^k}.$$
Let $t\in\mathbb{N}$. Now, extend this to construct a family of ...
2
votes
0
answers
92
views
Two-variable generating functions over coprime pairs
I am studying a sequence $(\alpha_{p,q})$ indexed by a pair of coprime integers; this sequence arises naturally in the study of a particular set of spaces in geometric topology, but unfortunately the ...
4
votes
1
answer
142
views
$0,1$-matrices with $1$ in every row/column vs. all $0,1$-matrices
Chapter 2, Exercise 25 of R. Stanley's "Enumerative Combinatorics" Vol. 1 asserts that
$$ \sum_{m,n \geq 0} \left(\sum_{t \geq 0} f_i(m,n)t^i\right)\frac{x^m}{m!}\frac{y^n}{n!} = e^{-x-y}\...
-1
votes
1
answer
125
views
Closed form for odd part of Bernoulli Polynomial generating function, $\sum_{k=0}^{\infty}B_{2k+1}(x)\frac{t^{2k+1}}{(2k+1)!}$ [closed]
If $B_k(x)$ are the Bernoulli polynomials, then (by definition, if you like) we get that
$$\sum_{k=0}^{\infty}B_k(x)\frac{t^k}{k!}=\frac{te^{tx}}{e^t-1}$$
My question is whether or not there is a ...
0
votes
1
answer
300
views
Generating function for partial sums of the sequence
Let $p$ and $q$ be integers.
Let $f(n)$ be A007814, the exponent of the highest power of $2$ dividing $n$, a.k.a. the binary carry sequence, the ruler sequence, or the $2$-adic valuation of $n$.
Then ...
2
votes
1
answer
504
views
What is the integral representation of the exponential function $e^{1/t}$ on $(0,\infty)$?
A function $q(x)$ is said to be completely monotonic on an interval $I$ if $q(x)$ has derivatives of all orders on $I$ and $(-1)^{n}q^{(n)}(x)\ge0$ for $x\in I$ and $n\ge0$. See Chapter 1 in the ...
20
votes
4
answers
2k
views
Non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
Is there a non-enumerative proof that, in average, less than 50% of tiles in domino tiling of 2-by-n rectangle are vertical?
It is a nice exercise with rational generating functions (or equivalently, ...
4
votes
1
answer
394
views
Generating functions for Hankel determinants of Catalan numbers
The Hankel determinants of the Catalan numbers are well known and can be written as
$d(k,n)= \det \left( C_{k + i + j} \right)_{i,j = 0}^{n - 1}=\prod_{i=1}^{k-1}\frac{\binom{2n+2j}{j}}{\binom{2j}{j}}$...
2
votes
0
answers
84
views
Finite version of Mehlers formula?
This is a crosspost from Math Stack Exchange, please let me know if this is not an appropriate use of crossposting, and I will delete.
Mehler's formula is the following identity for Hermite ...
3
votes
0
answers
106
views
Irreducible dimensions generating function for Lie algebra $\mathfrak{sl}_n$
Let $\lambda = \sum_{i = 1}^{n - 1} m_i \omega_i$ be the highest weight of irreducible representation $V(\lambda)$ of Lie algebra $\mathfrak{sl}_n$. As we know from the Weyl formula,
$$\dim V(\lambda) ...
3
votes
0
answers
123
views
$q$-series for the number of rectangles in a square lattice
Given a partition $\lambda\vdash n$ of $n$, look at its Young diagram $Y_{\lambda}$. Let $a(\lambda)$ be the number of squares (of all sizes) in $Y_{\lambda}$. For example, if $n=4$ then $a(4)=4, a(3,...
3
votes
1
answer
288
views
A generating function related to the Delannoy numbers
What is the generating function of $f_{m,n}$?
$ f_{m,n} = \begin{cases} 0 , & \text{if $m<0 $ or $ n<0$ }; \\
f_{n,m} , & \text{ if $n<m$}; \\
1, & \text{ if $0=m$ and $ n\...
1
vote
0
answers
170
views
Asymptotics of $\sum \frac{d(n)}{n}$ with generating functions
We can determine the asymptotics of partial sums involving the divisor function accurately by means of, for example, the hyperbola method: $$\sum_{n\leq N}\frac{d(n)}{n}=\frac{1}{2}(\log(N))^{2}+2\...
3
votes
0
answers
122
views
Positivity of sequences
Totally positive sequences $\lbrace a_n\rbrace_{n\in\mathbb{Z}}$ are defined as those such that the Töplitz matrix $A_{ij}=a_{i-j}$ is totally positive (all its minors are non-negative). An ...
0
votes
2
answers
752
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 ...
0
votes
0
answers
173
views
Asymptotically similar functions with opposite parity, were they considered, are they useful? Case of polynomials
So, can we transform an even function into an odd function and vice versa?
Let's consider this method:
Transformation even->odd:
Suppose $f_{even}(x)$ is a function which satisfies the following ...