The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
18 views

Find the probability generating function of a GW process [migrated]

Consider a Galton-Watson process with offspring distribution $Possion(1)$. That is, $\textbf{p}(k) = \frac{e^{-1}}{k!}$. Given this information, and that $P(z) = ...
7
votes
2answers
244 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 ...
1
vote
0answers
103 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
4answers
776 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 ...
3
votes
1answer
243 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 ...
4
votes
1answer
225 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
1answer
58 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 ...
1
vote
1answer
58 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
0answers
89 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
1answer
221 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
0answers
118 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 ...
0
votes
0answers
93 views

Are there generating functions of rational or integral solutions of Diophantine equation that

As we know,there are generating functions for c.e.languages which are some retricted rational or algebraic or transcendental functions dependent on the class of languages like regular ...
3
votes
0answers
112 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
0answers
101 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 }}$$ ...
0
votes
1answer
221 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 ...
0
votes
2answers
89 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 ...
1
vote
1answer
237 views

An infinite product: combinatorial interpretation

It is an undergraduate exercise to show that the generating function for the sequence of unrestricted integer partitions $p(n)$ is the celebrated infinite product ...
2
votes
2answers
819 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 ...
5
votes
1answer
157 views

The number of partitions between two fixed partitions

Given two partitions M and N, with $M_i \leq N_i$ for all $1\leq i\leq \max\{l(M),l(N)\}$. Is there a formula for the generating function: $$\sum_{\lambda: M_i\leq \lambda_i\leq N_i} ...
-1
votes
1answer
242 views

Does anyone recognize this generating function [closed]

