The generating-functions tag has no usage guidance.

**4**

votes

**0**answers

171 views

### Enumerating a class of polynomials

How many equivalence classes of $\Bbb F_2[x,y]$ polynomials with $x$ degree $n_x$ and $y$ degree $n_y$ are there such that each $y^i$ coefficient (polynomial in $\Bbb Z[x]$) is distinct and $x^i$ ...

**21**

votes

**2**answers

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

**2**

votes

**1**answer

148 views

### Generating function for numbers divisible by some primes

Consider the first $k$ primes $p_1 = 2, p_2 = 3, \dots, p_k$. Let $A_k$ be the set of numbers that are divisible by at least one $p_i$. We can represent this set as a generating function:
$$G_k(x) = \...

**3**

votes

**1**answer

186 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 + x)^...

**3**

votes

**0**answers

42 views

### Finite realization of irrational transfer functions

In the field of digital signal processing, linear time-invariant systems play a distinguished role. These are the systems for which there exists an impulse response, a function $h:\mathbb{Z}\to\...

**11**

votes

**1**answer

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

**6**

votes

**3**answers

381 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} + a_{n,m+2})...

**55**

votes

**8**answers

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

**13**

votes

**3**answers

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

**4**

votes

**1**answer

218 views

### Eliminating a variable from a two-variable linear recurrence

In attempting to enumerate a combinatorial class of objects, I've come to a bivariate recurrence:
$$
a_{n,k} = 2a_{n,k-1} + (k+1)a_{n-1,k+1} - ka_{n-1,k} - a_{n,k-2} + a_{n-1,k-1}.
$$
Together with ...

**4**

votes

**2**answers

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

**3**

votes

**1**answer

173 views

### Solving recursion / finding generating function of a probability mass function

I am assessing the probability distribution on a running time of some algorithm that we've developed. I am looking for a family of probability mass functions $f_n$ with the following recurrence:
$$
f_{...

**11**

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

**8**

votes

**1**answer

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

**3**

votes

**0**answers

160 views

### Combination of Generating Functions

Suppose I have the following generating functions:
$$\frac{x^ke^{\left(z-\frac{1}{N}\right)x}}{N^{k-1}k!\sum_{j=0}^{N-1}w_N^{-jk}e^{\frac{w_N^jx}{N}}}=\sum_{j=0}^\infty H_{N,k,j}(z)\frac{x^j}{j!}$$
...

**3**

votes

**5**answers

664 views

### Generating-functions: is there a relationship between a generating function and the corresponding squared generating function

Let's say we have a sequence $T(n)$ with the corresponding generating function
$$A(t) = \sum_{n = 0}^\infty T(n) t^n$$
Is there some relationship between the two functions $A(t)$ and $A(t^2)$? And ...

**2**

votes

**0**answers

169 views

### Hilbert series of the weight 0 sub-algebra of the algebra of functions on GL(N)

Let $A$ be the algebra of polynomials in $N^2$ variables $x^i_j$, $i,j=1,\dots,N$. It is $\mathbb{Z}^N$ graded, with $\text{weight}(x^i_j)=e_i-e_j$. Here $(e_1,\dots,e_n)$ is the standard basis of $\...

**0**

votes

**0**answers

99 views

### Multidimensional recurrence relations

There are many methods of solving one-dimensional homogeneous linear recurrence relations, i.e. such of the form
$$ a_n = \sum_{k=1}^{m}\alpha_ka_{n-k}.$$
Most widespread use linear algebra or ...

**23**

votes

**3**answers

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

**2**

votes

**0**answers

69 views

### Inverses of probability generating functions: positivity of derivatives

Let $\mathcal{G}$ be the set of probability generating functions of random variables taking positive integer values, considered as functions on $[0,1]$.
So $G\in\mathcal{G}$ can be written $G(x)=\...

**1**

vote

**3**answers

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

**0**

votes

**0**answers

55 views

### Direct proof that a certain generating function is D-finite

Consider the set $T^{2,3}_n$ of all non-planar rooted trees with $n$ leaves labelled by $1,2,\ldots,n$ where each internal vertex can have two or three children. If we think of the binary / ternary ...

**2**

votes

**2**answers

395 views

### Closed formula for the generating function of the sequence of powers

Does anyone know of a closed formula for the function
$f_k(x)=\sum_{n=1}^{\infty}{n^k x^n}$ ? That is, the generating function of the sequence $1^k,2^k,3^k...$.
It is not hard to see that $f_k(x)=\...

**4**

votes

**1**answer

104 views

### Calculation of one constant similar to MZV

The series arose in the calculation of Mean value of a function associated with continued fractions:
$$C=\sum_{1\le b\le d<\infty}\frac{1}{b(b+d)d^2}.$$
Obviously
$C=C_1-C_2,$
where
$$C_1=\sum_{1\...

**14**

votes

**2**answers

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

**9**

votes

**2**answers

267 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}$

**0**

votes

**1**answer

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

**3**

votes

**1**answer

277 views

### Generating function for number of different tessellation checkered rectangle

Let $R_n$ be checkered rectangle sized $n \times 4, n \ge 1$.
Let $a_n$ be number of different $R_n$ tiling with rectangles sized $1 \times 3$.
$\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $...

**4**

votes

**0**answers

161 views

### Puzzling behaviour of a recursively defined sequence of functions

This question arose in connection with another problem that I described earlier in Constructing a generating function using a series with all negative and positive powers of a variable. I had certain ...

**2**

votes

**2**answers

374 views

### Is there a nice generating function proof of the following identity?

Consider the Jordan function $J_2(n)$ defined by
$$
J_2(n) = \#\{x \in (\mathbb{Z}/n)^2 \mid ord(x) = n\}
$$
(this is OEIS A007434). One can prove the following identity pretty easily:
$$
\sum_{d \mid ...

**6**

votes

**3**answers

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

**7**

votes

**1**answer

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

**5**

votes

**0**answers

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

**12**

votes

**1**answer

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

**45**

votes

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

**3**

votes

**1**answer

421 views

### p-adic poly-Bernoulli numbers

We can define p-adic Bernoulli polynomials by using q-integral on $\mathbb{Z}_p$ and Taekyun Kim's method.
But how can we define p-adic poly-Bernoulli numbers and polynomials by using integral on $\...

**2**

votes

**1**answer

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

**3**

votes

**0**answers

126 views

### Generating function of a sequence involving reciprocals of binomial coefficients

Question: Is there a closed-form expression for the following sum
$$
F(z,k,r)=\sum_{n=0}^{r} \frac{z^n}{{n+k} \choose {k}}\label{sum}\tag{1}
$$
where $z\in\mathbb{C}$, and $r$, $k$ are non-negative ...

**5**

votes

**3**answers

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

**8**

votes

**2**answers

333 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 nd-1}P_d(x)=\begin{cases}x^...

**4**

votes

**0**answers

73 views

### Is there a nice way to invert this expression?

Let us first define the Euler polynomials to be the polynomials $P_n(q)$ that satisfy
$$
\frac{qP_n(q)}{(1 - q)^{n+1}} = \Big(q\frac{d}{dq}\Big)^n\frac{q}{1 - q}.
$$
For example, $P_0(q) = P_1(q) = 1$...

**3**

votes

**0**answers

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

**1**

vote

**1**answer

67 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 (q)_{N}}$...

**3**

votes

**1**answer

388 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

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

**6**

votes

**1**answer

122 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)$ i.e....

**1**

vote

**1**answer

159 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 \frac{x^n}{...

**12**

votes

**2**answers

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

**10**

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

**9**

votes

**0**answers

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