The tag has no usage guidance.

learn more… | top users | synonyms

7
votes
2answers
369 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
162 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 & = & K_{1}\tbinom{...
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 ...
3
votes
1answer
274 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 ...
5
votes
1answer
275 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*} e_{h}(\...
1
vote
1answer
249 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
70 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
110 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} = 1,f_{...
10
votes
1answer
294 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
142 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 ...
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, ...
1
vote
0answers
132 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 }}$$ ...
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 ...
1
vote
3answers
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 \...
2
votes
1answer
287 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 $$\prod_{k=1}^{\infty}\frac{1}{1-x^k}...
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 ...
5
votes
1answer
188 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} q^{|\lambda|}$$...
-1
votes
1answer
265 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
135 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
186 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
87 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) = \psi(L(z)),~\...
1
vote
1answer
139 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
361 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
338 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: $$...
1
vote
0answers
113 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, i....
6
votes
1answer
252 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
190 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
497 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
194 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
343 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
86 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
126 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
104 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
729 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 convention)...
0
votes
0answers
208 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 ...
11
votes
2answers
515 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 ...
5
votes
1answer
370 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
105 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} - \sqrt{1-t^2}]}{t^2(...
2
votes
0answers
214 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 ...
9
votes
0answers
682 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) = \prod_{i,j}(1-...
21
votes
2answers
707 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 ...
10
votes
1answer
358 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 ...
3
votes
2answers
324 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
929 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 ...
6
votes
3answers
492 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
278 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)} $$
19
votes
1answer
791 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
802 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} = \sum_{a,...
1
vote
0answers
209 views

An equation about generating functions and subfactorial

As I promised, I clone the problem from Math.SE to here, in order to find a solution. Suppose $G_n(w)$ is a formal power series (really a probability generating function, see the following ...
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 $\...