The tag has no usage guidance.

learn more… | top users | synonyms

8
votes
0answers
106 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) ...
2
votes
0answers
59 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 ...
2
votes
1answer
143 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 + ...
1
vote
3answers
178 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
0answers
49 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
2answers
366 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 ...
4
votes
1answer
98 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 ...
14
votes
2answers
219 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 ...
16
votes
2answers
600 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 ...
8
votes
2answers
231 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
1answer
78 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 ...
4
votes
1answer
268 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
0answers
110 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
2answers
350 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
3answers
466 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
1answer
189 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
0answers
175 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
1answer
280 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 ...
44
votes
3answers
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
1answer
420 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 ...
7
votes
1answer
433 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 ...
2
votes
1answer
626 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
0answers
117 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
3answers
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
2answers
313 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 ...
4
votes
0answers
65 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) = ...
3
votes
0answers
122 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
1answer
64 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
1answer
376 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
1answer
119 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
1answer
113 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)$ ...
1
vote
1answer
147 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
2answers
359 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
5answers
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
0answers
104 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
0answers
55 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( ...
50
votes
7answers
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 ...
5
votes
1answer
363 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
1answer
375 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
1answer
175 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
1answer
63 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
2answers
217 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
0answers
156 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 ...
3
votes
0answers
262 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
1answer
191 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
1answer
223 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 ...
0
votes
0answers
115 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
1answer
214 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 ...
19
votes
4answers
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
1answer
202 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 ...