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
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, ...
Dan Kneezel's user avatar
  • 1,405
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 ...
Richard Stanley's user avatar
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 ...
Pietro Majer's user avatar
  • 56.5k
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 ...
Alexandra Seceleanu's user avatar
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 ...
Fedor Petrov's user avatar
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 ...
Fedor Petrov's user avatar
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 ...
John Murray's user avatar
  • 1,070
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 ...
Brendan McKay's user avatar
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 ...
Alejandro Erickson's user avatar
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
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 ...
Johann Cigler's user avatar
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 ...
Anton Petrunin's user avatar
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 ...
Richard Stanley's user avatar
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$ ...
Sam Hopkins's user avatar
  • 22.7k
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 ...
T. Amdeberhan's user avatar
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,...
Keshav Srinivasan's user avatar
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
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
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\...
René Gy's user avatar
  • 485
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 ...
Martin Rubey's user avatar
  • 5,533
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 ...
Amritanshu Prasad's user avatar
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 ...
Vladimir Dotsenko's user avatar
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-...
Drew's user avatar
  • 1,469
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 ...
David Bevan's user avatar
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 ...
Siddharth Bhat's user avatar
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: ...
Gjergji Zaimi's user avatar
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: $$\...
T. Amdeberhan's user avatar
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)...
Gian Maria Dall'Ara's user avatar
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) $\...
მამუკა ჯიბლაძე's user avatar
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 \...
Seva's user avatar
  • 22.8k
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+...
Somos's user avatar
  • 2,464
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 ...
Alex Fink's user avatar
  • 582
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)$, ...
Michael Lugo's user avatar
  • 13.8k
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
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+...
მამუკა ჯიბლაძე's user avatar
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}(\...
Félix's user avatar
  • 231
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 ...
nuvw's user avatar
  • 133
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$ ...
მამუკა ჯიბლაძე's user avatar
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-...
R. Rosenbaum's user avatar
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 ...
Fedor Petrov's user avatar
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 ...
T. Amdeberhan's user avatar
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 ...
Simon Rose's user avatar
  • 6,240
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
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 ...
Samuele Giraudo's user avatar
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) ...
Wadim Zudilin's user avatar
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 (...
Pradipta's user avatar
  • 501
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 ...
Leox's user avatar
  • 546
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 $\...
Skochko Vova's user avatar
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-...
Alexander Burstein's user avatar

1
2 3 4 5
8