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
73
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 ...
61
votes
4
answers
10k
views
Hirzebruch's motivation of the Todd class
In Prospects in Mathematics (AM-70), Hirzebruch gives a nice discussion of why the formal power series $f(x) = 1 + b_1 x + b_2 x^2 + \dots$ defining the Todd class must be what it is. In particular, ...
51
votes
2
answers
5k
views
The "square root" of a graph?
The number $f(n)$ of graphs on the vertex set $\{1,\dots,n\}$,
allowing loops but not multiple edges, is $2^{{n+1\choose
2}}$, with exponential generating function $F(x)=\sum_{n\geq 0}
2^{{n+1\choose ...
45
votes
10
answers
10k
views
The functional equation $f(f(x))=x+f(x)^2$
I'd like to gather information and references on the following functional equation for power series $$f(f(x))=x+f(x)^2,$$$$f(x)=\sum_{k=1}^\infty c_k x^k$$
(so $c_0=0$ is imposed).
First things that ...
26
votes
3
answers
4k
views
Is the sum $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0?$
I am trying to prove $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$. This inequality has been verified by computer for $k\le40$.
Some clues that might work (kindly provided by ...
26
votes
2
answers
1k
views
Partitions to different parts not exceeding $n$
Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
24
votes
2
answers
1k
views
Combinatorial meaning of the functional equation for logarithm
If we set $\exp(x)=\sum x^k/k!$, then $\exp(x+y)=\exp(x)\cdot \exp(y)$. In terms of coefficients it means that $(x+y)^n=\sum \frac{n!}{k!(n-k)!} x^ky^{n-k}$, i.e. just binomial expansion.
Now ...
22
votes
1
answer
957
views
What is the generating function for skew Young diagrams?
The problem
This strikes me as a very natural problem which should have been asked (and solved?) already.
For each positive integer k, find a nice expression for the following generating function in ...
21
votes
1
answer
1k
views
A strange sum over bipartite graphs
While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone ...
21
votes
1
answer
1k
views
Monomer-Dimer tatami tilings need better relationships with other math. Summary of results
A monomer-dimer tiling of a rectangular grid with $r$ rows and $c$ columns satisfies the tatami condition if no four tiles meet at any point. (Or you can think of it as the removal of a matching from ...
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, ...
20
votes
4
answers
3k
views
Are the q-Catalan numbers q-holonomic?
The generating function $f(z)$ of the Catalan numbers which is characterized by $f(z)=1+zf(z)^2$ is D-finite, or holonomic, i.e. it satisfies a linear differential equation with polynomial ...
19
votes
8
answers
6k
views
Generating function in graph theory
I am looking for a simple illustration of generating functions in graph theory.
So far, the matching polynomial seems to be the best. But I want something bit richer; at least a derivative should ...
19
votes
2
answers
700
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 ...
17
votes
3
answers
738
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$ ...
17
votes
1
answer
749
views
Congruences Ramanujan-style
Let $t\in\Bbb{N}$ and consider the sequences $p_t(n)$ defined by
$$\sum_{n\geq0}p_t(n)x^n=\prod_{i\geq1}\frac1{(1-x^i)^t}=(x;x)_{\infty}^{-t}.$$
The numbers $p_t(n)$ can be regarded as enumerating ...
17
votes
3
answers
487
views
What alternatives are there to the binomial poset theory of generating function families?
A natural question in combinatorics is, why are certain families of generating functions combinatorially useful, like $\Sigma_n a_n x^n$ and $\Sigma_na_n\frac{x^n}{n!}$, why are other families are not,...
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+...
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 ...
16
votes
1
answer
576
views
What is this sequence?
This is again a question that I asked at Stack Exchange, but got no answer so far, so I am trying here.
Let:
$$ a_n=\sum_{k\ge0}(k+1) {n+2\brack k+2}(n+2)^kB_k$$
$B_k$ is the Bernoulli number. ${n\...
16
votes
1
answer
436
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 ...
15
votes
4
answers
3k
views
Ordinary Generating Function for Bell Numbers
In the OEIS entry for Bell numbers, there appears a generating function
$$\sum_{k=0}^\infty B_k t^k = \sum_{r=0}^\infty \prod_{i=1}^r \frac{t}{1-it}$$
However, I could not locate any proof of ...
15
votes
6
answers
1k
views
An example of a series that is not differentially algebraic?
Motivated by this question, I remembered a question I was curious about sometime which I am sure has some easy and nice example for it as well, which I just can't think of for some reason. I want an ...
15
votes
1
answer
249
views
A formula for this generating function that is similar to the $qt$-Catalan numbers
I came up with the following conjecture:
$$
\sum_{n \ge 0} z^n \sum_{\mu \vdash n} \frac{ t^{\sum l}q^{\sum a}}{\prod (q^a - t^{l+1})(t^l - q^{a+1})} = \exp\left(\sum_{n \ge 1} \frac{z^n}{n(q^n-1)(t^n-...
15
votes
2
answers
353
views
Generating functions for objects with irrational sizes
A problem I'm investigating concerns a combinatorial class in which the 'atoms' have irrational sizes. It seems likely that this is something that has been considered before, but I haven't been able ...
15
votes
0
answers
256
views
Lie theoretic meaning to $e^{\text{cycle}} = \text{permutation}$?
It is well known that exponentiating the EGF(exponential generating function) for cycles gives the EGF for permutations: link here. Usually summarized under the catchy slogan ...
15
votes
0
answers
701
views
Wherefore art thou a Borcherds Product?
This question essentially asks how can one recognize (or rule out) that a generating function of combinatorial origin may be given as a Borcherds type product. I'll start with a motivational example: ...
14
votes
7
answers
3k
views
A special type of generating function for Fibonacci
Notation. Let $[x^n]G(x)$ be the coefficient of $x^n$ in the Taylor series of $G(x)$.
Consider the sequence of central binomial coefficients $\binom{2n}n$. Then there two ways to recover them:
$$\...
14
votes
4
answers
2k
views
Partitions-sum of divisors identity
A few years ago I first read about the marvelous Euler identity:
$\sum_{n\in\mathbb{N}}p(n)z^n=\prod_{k\geq1}\frac{1}{1-z^k}$,
where $p(n)$ is the number of partitions of $n$ ($p(0)=1$ by convention)...
14
votes
3
answers
1k
views
A seemingly simple combinatorial object that must have an easy generating function
One more question related to my earlier "Special" meanders.
I am trying to isolate simplest problems related to it. Here is one.
For a composition (i. e. a tuple of natural numbers) $\...
14
votes
1
answer
720
views
Generating function of the Thue-Morse sequence
Let $T$ be the generating function of the Thue-Morse sequence; thus,
$T(x)=x+x^2+x^4+x^7+\dotsb$. It is known that $T$ satisfies the nice
congruence
$$ (1+x)^3 T^2(x) + (1+x)^2 T(x) + x \equiv 0 \...
14
votes
1
answer
911
views
Ramanujan's Lost Notebook page 1 first equation and OEIS sequence A260195
In the 1988 Narosa edition of Ramanujan's The Lost Notebook and Other Unpublished Papers, on the first line of page 1 is the following:
$$ \Big(1+\frac1a\Big) \Bigg\{\frac{1}{(1-aq)(1-q/a)}+\frac{q(1+...
14
votes
1
answer
596
views
Which sets of lattice points have rational generating functions?
Let $P$ be a subset of $\mathbb N^d$ (or of some normal pointed affine semigroup), and suppose that $f:=\sum_{p\in P}\ t^p\in\mathbb Z[[t_1,\ldots,t_d]]$ is a rational function. What can be said ...
14
votes
1
answer
923
views
How many pairs (M, N) of sets of size n have M + N = {0, 1, ..., n^2-1}?
How many pairs (M, N) of sets of size n have M + N = {0, 1, ..., n^2-1}?
Manfred Schroeder, in Number Theory in Science and Communication, 4th edition, asks (p. 27): find all pairs of sets $(M,N)$, ...
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(...
13
votes
2
answers
1k
views
A mystery sequence
This question arose from the recent one, roots of a polynomial linked to mock theta function?. Let
$$
g(x):=\sum_{k=0}^\infty x^k\prod_{j=1}^{k-1}(1 + x^j)^2\\=1+x+x^2+3 x^3+4 x^4+6 x^5+10 x^6+15 x^7+...
13
votes
3
answers
847
views
Examples of specializations of elementary symmetric polynomials
Let $\mathcal{S}_{x}=\{x_{1,},x_{2},\ldots x_{n}\}$ be a set of $n$
indeterminates. The $h^{th}$elementary symmetric polynomial is the
sum of all monomials with $h$ factors
\begin{eqnarray*}
e_{h}(\...
13
votes
2
answers
606
views
Asymptotics of coefficients of implicitely defined generating function
I have two integer sequences $\{a_n\}_{n=0}^\infty$ and $\{b_n\}_{n=0}^\infty$. Explicit formulas for the $a_n$ are known and their asymptotic growth is fully understood. My wish is to also understand ...
13
votes
1
answer
524
views
Number of trivializations of a trivial word in the free group
Let $M$ be the free monoid on $2n$ generators $x_1,X_1,...,x_n,X_n$ and consider the set $T$ of all those elements of $M$ which map to 1 of the free group on $x_1,...,x_n$ under the homomorphism $\pi$ ...
13
votes
0
answers
1k
views
Generalization of Cauchy's identity
Let $ s_{\lambda} $ be the Schur function associated to the partition $ \lambda $.
Cauchy's identity (as in Macdonald) states that
$$
\sum_{\lambda} s_{\lambda}(X)s_{\lambda}(Y) = \prod_{i,j}(1-...
12
votes
5
answers
2k
views
Use of everywhere divergent generating functions
Generating functions are well-known to be much useful in combinatorics. But, maybe just since I am illiteral, all the applications coming in mind deal with power series, which are not just formal, but ...
12
votes
2
answers
707
views
Alternating sum of hook lengths: Part I
Given $\lambda$ an integer partition of $n$, let $h_{ij}(\lambda)$ denote the hook length of cell $(i,j)$ in the Young diagram of $\lambda$.
Is there a closed formula or a generating function for the ...
12
votes
2
answers
2k
views
What classes am I missing in the Picard lattice of a Kummer K3 surface?
Constructing the Kummer K3 of an Abelian surface $A$, we have an obvious 22-dimensional collection of classes in $H^2(K3, \mathbb{Z})$ given by the 16 (-2)-curves (which by construction do not ...
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 ...
12
votes
2
answers
666
views
Series defined by a fixed-point functional equation
Description
I my work, I met fixed-point functional equations of a very specific form. Since I am not expert in the domain of functional equations, I have not pushed the study of these very far. Here ...
12
votes
2
answers
1k
views
Positivity of sequences via generating series
There are different ways of showing that a given sequence $a_0,a_1,a_2,\dots$
of integers, say, is nonnegative. For example, one can show that $a_n$ count
something, or express $a_n$ as a (multiple) ...
11
votes
5
answers
2k
views
Coin flipping and a recurrence relation
How can one solve the following recurrence relation?
$f(n) = 1 + \frac{1}{2^n} \sum_{k = 0}^n {{n}\choose{k}} f(k)$
$f(0) = 0$
As it happens, I can show $f(n) = \Theta(\log n)$ through other means (...
11
votes
1
answer
657
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 ...
11
votes
1
answer
314
views
Generating function of a sequence is not algebraic
Let we have a sequence $\{a_{n}\}$, such that $\forall n \,\, a_{n}>0$ and $a_{n} \rightarrow\infty, n\rightarrow\infty$. Also let's suppose that we have a subsequence $\{a_{n_{k}}\}$ such that $\...
11
votes
2
answers
1k
views
Proofs of some combinatorial identities
Just wondering if anyone knows any references in the literature to bijections corresponding to the following simple generating function identities. Let $B(z)=\dfrac{1}{\sqrt{1-4z}}$ and $C(z)=\dfrac{1-...