The tag has no usage guidance.

learn more… | top users | synonyms

55
votes
8answers
8k 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 ...
44
votes
3answers
5k 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, ...
42
votes
10answers
7k 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 ...
23
votes
3answers
3k 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 ...
20
votes
2answers
921 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
810 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
4answers
1k 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
1answer
775 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 ...
18
votes
1answer
501 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 ...
16
votes
2answers
621 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
2answers
234 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 ...
13
votes
3answers
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) ...
13
votes
1answer
551 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
883 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
872 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 ...
12
votes
1answer
306 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 ...
12
votes
2answers
394 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 ...
11
votes
4answers
1k 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 ...
11
votes
1answer
217 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
2answers
509 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 ...
11
votes
2answers
773 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
1answer
377 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$ ...
10
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 ...
10
votes
1answer
291 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
355 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
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
889 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 ...
9
votes
2answers
257 views

Asymptotic growth rate of coefficients of generating function

how to calculate the asymptotic growth rate of coefficients generating function $T(z)$ satisfied this identity $T(z)=z+\frac{T(z)^3}{6}+\frac{T(z^2)T(z)}{2}+\frac{T(z^3)}{3}$
9
votes
2answers
877 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
3answers
593 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} ...
9
votes
3answers
2k 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 ...
9
votes
0answers
111 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 ...
9
votes
0answers
652 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) = ...
8
votes
4answers
710 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
1answer
518 views

Another formula for Bell numbers

Here is an observation (thanks to OEIS): $$\sum_{i=0}^\infty \frac{i^k}{i!}= B_k e,$$ where $B_k$ is the $k$-th Bell number. I might be having reading comprehension issues, but I don't see this ...
8
votes
1answer
230 views

Higher moments of information and Renyi entropy

For a given discrete probability distribution, Shannon entropy can be though as an expectation value $\langle - \log p \rangle$ (see also: What is entropy, really?, What is the role of the logarithm ...
8
votes
2answers
330 views

Determining the Lambert series for $xq+x^2q^4+x^3q^9+…+x^nq^{n^2}+…$

I am trying to determine the polynomials $P_n(x)$ from $$ xq+x^2q^4+x^3q^9+...+\ x^nq^{n^2}+...=\sum_{n\geqslant1}\frac{P_n(x)q^n}{1-xq^n}; $$ that is, $$ \sum_{d|n}x^{\frac ...
7
votes
2answers
366 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
195 views

Constructing a generating function using a series with all negative and positive powers of a variable

Trying to count certain combinatorial structures, I arrived at a construction of their generating function through a very inconvenient procedure. I realize that anybody who will read this has right ...
7
votes
1answer
905 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 ...
6
votes
3answers
372 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} + ...
6
votes
3answers
479 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 ...
6
votes
3answers
853 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
2answers
1k 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\}$, ...
6
votes
1answer
343 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
769 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
251 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
119 views

Asymptotics of a Bivariate Generating Function

I have the following generating function, $$G(x,y)=\sum_{n,k \geq 0}a(n,k)x^ny^k = \frac{(y^2-y)x+1}{(y-y^3)x^2-(y+1)x+1}$$ and I am interested in obtaining an asymptotic for the sequence $a(n,k)$ ...