The generating-functions tag has no wiki summary.

**2**

votes

**2**answers

757 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} = ...

**1**

vote

**0**answers

186 views

### An equation about generating functions and subfactorial

As I promised, I clone the problem from Math.SE to here, in order to find a solution.
Suppose $G_n(w)$ is a formal power series (really a probability generating function, see the following ...

**0**

votes

**2**answers

251 views

### Enumeration Result [closed]

Hi
I have a very soft question:
What exactly is the definition of an enumeration result?
Let say I want to enumerate some combinatorial structure and I came up with an equation for a generating ...

**3**

votes

**1**answer

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

**3**

votes

**1**answer

246 views

### The relationship between Stirling number of the second kind and the polylogarithm

It is shown here on Mathworld's page on Stirling number of the second kind that
$$
\sum_{k=1}^n S(n,k) (k-1)! z^k = (-1)^n \text{Li}_{1-n}(1+\frac{1}{z})
$$
where $S(n,k)$ is Stirling number of the ...

**20**

votes

**1**answer

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

**4**

votes

**0**answers

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

**0**answers

224 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

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

**1**

vote

**1**answer

302 views

### Limit of an infinite series, related to (generalised Newton's) binomial expansion

How to calculate the infinite sum of the following series, related to binomial expansion for rational number, $r$:
...

**2**

votes

**1**answer

267 views

### Difference equation $A(n,x)=p(x)A(n-1,x-1)+q(x)A(n-1,x)$

I asked this question on MSE, but didn't get enough information. If it is a violation of some norms, let me know, I'll delete it.
I'm having problem solving this difference equation. Initially I ...

**-3**

votes

**2**answers

646 views

### An interesting, simple, sequence - surprised to find little material. [closed]

I've been considering this sequence:
$$1,2,3,6,12,24,48,96,192,...$$
I've generated the sequence from the rule
$$V_n=\sum_{0\leq i \lt n} V_i$$
$$V_0=1; V_1=2V_0=V_0+V_0$$
What interests me most, ...

**2**

votes

**1**answer

204 views

### A sequence of generating functions

I came on this sequence of generating functions on trying to count lambda terms (in lambda calculus)
$T^{\langle m+1\rangle} = \frac{T^{\langle m \rangle}(z)}{z} - (T^{\langle m\rangle}(z))^2$
with
...

**6**

votes

**2**answers

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

**5**

votes

**2**answers

823 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

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

**4**

votes

**2**answers

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

**13**

votes

**1**answer

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

**0**

votes

**0**answers

609 views

### Any tips on finding generating functions from recurrence relations involving minimization and maximization?

Any general tips on or examples of finding interesting generating functions from recurrence relations involving minimization and maximization?
I'd imagine the case with one term of a minimization or ...

**28**

votes

**1**answer

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

**2**answers

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

**40**

votes

**10**answers

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

**5**

votes

**0**answers

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

**1**

vote

**0**answers

295 views

### Transfinite Sums Related to a Sequence

Hello,
Given a sequence $S$ indexed by the finite ordinals, a limit ordinal $\alpha$, and $k \in \mathbb{N}$, define $S_{\alpha+k}$(the extension of $S$ to $\alpha+k$) to be the sum over the products ...

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

645 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

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

**1**

vote

**1**answer

562 views

### Asymptotics of Hermite and hypergeometric function

I am looking for the asymptotics of the following integral
$\int_{\mathbb{R}} H_m^2(x) {\rm e}^{-2 \alpha^2 x^2} {\rm d} x = 2^{m-1/2} \alpha^{-2m -1} (1-2\alpha^2)^m \ \Gamma(m+1/2) ~ ...

**2**

votes

**1**answer

2k views

### Solving partial difference equation

I am trying to solve the following partial difference equation:
$$A_k^{n+1}=(k+1)A_{k+1}^n+(n+2-k)A_{k-1}^n $$
with initial condition:
$$\begin{cases} A_0^0&=1\\ A_1^0&=1 \end{cases}$$
I ...

**2**

votes

**0**answers

219 views

### Algebraic Dirichlet series and beyond

I wonder what the "right" notion of "algebraic Dirichlet series" might be. Here I'm thinking of formal Dirichlet series $D(s)=\sum_{n\geq 1} a_n/n^s$, say with $a_n$ being rational numbers.
I'm ...

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

**11**

votes

**2**answers

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

**9**

votes

**1**answer

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

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

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

**6**

votes

**3**answers

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

**5**

votes

**1**answer

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

**12**

votes

**6**answers

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

**6**

votes

**1**answer

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

**13**

votes

**1**answer

832 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)$, ...

**3**

votes

**2**answers

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

**-1**

votes

**2**answers

524 views

### Where do I turn for help with generating functions?

Please forgive me if this is inappropriate for MathOverflow. I've been working/playing with generating functions for a little while and may have stumbled upon a new technique or methodology.
The ...

**3**

votes

**2**answers

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

**9**

votes

**2**answers

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