The generating-functions tag has no usage guidance.

**3**

votes

**0**answers

96 views

### Involutions on $[0,1]$ given by power series (related to probability generating functions)

Let $A$ be a function from $[0,1]$ to $[0,1]$. $A$ is an involution if $A(A(x))=x$ for all $x\in[0,1]$.
Which involutions $A$ exist such that $A(x)=\sum_{k=0}^\infty a_k x^k$ with $a_0=1$ and ...

**0**

votes

**1**answer

104 views

### The number of ways of writing a natural number as the sum of distinct elements from a finite set [on hold]

Given a finite set of natural numbers $A$, is there a generating function for the number of ways of writing a given natural number $n$ as a sum of $s$ distinct elements from $A$?

**2**

votes

**1**answer

596 views

### Probability generating function zero implies random variable is infinite

Let $V$ be a random variable supported on the nonnegative integers (including $\infty$) and $f(x) = \mathbf E x^V$ be the probability generating function. In our model $V$ is the number of visits to ...

**1**

vote

**1**answer

52 views

### Restricted partitions with square terms only

Let $P(N,M,n)$ be the number of partitions of $n$ such that each term is $\le N$ and there are at most $M$ terms. So we know the generating function for $P(N,M,n)$ is $ \frac{(q)_{N+M}}{(q)_M ...

**2**

votes

**1**answer

65 views

### Generating function of alternating even terms in the Vandermonde Convolution

I have
\begin{equation}
G(x) = \sum_{i = 0}^{\infty} \sum_{r = 0}^{\infty} (-1)^i \binom{k}{2i} \binom{n-k}{r} x^{2i} x^{r} = \frac{1}{2} \left( (1 + x{\iota})^{k} + (1 - x \iota)^{k} \right)(1 + ...

**2**

votes

**1**answer

346 views

### A particularly “natural” algebraic structure with three commutative, pairwise-distributive operations

EDIT: As mentioned in my answer below, I was mistaken in thinking Dirichlet convolution distributes over ordinary convolution. I'm leaving this question here for reference.
I keep stumbling on the ...

**2**

votes

**1**answer

77 views

### Any interesting properties of the matrix $M:=(m_{ij})$ with $m_{ij}=min(i,j)$? [closed]

Do you know any interesting properties on the matrix $M(n):=(m_{ij})$ of size $n \times n,$ where $m_{ij}= \text{min}(i,j)$ ? The matrix $M$ enumerates certain combinatorial objects.

**5**

votes

**1**answer

96 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)$ ...

**0**

votes

**1**answer

43 views

### Solving the difference equation $h(\vec x)\cdot A(\vec x)=\sum_{i=1}^m A(\vec x - \vec e_i)$

I am trying to solve the following difference equation:
$$h(x_1,x_2,x_3,x_4) \cdot A(x_1,x_2,x_3,x_4)=A(x_1-1,x_2,x_3,x_4)+A(x_1,x_2-1,x_3,x_4)+A(x_1,x_2,x_3-1,x_4)+A(x_1,x_2,x_3,x_4-1)$$
with ...

**1**

vote

**2**answers

138 views

### How do powers affect asymptotics in generating functions?

Let $a_n$ be a sequence of non-negative real numbers, and $A(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$ its exponential generating function. Also, suppose $B(x) = \sum_{n=0}^{\infty} b_n ...

**12**

votes

**2**answers

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

**9**

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

**0**answers

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

**3**

votes

**0**answers

42 views

### Using Mellin transform for a certain function

In short, I want to use the Mellin transform to obtain the asymptotic behavior of the sequence $D_n = \frac{ [z^n] D(z)} {C_n}$ where
$$
D(z) = \frac 1{2z}\sum_{p \ge 1}C_p \left( ...

**48**

votes

**7**answers

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

**5**

votes

**1**answer

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

**11**

votes

**1**answer

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

**4**

votes

**1**answer

157 views

### Raising coefficients of a power series to some power

Suppose you are given a power series $P=\sum_{i=0}^\infty{a_nt^n}$. I am primarily concerned with those power series coming from rational functions of the form
$$ ...

**1**

vote

**1**answer

58 views

### Generating function for products of laguerre polynomials?

In a quantum physics context, I would like to evaluate $S=\sum_{n=0}^\infty z^n\cos(\pi L_n(x))$ for $z<1$. I found generating functions for squares of Laguerre polynomials but not for any higher ...

**2**

votes

**2**answers

165 views

### How to calculate one Cauchy type determinant

As we know, a Cauchy determinant of size n admits the following explicit formula:
$$\det \left(\frac{1}{x _i+y _j}\right) _{1\le i,j \le n}=\frac{\prod _{1\le i < j\le n} (x _j-x _i)(y _j-y ...

**0**

votes

**0**answers

143 views

### Generating function for reciprocals of Stirling numbers?

Is there an (ordinary or exponential) generating function for the reciprocals $\frac{1}{s(n,k)}$ of the Stirling numbers of the first kind?
Also, is there some general way to find generating ...

**0**

votes

**3**answers

152 views

### Hypergeometric sum specific value

How to show?
$${}_2F_1(1,1;\frac{1}{2}, \frac{1}{2}) = 2 + \frac{\pi}{2} $$
It numerically is very close, came up when evaluating:
$$ \frac{1}{1} + \frac{1 \times 2}{1 \times 3} + \frac{1 \times 2 ...

**3**

votes

**0**answers

233 views

### Solving a doubly exponential generating function

I am analyzing the average time complexity of some algorithm on some probabilistic model, and I've come to a doubly exponential sequence for which I cannot find corresponding generating function. I ...

**1**

vote

**1**answer

140 views

### Proof of closed walk generating function identity

In 'Spectral Conditions for the Reconstructibility of a Graph' Godsil and McKay give a short proof of an identity (Lemma 2.1) that relates the generating function for the number of closed walks ...

**8**

votes

**1**answer

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

**39**

votes

**2**answers

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

**0**

votes

**0**answers

102 views

### Help solving a recurrence relation

For solving a related probability problem, I need to solve the following recurrence relation:-
$q(r,b,L)=\frac{b}{r+b}q(r,b-1,L)+\sum_{k=1}^{L}\frac{r}{r+b}\times\cdots \times ...

**1**

vote

**1**answer

167 views

### Matrix Generator for M/M/1 Queue Waiting Time Distribution

I "believe" that generator, $\bf W$, of the waiting time distribution for the M/M/1 queue is given by the following (I'm not sure if this is even correct):
${\bf W} =\left( \begin{array}{ccccc}
0 ...

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

**1**

vote

**1**answer

193 views

### Name for series $\sum f_n x^n / (n! (n+k)!)$

Let $(f_n)_{n\ge0}$ be a real sequence. Then $\sum f_n {x^n \over n!}$ is called the exponential generating function of $(f_n)$.
Let $k\ge0$ be a nonnegative integer. If we add another factorial ...

**4**

votes

**2**answers

333 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

**0**answers

93 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) ( ...

**0**

votes

**0**answers

50 views

### Coupled recurrence relations for generating functions, involving squared arguments

I'm trying to find a solution for the following system of three equations in terms of three bivariate generating functions.
$G(x,y)=b(x,y) \cdot \left( G(x,y^2) + I(x,y^2) \right) +y ;$
$H(x,y)=x ...

**19**

votes

**1**answer

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

**7**

votes

**2**answers

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

**5**

votes

**2**answers

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

**1**

vote

**0**answers

138 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

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

**42**

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

**3**

votes

**1**answer

260 views

### Is there a nice way to write the generating function obtained by taking the quadratic coefficients of another one?

Suppose that you have a generating function
$$
f(q) = \sum_{k=0}^\infty a_k q^k
$$
It's not too hard to obtain the generating function
$$
f_{n,m}(q) = \sum_{k=0}^\infty a_{nk + m}q^k
$$
by taking a ...

**2**

votes

**2**answers

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

**5**

votes

**1**answer

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

**1**

vote

**1**answer

68 views

### Approaches to implicitly defining generating function

First,every language in Chomsky hierarchy(or c.e.language) corresponds to a generating function,the set of the functions is GF,now,a question : is every generating function with integral coefficient ...

**0**

votes

**0**answers

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

**10**

votes

**1**answer

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

**1**

vote

**0**answers

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

**2**

votes

**1**answer

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

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

**4**

votes

**0**answers

140 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

**0**answers

119 views

### Is there inverse FFT algorithm for Fourier transform of a integer-valued random variable?

In many applications, it is possible to derive an explicit expression for the
Fourier transform of a random variable $X$
$$\varphi (\theta ) = \sum\limits_{n = 0}^\infty {{p_n}} {e^{in\theta }}$$
...