$a_1=1, a_2=1, a_3=3, a_4=15, a_5=105$ Reccurence formula is $a_{k+1}=\sum\limits_{\lambda_1+\lambda_2+\ldots+\lambda_s=k,\ \lambda_i\geq1} a_{\lambda_1}a_{\lambda_2}...a_{\lambda_s}{k \choose ...
0
votes
0answers
85 views

What are the properties of this linear operator?

Suppose $f(x)$ is a function which satisfies the following condition: $$f(x)=\sum_{k=0}^\infty G(2k)\frac{x^{2k}}{(2k)!}$$ Where the generating function $G(x)$ is a "natural" or "discrete-analytic" ...
5
votes
2answers
161 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 ...
2
votes
0answers
75 views

Lagrangean equations for the generating function of quadrangulations

Let $M(z)$ be the generating function of edge-rooted connected quadrangulations, with $z$ marking the number of edges. I derived the following Lagrangean equations for $M(z)$: $$M(z) = ...
1
vote
1answer
117 views

Truncated sums of symmetric polynomials; reference request for an algebraic derivation

EDIT: This is a case of being too wrapped up in a formulation ($e_j,p_i,$ and the like) to try something simple. It did not occur to me to pull exp to the outside in the weeks I have stared at this. ...
2
votes
2answers
304 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 ...
3
votes
0answers
187 views

Generating function for the characteristic function of prime numbers

What do we know about the generating function of $\chi(n)$ (A010051) $$ f(x) = \sum_{n=0}^\infty \chi(n)x^n = \sum_{p\text{ prime}} x^p $$ for $\chi(n)$ the characteristic function of the primes: ...
2
votes
0answers
55 views

Rank generating functions on a graded poset and a linear extension of it

Let $A$ be a possibly infinite ensemble and let $\leq$ be a partial order between elements of $A$. We denote $P_{\leq}=(A,\leq)$ the corresponding poset. Furthermore, we suppose that $P$ is graded, ...
6
votes
1answer
236 views

Does the following operation on modular forms yield something modular?

Let $f(z) = \sum_{n=0}^\infty a_nq^n$ be the fourier expansion of a (quasi-)modular form (with $q = e^{2\pi i z}$). Consider the following related functions: $$f_{m,k}(z) = \sum_{n=0}^\infty a_{mn + ...
0
votes
1answer
144 views

Given a generating function with “zeros”, can one derive the function for ONLY the “zeros”?

If I have an generating function (GF) --- ordinary or exponential --- defining a series with at least one coefficient equal to zero, is there a general method to find the "inverse GF", i.e., the GF ...
2
votes
1answer
442 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 ...
2
votes
2answers
170 views

Generating function of factorable binary words

A word $w$ on the alphabet $A := \{0, 1\}$ is factorable if \begin{equation} w = u^k \mbox{ where } u \in A^* \mbox{ and } k \geq 2. \end{equation} Let $L$ be the language of the set of ...
6
votes
1answer
294 views

Generating functions with all non-zero coefficients equal to one

Inspired by this question, I have been wondering if there are any useful generating functions with all non-zero coefficients equal to one. Obviously, the trivial generating function $\frac{1}{1-x}$ ...
1
vote
0answers
81 views

Generating series of free PROs

Let \begin{equation} G := \biguplus_{p \geq 0} \: \biguplus_{q \geq 0} G(p, q) \end{equation} be a bigraded set of generators and $\mathcal{F}(G)$ be the free PRO generated by $G$ (see [1] for a net ...
0
votes
0answers
107 views

Using extended group rings for combinatorial generating functions

In work of mine recently, I have come to investigate generalised recurrence relations. The generalisation I have in mind is where, instead of natural numbers or integers, the recurrence is over some ...
1
vote
1answer
92 views

Approximating rational generating functions

Suppose we have a initial segment $x_1,\ldots,x_N$ (for reasonably large $N$) of a sequence of natural numbers $(x_i)$. We have reason to believe the generating function $\sum_{i=0}^\infty x_iX^i$ is ...
8
votes
4answers
454 views

Partitions-Sum of divisors identity

A few years ago I first read about the marvelous Euler identity: $\sum_{n\in\mathbb{N}}p(n)z^n=\prod_{k\geq1}\frac{1}{1-z^k}$, where $p(n)$ is the number of partitions of $n$ ($p(0)=1$ by ...
0
votes
0answers
189 views

functional equation, how to solve

Suppose $x_i, y_i \in \mathbb{R}^n$, and $F,G: \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}^n$. $$F(x, y) = \frac{x\circ Ay}{x^TAy}$$ $$G(x, y) = \frac{x\circ By}{x^TBy}$$ where $A$ and $B$ are ...
9
votes
2answers
438 views

Series defined by a fixed-point functional equation

Description I my work, I met fixed-point functional equations of a very specific form. Since I am not expert in the domain of functional equations, I have not pushed the study of these very far. Here ...
3
votes
1answer
231 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 ...
0
votes
0answers
91 views

Theorem Leads for tied-down random walk

scribd.com/doc/87930409/18/Leads-for-tied-down-random-walk [Theorem 3.7, page 38] Could you explain me the last equality in the proof? I mean this: $$\frac{2[\sqrt{1 - s^2t^2} - ...
1
vote
0answers
175 views

Generalization of Lagrange inversion with “skewed” formal parameter

I am interested in obtaining an analog of the Lagrange inversion formula, starting from a generalization of the implicit equation. Ordinary Lagrange reversion, as I am familiar with it, starts with ...
7
votes
0answers
292 views

Generalization of Cauchy's identity

Let $ s_{\lambda} $ be the schur function associated to the partition $ \lambda $. Cauchy's identity (as in Macdonald) states that $$ \sum_{\lambda} s_{\lambda}(X)s_{\lambda}(Y) = ...
14
votes
2answers
416 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 ...
9
votes
1answer
340 views

Elephant populations (and Dyck words)

Hello, I'm relatively new to this forum so apologies if I have tagged my question incorrectly. I have been in contact with a wildlife biologist recently concerning counting elephant populations and ...
2
votes
2answers
262 views

Alternating sum of binomial coefficients times logarithm

Trying to find a closed form expression for the following sum, or an asymptotic expression in terms of well known functions (like the Gamma function, for instance). Let $m,n$ be positive integers ...
7
votes
1answer
734 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
2answers
313 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
2answers
242 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)} $$
17
votes
1answer
520 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
2answers
757 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} = ...