# Tagged Questions

**4**

votes

**2**answers

131 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 ...

**1**

vote

**0**answers

94 views

### Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$
\begin{array}{cccccccccc}
1 & = & ...

**9**

votes

**4**answers

759 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 ...

**4**

votes

**1**answer

217 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*}
...

**0**

votes

**0**answers

85 views

### Estimating when does a certain binomial sum exceed an upper bound

Given a fixed integer $n > 0$ and $0 \le m \le n$ let us define the numbers
$$f_{n,m} = \sum_{i=\lfloor m/2 \rfloor}^m {n-2i \choose n - m -i}{i+1 \choose m - i +1}.$$
For example $f_{n,0} = ...

**1**

vote

**0**answers

118 views

### How to prove this identity? (Perhaps related to partition) [closed]

How to prove this identity?
$ \sum_{n\ge 0} \frac{x^{n^2}}{(1-x)(1-x^2)\cdots(1-x^n)}= \frac{1}{\prod_{k \ge 0}(1-x^{5k+1})(1-x^{5k+4})}$
I will appreciate it a lot if a solution using method ...

**3**

votes

**0**answers

111 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, ...

**1**

vote

**1**answer

235 views

### An infinite product: combinatorial interpretation

It is an undergraduate exercise to show that the generating function for the sequence of unrestricted integer partitions $p(n)$ is the celebrated infinite product
...

**2**

votes

**2**answers

809 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 ...

**5**

votes

**1**answer

156 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} ...

**-1**

votes

**1**answer

242 views

### Does anyone recognize this generating function [closed]

$a_1=1, a_2=1, a_3=3, a_4=15, a_5=105$
Reccurence formula is
$a_{k+1}=\sum\limits_{\lambda_1+\lambda_2+\ldots+\lambda_s=k,\ \lambda_i\geq1} a_{\lambda_1}a_{\lambda_2}...a_{\lambda_s}{k \choose ...

**2**

votes

**0**answers

75 views

### Lagrangean equations for the generating function of quadrangulations

Let $M(z)$ be the generating function of edge-rooted connected quadrangulations, with $z$ marking the number of edges. I derived the following Lagrangean equations for $M(z)$:
$$M(z) = ...

**2**

votes

**2**answers

302 views

### Asymptotic behaviour of sequence

I am interested in the sequence
$$a(n)=\sum_{k=0}^n {p(n-k) \choose k}$$
where $p(n)$ is a polynomial equation.
When $p(n)=n$ this reduces to the Fibonacci sequence, but what about when $p(n)$ is ...

**2**

votes

**1**answer

439 views

### Recurrence relation for coefficients of product of generating functions for partition numbers

It is well known that
$$Z(x,q) = \prod_{n=1}^\infty\frac{1}{(1-xq^n)} = \sum_{m=0}^\infty\sum_{k=0}^m p_{m,k}x^kq^m$$
is the generating function for the number $p_{m,k}$ of partitions of $m$ in ...

**6**

votes

**1**answer

294 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}$ ...

**1**

vote

**0**answers

79 views

### Generating series of free PROs

Let
\begin{equation}
G := \biguplus_{p \geq 0} \: \biguplus_{q \geq 0} G(p, q)
\end{equation}
be a bigraded set of generators and $\mathcal{F}(G)$ be the free PRO generated by $G$ (see [1] for a net ...

**0**

votes

**0**answers

106 views

### Using extended group rings for combinatorial generating functions

In work of mine recently, I have come to investigate generalised recurrence relations. The generalisation I have in mind is where, instead of natural numbers or integers, the recurrence is over some ...

**9**

votes

**2**answers

437 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 ...

**3**

votes

**1**answer

229 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 ...

**6**

votes

**0**answers

287 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) = ...

**14**

votes

**2**answers

413 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 ...

**9**

votes

**1**answer

340 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 ...

**16**

votes

**0**answers

459 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 ...

**2**

votes

**2**answers

755 views

### Proving generating functions equality

What do you use to prove the following equality (and possibly more general ones of the kind)?
\begin{align*}\sum_{r,s,t} \frac{q^{r^2+rs+s^2+st+t^2}}{(q)_r (q)_s (q)_t} z_1^{r+s} z_2^{s+t} = ...

**2**

votes

**1**answer

381 views

### Generating function for Dyck Words

Hello,
I'm trying to reinvent the wheel here by deriving the formula for Dyck Words of length p+q, that is, p left parens and q right parens. The answer of course is $\binom{p+q}{q} - ...

**4**

votes

**0**answers

220 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:
$$
...

**14**

votes

**1**answer

363 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 ...

**5**

votes

**2**answers

813 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\}$, ...

**2**

votes

**1**answer

460 views

### Combinatorial Identities : Possible Simplification?

Hi everybody,
This is my first question so I hope I will correctly be following the rules!
I am looking for a simplification of the expression
$$
m! \sum_{k=0}^n \binom{n}{k} \binom{\alpha k}{m} ...

**3**

votes

**0**answers

176 views

### closure properties of q-differential equations

I am interested in q-differential equations of the form
$p(f(z), f(qz),\dots,f(q^kz))=0$
where $p$ is a polynomial and $k$ an nonnegative integer. I wonder about the closure properties of the class ...

**0**

votes

**2**answers

517 views

### Determining a generating function (of a restricted form)

Inspired by a recent problem for linear recurrence relations I have the following question (which may be too much to hope for). The Catalan numbers (just to give a specific example) have generating ...

**13**

votes

**1**answer

528 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 ...

**8**

votes

**3**answers

563 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} ...

**20**

votes

**2**answers

840 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 ...

**9**

votes

**5**answers

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 ...

**5**

votes

**0**answers

261 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 ...

**8**

votes

**5**answers

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

**2**answers

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 ...

**9**

votes

**3**answers

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 ...

**1**

vote

**1**answer

644 views

### Infinite graphs as functional operators

Original Question
Consider an infinite tree of constant degree $k$. For such a tree we can consider the total number of nodes at depth $n$, $g(f)$, and the total number of paths from the root, ...

**6**

votes

**1**answer

406 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 ...

**41**

votes

**7**answers

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 ...

**17**

votes

**3**answers

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

**4**answers

965 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 ...

**3**

votes

**2**answers

988 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 ...

**4**

votes

**3**answers

986 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 ...