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.

Filter by
Sorted by
Tagged with
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 ...
The Substitute's user avatar
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(...
Richard Stanley's user avatar
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$, ...
Johnny Cage's user avatar
  • 1,543
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 ...
Richard Stanley's user avatar
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}\...
Igor Pak's user avatar
  • 16.3k
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(...
Severyn Kh's user avatar
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 ...
David E Speyer's user avatar
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 $$ \...
Oleksandr  Kulkov's user avatar
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!...
T. Amdeberhan's user avatar
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 ...
T. Amdeberhan's user avatar
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&...
Mike Stay's user avatar
  • 1,532
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) = \...
Gupta's user avatar
  • 268
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}\...
qifeng618's user avatar
  • 838
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 ...
Jerry's user avatar
  • 77
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 ...
mttt's user avatar
  • 1
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 ...
James Propp's user avatar
  • 19.4k
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 ...
Vladimir Dotsenko's user avatar
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 ...
Fabius Wiesner's user avatar
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$ ...
Sam Hopkins's user avatar
  • 22.7k
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)=\...
Kane's user avatar
  • 43
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{\...
Kane's user avatar
  • 43
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 ...
blizzard's user avatar
  • 101
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+...
M.G.'s user avatar
  • 6,683
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 ...
Andrius Kulikauskas's user avatar
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 ...
Johann Cigler's user avatar
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 ...
T. Amdeberhan's user avatar
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\...
Fancier of Mathematica's user avatar
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} = \...
mathoverflowUser's user avatar
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 ...
Leox's user avatar
  • 546
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 ...
Vlad Matei's user avatar
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-...
qifeng618's user avatar
  • 838
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$ ...
Sam Hopkins's user avatar
  • 22.7k
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}$...
VSP's user avatar
  • 233
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-...
VSP's user avatar
  • 233
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 ...
T. Amdeberhan's user avatar
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 ...
Alex Elzenaar's user avatar
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}\...
Sam Hopkins's user avatar
  • 22.7k
-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 ...
Milo Moses's user avatar
  • 2,809
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 ...
Notamathematician's user avatar
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 ...
qifeng618's user avatar
  • 838
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, ...
Sam Hopkins's user avatar
  • 22.7k
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}}$...
Johann Cigler's user avatar
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 ...
fewfew4's user avatar
  • 233
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) ...
Rybin Dmitry's user avatar
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,...
T. Amdeberhan's user avatar
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\...
José María Grau Ribas's user avatar
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\...
Max Muller's user avatar
  • 4,485
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 ...
Nicolas Medina Sanchez's user avatar
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 ...
Tiago's user avatar
  • 59
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 ...
Anixx's user avatar
  • 9,306

1
2
3 4 5
8