The tag has no usage guidance.

learn more… | top users | synonyms

4
votes
2answers
237 views

Negative probabilities - what are two ordinary pgfs that correspond to the gf of a half-coin?

In Half of a Coin: Negative Probabilities, author considers pgf of a fair coin represented by random variable, $X = 1_H$: $$G_X(z) = E[z^X] = \sum_{x=0,1} z^xP(X=x) = (z^0)(1/2) + (z^1)(1/2) = \frac{...
2
votes
2answers
253 views

Convergence issues with infinite product of formal series

Question first: Show that if $s_1 < s_2 < \dots$ is an increasing sequence of positive integers and $P(x)$ is a nonzero polynomial then we cannot have $$ P(x) \equiv \prod_{j=1}^\infty (1 -...
1
vote
1answer
153 views

Solving for f given constraint involving f(x, y) and f(xy, y)

I am interested in a weighted version of the Catalan numbers. The generating function for this case, $$ f(x, y) = \sum_s \sum_n f_{s n} x^s y^n $$ (where the $y^n$ term is the weight), obeys the ...
3
votes
1answer
199 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)^...
2
votes
1answer
79 views

An inequality on partitions into distinct bounded parts

Let $P(n,m)$ denote the set of all positive integer partitions of $n$ into parts that are pairwise distinct and bounded by $m$. Let $p(n,m) = |P(n,m)|$. After some numerical experiments it appears $...
4
votes
0answers
175 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
2answers
714 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
1answer
152 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
0answers
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
1answer
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
3answers
384 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})...
56
votes
8answers
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
3answers
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
1answer
222 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
2answers
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
1answer
183 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
4answers
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
1answer
527 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
0answers
163 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
5answers
667 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
0answers
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
0answers
100 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
3answers
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
0answers
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
3answers
184 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
58 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
396 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
1answer
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
2answers
239 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
2answers
277 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
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
1answer
279 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
162 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
375 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
504 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
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
0answers
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
1answer
319 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
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
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
1answer
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
0answers
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
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
334 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
0answers
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
0answers
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
1answer
68 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
1answer
390 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
200 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
123 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....