The generating-functions tag has no wiki summary.

**7**

votes

**1**answer

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

**5**

votes

**2**answers

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

**0**

votes

**2**answers

256 views

### Ramanujan Divisor Function [closed]

Help me prove
$$
\sum_{n=1}^\infty \frac{\sigma_a(n)\sigma_b(n)}{n^s} = \frac{\zeta(s) \zeta(s-a) \zeta(s-b) \zeta(s-a-b)}{\zeta(2s-a-b)} $$

**19**

votes

**1**answer

634 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

762 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

193 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

255 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

416 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

250 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

753 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

175 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

233 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

388 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

310 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

269 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

650 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

208 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

694 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

862 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

463 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

523 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

375 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

531 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

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

**0**

votes

**0**answers

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

**39**

votes

**2**answers

4k 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

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

**41**

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

264 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

298 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

652 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

420 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

571 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

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

**43**

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

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

**18**

votes

**4**answers

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

**6**

votes

**3**answers

797 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

717 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

811 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

997 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

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