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
6
votes
3
answers
577
views
Tricky two-dimensional recurrence relation
I would like to obtain a closed form for the recurrence relation
$$a_{0,0} = 1,~~~~a_{0,m+1} = 0\\a_{n+1,0} = 2 + \frac 1 2 \cdot(a_{n,0} + a_{n,1})\\a_{n+1,m+1} = \frac 1 2 \cdot (a_{n,m} + a_{n,m+2})...
- 61
6
votes
2
answers
742
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
6
votes
2
answers
499
views
Any reference for the series expansion of $\Bigr[-\log(1-t)\Bigr]^x$?
Any reference that we can find the following $$\Bigr[-\log(1-t)\Bigr]^x = t^x + x t^x \sum_{k=0}^\infty \psi_k(x+k)\,t^{k+1}; \quad \mbox{for all} \, x\in \mathbb R, \, |t|<1$$
where $\psi_k(.)$ ...
- 588
6
votes
3
answers
342
views
Second order recurrence relation for third order polynomial root
Consider this recurrence relation:
$$
\begin{eqnarray*}
f_0&=&1\\
f_n&=&
\sum_{m=0}^{n-1} \frac{\left(\frac{m+3}{2}\right)_{m-1}}{\left(\frac{m+2}{2}\right)_m} f_{n-m-1} f_m\ \ \ \...
- 237
6
votes
2
answers
700
views
Negative probabilities - what are two ordinary pgfs that correspond to the gf of a half-coin?
In Half of a Coin: Negative Probabilities, author considers pgf of a fair coin represented by random variable, $X = 1_H$:
$$G_X(z) = E[z^X] = \sum_{x=0,1} z^xP(X=x) = (z^0)(1/2) + (z^1)(1/2) = \frac{...
- 247
6
votes
1
answer
465
views
$a^{th}$-root of exponential generating functions
This is a quick follow up on R. Stanley's interesting post on MO in a different direction, which might be easier.
For positive integers $a$, define the family of functions (infinite series) given by
$$...
- 41.8k
6
votes
2
answers
2k
views
Convergence issues with infinite product of formal series
Question first:
Show that if $s_1 < s_2 < \dots$ is an increasing sequence of positive integers and $P(x)$ is a nonzero polynomial then we cannot have
$$ P(x) \equiv \prod_{j=1}^\infty (1 - ...
- 1,167
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 ...
- 41.8k
6
votes
1
answer
285
views
Reference request: Reduced reflection length in Coxeter groups
I recently read this paper, where the authors define on page 26 what they call the reduced reflection length. For that we take a Coxeter group $G$ with Coxeter generators $S$ and transpositions $T$. ...
- 809
6
votes
2
answers
237
views
Quantities whose generating functions are symmetric
This is inspired by an old Putnam problem from 2005, and a solution given by Professor Greg Martin (a Professor of Mathematics at the University of British Columbia, also a user on MO). The question ...
- 25.5k
6
votes
2
answers
905
views
Closed form or/and asymptotics of a hypergeometric sum
Dear mathematicians,
I am a computer scientist wandering in the deep sea of combinatorics and asymptotics to pursue a recent interest in average case analysis of algorithms. In doing so, I designed ...
6
votes
1
answer
325
views
Formal theory of (some) generating functions in $t$ and $t^{-1}$?
I am interested in using series of the form $\sum_{n=-\infty}^{\infty} a_nt^n$ (where $a_n\in\mathbb C$) as generating functions. In general, multiplication of such series goes against the "formal ...
- 523
6
votes
1
answer
161
views
An identity for rational functions leading to equations for multiple polylogarithms
The following identity is not hard to prove:
$$
\sum_{1\leq i_1<i_2<\ldots <i_{2n}\leq N} (-1)^{i_1+\ldots+i_{2n}}\frac{(1-x_{i_1})(1-x_{i_3})\ldots(1-x_{i_{2n-1}})}{(1-x_{i_2})(1-x_{i_4}) \...
- 4,296
6
votes
1
answer
279
views
Does the following operation on modular forms yield something modular?
Let $f(z) = \sum_{n=0}^\infty a_nq^n$ be the fourier expansion of a (quasi-)modular form (with $q = e^{2\pi i z}$). Consider the following related functions:
$$f_{m,k}(z) = \sum_{n=0}^\infty a_{mn + ...
- 6,240
6
votes
1
answer
541
views
A generalization of binary Krawtchouk polynomials
I am looking for orthogonal polynomials $P_{d,m,n}$ that have their values at integers $i$ specified by the following generating function
$(1-z)^i (1+z+z^2+ \ldots + z^d)^{n-i} = \sum_{m=0}^{i+d(n-i)}...
- 61
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,696
6
votes
0
answers
204
views
Parameter independence of Stanley's "content formula". Why?
For a cell $\square$ in the Young diagram of a partition $\lambda$, let $h_{\square}$ and $c_{\square}$ denote the hook length and content of $\square$, respectively.
R. Stanley remarked following ...
- 41.8k
6
votes
0
answers
184
views
A class of symmetric functions
When attacking a symmetric problem via an asymmetric method, I encountered the following function: $$U_2(n, m) = \sum_{a = 0}^n\binom na (2^a + 2^{n - a})^m.$$
It is easy to see that this function is ...
- 3,232
6
votes
0
answers
99
views
Number of Dyck paths up to stable equivalence
Acyclic (connected) Nakayama algebras can be identified with Dyck paths via their top boundary Auslander-Reiten quivers.
Now two Nakayama algebras $A$ and $B$ should be stable equivalent in case ...
- 26.1k
5
votes
2
answers
3k
views
Number of 1 in binary representation of n
Let $1(n)$ be the number of digits $1$ in binary representation of number $n$.
For example, $13=1101_2$ so $1(13)=3\\$
Is there explicit form of $\,\,\sum{1(i)x^i} $?
I checked OEIS and didn't find ...
- 443
5
votes
5
answers
1k
views
Generating-functions: is there a relationship between a generating function and the corresponding squared generating function
Let's say we have a sequence $T(n)$ with the corresponding generating function
$$A(t) = \sum_{n = 0}^\infty T(n) t^n$$
Is there some relationship between the two functions $A(t)$ and $A(t^2)$? And ...
- 297
5
votes
2
answers
421
views
An interesting calculation of derivative
I was trying to get the probability distribution $p(n)$ from a generating function $G(s)$ like this:
$G(s) = e^{a(s-1)^2}=\sum s^np(n)$
I need first to do Maclaurin expansion of the exponential and ...
- 153
5
votes
1
answer
214
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$ ...
- 22.9k
5
votes
1
answer
291
views
Does the ordinary generating function of Bell numbers converge?
I am working in a field not really based on combinatorics, therefore I appologize if my question is in any kind invalid. Nevertheless, in my calculations, the Bell numbers appeared. I need to find ...
- 51
5
votes
1
answer
2k
views
Convergence of the series of Legendre polynomials
Consider the generating function of Legendre polynomials:
$$\frac{1}{\sqrt{1 - 2xt + t^2}} = \sum\limits^{\infty}_{n=0} P_n(x)t^n$$
Is it true that for $0<x<1, t=1$ series of Legendre ...
5
votes
3
answers
1k
views
Asymptotics of a hypergeometric series/Taylor series coefficient.
I was planning on figuring this problem out for myself, but I also wanted to try out mathoverflow. Here goes:
I wanted to know the asymptotics of the sum of the absolute values of the Fourier-Walsh ...
- 6,571
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 $...
- 5,572
5
votes
2
answers
369
views
Independent families of functions on $\omega$ of size continuum
In Hausdorff's article "Über zwei Sätze von G. Fichtenholz und L. Kantorovich''(1935) one can find the (simplified) proofs of the following two theorems:
1) There are continuum many essentially ...
- 51
5
votes
1
answer
176
views
an algebra generated by some known series
Denote the e.g.f. for the number of (unordered) rooted labeled trees on $n$ nodes by
$$\Phi(x)=\sum_{n\geq1}\frac{n^{n-1}}{n!}x^n.$$
And, the related series $\Psi(x)=\sum_{n\geq1}\frac{n^n}{n!}x^n$. ...
- 41.8k
5
votes
1
answer
920
views
beyond differentially algebraic power series
In a recent question, we learned about the existence of functions that do not satisfy any algebraic differential equation.
One nice property of such equations is that there is a good way to ...
- 5,563
5
votes
1
answer
201
views
Collapsed partitions and generating functions
Given $n\in\Bbb{N}$, the number of (unrestricted) integer partitions of $n$ are given by
$$\sum_{n\geq0}p(n)x^n=\prod_{j\geq1}\frac1{1-x^j}.$$
Define the collapsed partitions of $n$ to be the ...
- 41.8k
5
votes
1
answer
286
views
The number of partitions between two fixed partitions
Given two partitions M and N, with $M_i \leq N_i$ for all $1\leq i\leq \max\{l(M),l(N)\}$. Is there a formula for the generating function: $$\sum_{\lambda: M_i\leq \lambda_i\leq N_i} q^{|\lambda|}$$...
- 489
5
votes
1
answer
428
views
Repertory of the different sorts of operads
Many different types of operads have emerged in recent years (symmetric, shuffle, cyclic, anticyclic, coloured, etc.).
I would like, for any of these, list the following data:
Description of the ...
5
votes
1
answer
438
views
Generating function related to 2-residues of partitions
Question
Express the following power series in two commuting variables $x,y$ as an infinite product, or a short sum of infinite products:
$$
\frac{P(xy)^2}{(1-x)}\sum_{k=-\infty}^\infty(2k+1)x^{k^2}y^...
- 1,070
5
votes
1
answer
633
views
Generating function of alternating even terms in the Vandermonde Convolution
I have
\begin{equation}
G(x) = \sum_{i = 0}^{\infty} \sum_{r = 0}^{\infty} (-1)^i \binom{k}{2i} \binom{n-k}{r} x^{2i} x^{r} = \frac{1}{2} \left( (1 + x{\iota})^{k} + (1 - x \iota)^{k} \right)(1 + x)^...
- 51
5
votes
0
answers
192
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} =
\...
- 2,462
5
votes
0
answers
74
views
Complexity of calculating $f^{(n)}(0)$/extracting a coefficient of a functions taylor-series
Many combinatorial problems can be solved using generating functions.
In such a case, we obtain a function $f(x)$, which (for usual) has a taylor-expansion:
$$
f(x) = \sum_{n\ge 0 } a_n x^n
$$
So ...
- 151
5
votes
0
answers
102
views
Hooks, monomers, dimers and Young diagrams: Part II
As promised, I've upgraded my last question.
Consider the $k$-by-$n$ partition $\lambda_n=(n,\dots,n)$ and its corresponding Young diagram $Y_{n,k}$, which is a $k\times n$ rectangle of cells. Now, ...
- 41.8k
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 ...
- 151
5
votes
0
answers
169
views
operation on Ord., Exp., Dri. generating functions
The ordinary, exponential and Dirichlet generating functions for a sequence $\{a_n\}_{n\geq0}$ are given (at least on the formal side), respectively, by
$$F(x)=\sum_{n\geq0}a_nx^n, \qquad E(x)=\sum_{n\...
- 41.8k
5
votes
0
answers
1k
views
The functional equation $f(x) = qx + qxf(x) - f(x^2)$
A word (i.e., ordered string of letters) is bifix-free provided it has no proper initial string and terminal string that are identical. For example, the word $ingratiating$ has bifix $ing$, but the ...
- 399
5
votes
0
answers
351
views
Puzzling behaviour of a recursively defined sequence of functions
This question arose in connection with another problem that I described earlier in Constructing a generating function using a series with all negative and positive powers of a variable. I had certain ...
- 17.5k
5
votes
0
answers
238
views
Involutions on $[0,1]$ given by power series (related to probability generating functions)
Let $A$ be a function from $[0,1]$ to $[0,1]$. $A$ is an involution if $A(A(x))=x$ for all $x\in[0,1]$.
Which involutions $A$ exist such that $A(x)=\sum_{k=0}^\infty a_k x^k$ with $a_0=1$ and $a_k\...
- 3,787
5
votes
0
answers
207
views
Asymptotics and combinatorics
Wright's expansion of
$$
(1-z)^b\exp[A/(1-z)^c], \text{for } A > 0, 0<c<1\tag{1}
$$
is, in the words of the late, great Mark Kac "well known to those that know it well".
(See, for example, ...
- 51
5
votes
0
answers
344
views
When does a triangle of numbers have a zero row sum?
Suppose we have a triangle of numbers defined by the recurrence relation
$$\left| n \atop k \right| = f(n,k) \left| n-1 \atop k \right| +g(n,k) \left| n-1 \atop k-1 \right| + [n=k=0],$$
for some ...
- 3,253
4
votes
2
answers
589
views
Adem-Wu relations from Bullett-Macdonald identities
Question. Let $p$ be a prime. Let $q$ be a power of $p$. Let $P^0$, $P^1$, $P^2$, ... be elements of some associative $\mathbb F_q$-algebra $A$. (Here, $P^i$ does not mean $P$ to the $i$-th power; ...
- 33.2k
4
votes
1
answer
258
views
A 2nd order recursion with polynomial coefficients
I'm hoping to find "exact" an solution to the following simple recursion:
$q_m(j+1) = m \cdot q_m(j) + j(j+m)\cdot q_m(j-1)$
with initial data $q_m(0) = 1$, $q_m(1)=m$, where $m \geq 0$ is an ...
4
votes
1
answer
606
views
Generating function of a sequence involving reciprocals of binomial coefficients
Question: Is there a closed-form expression for the following sum
$$
F(z,k,r)=\sum_{n=0}^{r} \frac{z^n}{{n+k} \choose {k}}\label{sum}\tag{1}
$$
where $z\in\mathbb{C}$, and $r$, $k$ are non-negative ...
- 965
4
votes
2
answers
2k
views
How to compute the rook polynomial of a Ferrers board?
Given a Ferrers board of shape $(b_1,\ldots,b_m)$, we define $r_k$ as number of ways to place $k$ non-attacking rooks (as in Chess). In section 2.4 of Stanley's Enumerative Combinatorics (vol. 1) it's ...
- 1,015
4
votes
1
answer
398
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}}$...
- 5,572