The tag has no wiki summary.

learn more… | top users | synonyms

42
votes
7answers
6k 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 ...
40
votes
10answers
6k 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 ...
28
votes
1answer
3k 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, ...
20
votes
2answers
848 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 ...
20
votes
1answer
741 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 ...
19
votes
1answer
617 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 \emph{tatami} condition if no four tiles meet at any point. (or you can think of it as the removal of a ...
17
votes
3answers
2k views

Need help proving that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$

Hello. I have been trying very hard to show that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$ and could not quite get anywhere. This inequality has been verified by computer ...
15
votes
4answers
971 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 ...
14
votes
2answers
425 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 ...
14
votes
1answer
380 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 ...
13
votes
1answer
530 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 ...
13
votes
1answer
840 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)$, ...
12
votes
6answers
799 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 ...
11
votes
2answers
753 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) ...
10
votes
1answer
233 views

Laurent polynomials associated to partitions and a $Q$-deformation of $\sigma(d)$

Let $\alpha \vdash d$ be a partition of $d$, i.e. $\alpha = (\alpha_1 \geq \alpha_2 \geq …\geq \alpha_l)$, where $\sum_k \alpha_k = d$. Define a Laurent polynomial in $Q$ as follows: $$ P_\alpha(Q) = ...
10
votes
1answer
342 views

Elephant populations (and Dyck words)

Hello, I'm relatively new to this forum so apologies if I have tagged my question incorrectly. I have been in contact with a wildlife biologist recently concerning counting elephant populations and ...
9
votes
4answers
808 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 ...
9
votes
5answers
1k 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 ...
9
votes
2answers
830 views

Can you find linear recurrence relation for dimensions of invariant tensors?

Let $V$ be a finite dimensional highest weight representation of a (semi)-simple Lie algebra. For each $n\ge 0$ take $a_n$ to be the dimension of the space of invariant tensors in $\otimes^n V$. In ...
9
votes
2answers
442 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 ...
9
votes
3answers
1k views

Solving a general two-term combinatorial recurrence relation

What is known about explicit (not necessarily closed-form) solutions to the recurrence $$R^n_k= (\alpha n) R^{n-1}_k + (\alpha' n + \beta' k) R^{n-1} _{k-1},$$ with initial condition $R_0^0 = 1$ and ...
9
votes
1answer
1k views

Finding recurrence relation for a sequence of polynomials

The sequence A059710 starts 1,0,1,1,4,10,35,... This satisfies the polynomial recurrence relation $$ (n+5)(n+6)a(n)=2(n-1)(2n+5)a(n-1)+(n-1)(19n+18)a(n-2)+14(n-1)(n-2)a(n-3) $$ I have a $q$-analogue ...
8
votes
5answers
1k 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 ...
8
votes
4answers
480 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 ...
8
votes
2answers
1k views

Expressions involving Eulerian numbers of the second kind: trying to show $\sum_{m=0}^{n} (-1)^m(m)m!(2n-m-2)!\left\langle\left\langle n\atop m\right\rangle\right\rangle\neq0$ for even $n$.

Considering the success of a previous question involving Eulerian numbers, I thought I might throw this question into the mix. It comes from some localization computations in GW theory, but in this ...
8
votes
2answers
712 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 ...
8
votes
3answers
565 views

Identifying the generating function $ G(a,z) = \sum_{n=0}^{\infty} a^n z^{(n+1)(n+2)/2}. $

I have computed a generating function for a problem involving a particular series, and would like to know if anyone has any references or a categorisation for it? It's $$ G(a,z) = \sum_{n=0}^{\infty} ...
7
votes
2answers
284 views

What is the number of noncrossing acyclic digraphs?

A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross ...
7
votes
1answer
738 views

Generating function for Random Walk Hitting Time, taking the wrong root

In a calculation of the hitting time for a Bernoulli random walk we have to calculate the hitting time $\tau(1)=\inf\{n\ge 0:S_n=1\}$ to reach $+1$ and the generating function has the recursion ...
7
votes
0answers
318 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) = ...
6
votes
3answers
794 views

What information do the roots of the generating function of the nontrivial zeroes of the Riemann zeta function encode.

Let $a_{m}$ be the imaginary part of the nontrivial roots of the Riemann zeta function $\zeta(s)$. Suppose we have their generating function $u(x)=\sum_{m=1}^{\infty} ...
6
votes
1answer
300 views

Generating functions with all non-zero coefficients equal to one

Inspired by this question, I have been wondering if there are any useful generating functions with all non-zero coefficients equal to one. Obviously, the trivial generating function $\frac{1}{1-x}$ ...
6
votes
2answers
684 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
1answer
238 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
votes
1answer
411 views

How to extract the diagonal from a bivariate generating function

Let $ F(s,t)= \sum_{i,j} f(i,j) s^i t^j$, which is a bivariate generating funcion of the number $f(i,j)$ for some enumeration problem. Sometimes we know about $F(s,t)$, but what we really need is the ...
6
votes
1answer
963 views

Solving recurrence equation with indexes from negative infinity to positive infinity

In many cases, the recurrence equations that people are solving involves index of only non-negative values. Here I have a recurrence equation which arises from transport of light in an infinite 1D ...
5
votes
2answers
318 views

A diagonal operation on power series

Given a formal power series $f(x,y)=\sum_{n,m\ge 0}f(n,m)\: x^n y^m$ in two variables $x$ and $y$ over some field of characteristic zero, e.g. the field of complex numbers $\mathbb C$, we define a new ...
5
votes
2answers
839 views

What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts?

For example, if $n = 10$ and $k = 3$, then the legal partitions are $$10 = 7 + 2 + 1 = 6 + 3 + 1 = 5 + 4 + 1 = 5 + 3 + 2$$ so the answer is $4$. By choosing $k$ random elements of $\{1,\ldots,2n/k\}$, ...
5
votes
1answer
714 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
votes
2answers
163 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 ...
5
votes
1answer
162 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} ...
5
votes
0answers
263 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 ...
4
votes
2answers
315 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 ...
4
votes
2answers
370 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; ...
4
votes
3answers
996 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 ...
4
votes
1answer
235 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*} ...
4
votes
0answers
78 views

Prove a complicated function (in epidemic spreading search) to be convex

When analyse epidemic spreading, I came across to prove that a complicated function $f(x)$ is convex when $0 \leq x \leq 1$. \begin{equation} f(x)=\frac{b_1g'(x) f_1(x)^{n-2}+g'(1) \gamma}{g'(1) ( ...
4
votes
0answers
173 views

probabilistic terminology for polynomials with positive coefficients

Given a polynomial $P(x) = p_0 + p_1 x + p_2 x^2 + ... + p_n x^n$ with non-negative coefficients, is there a standard name for (the function of $p_1,...,p_n$ equal to) the variance of an ...
4
votes
0answers
230 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: $$ ...
3
votes
2answers
427 views

Euler characteristics and operator indices as exponents for Laurent polynomials

This question is rather vague. Are there any natural situations which involve Laurent polynomials of the form $$\sum q^{a_i}\in\mathbb{Z}[q,q^{-1}]$$ where the $a_i$'s are either Euler characteristics ...