The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
1answer
179 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
488 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
182 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
325 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
83 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
117 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
101 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
606 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
199 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
465 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
352 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
97 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} - ...
2
votes
0answers
203 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
501 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
458 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
348 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
295 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
802 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
369 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
264 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
715 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
774 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} = ...
1
vote
0answers
201 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 ...
0
votes
2answers
260 views

Enumeration Result [closed]

Hi I have a very soft question: What exactly is the definition of an enumeration result? Let say I want to enumerate some combinatorial structure and I came up with an equation for a generating ...
3
votes
1answer
450 views

Generating function for Dyck Words

Hello, I'm trying to reinvent the wheel here by deriving the formula for Dyck Words of length p+q, that is, p left parens and q right parens. The answer of course is $\binom{p+q}{q} - ...
3
votes
1answer
263 views

The relationship between Stirling number of the second kind and the polylogarithm

It is shown here on Mathworld's page on Stirling number of the second kind that $$ \sum_{k=1}^n S(n,k) (k-1)! z^k = (-1)^n \text{Li}_{1-n}(1+\frac{1}{z}) $$ where $S(n,k)$ is Stirling number of the ...
20
votes
1answer
791 views

A strange sum over bipartite graphs

While mucking around with some generating functions related to enumeration of regular bipartite graphs, I stumbled across the following cutie. I wonder if anyone has seen it before, and/or if anyone ...
4
votes
0answers
178 views

probabilistic terminology for polynomials with positive coefficients

Given a polynomial $P(x) = p_0 + p_1 x + p_2 x^2 + ... + p_n x^n$ with non-negative coefficients, is there a standard name for (the function of $p_1,...,p_n$ equal to) the variance of an ...
4
votes
0answers
251 views

Generating function related to 2-residues of partitions

Question Express the following power series in two commuting variables $x,y$ as an infinite product, or a short sum of infinite products: $$ ...
17
votes
1answer
433 views

What is the Generating Function for Skew Young Diagrams?

The Problem This strikes me as a very natural problem which should have been asked (and solved?) already. For each positive integer k, find a nice expression for the following generating function in ...
1
vote
1answer
327 views

Limit of an infinite series, related to (generalised Newton's) binomial expansion

How to calculate the infinite sum of the following series, related to binomial expansion for rational number, $r$: ...
2
votes
1answer
279 views

Difference equation $A(n,x)=p(x)A(n-1,x-1)+q(x)A(n-1,x)$

I asked this question on MSE, but didn't get enough information. If it is a violation of some norms, let me know, I'll delete it. I'm having problem solving this difference equation. Initially I ...
-3
votes
2answers
666 views

An interesting, simple, sequence - surprised to find little material. [closed]

I've been considering this sequence: $$1,2,3,6,12,24,48,96,192,...$$ I've generated the sequence from the rule $$V_n=\sum_{0\leq i \lt n} V_i$$ $$V_0=1; V_1=2V_0=V_0+V_0$$ What interests me most, ...
2
votes
1answer
211 views

A sequence of generating functions

I came on this sequence of generating functions on trying to count lambda terms (in lambda calculus) $T^{\langle m+1\rangle} = \frac{T^{\langle m \rangle}(z)}{z} - (T^{\langle m\rangle}(z))^2$ with ...
6
votes
2answers
729 views

Closed form or/and asymptotics of a hypergeometric sum

Dear mathematicians, I am a computer scientist wandering in the deep sea of combinatorics and asymptotics to pursue a recent interest in average case analysis of algorithms. In doing so, I designed ...
5
votes
2answers
976 views

What are the best known bounds on the number of partitions of $n$ into exactly $k$ distinct parts?

For example, if $n = 10$ and $k = 3$, then the legal partitions are $$10 = 7 + 2 + 1 = 6 + 3 + 1 = 5 + 4 + 1 = 5 + 3 + 2$$ so the answer is $4$. By choosing $k$ random elements of $\{1,\ldots,2n/k\}$, ...
2
votes
1answer
472 views

Combinatorial Identities : Possible Simplification?

Hi everybody, This is my first question so I hope I will correctly be following the rules! I am looking for a simplification of the expression $$ m! \sum_{k=0}^n \binom{n}{k} \binom{\alpha k}{m} ...
3
votes
0answers
181 views

closure properties of q-differential equations

I am interested in q-differential equations of the form $p(f(z), f(qz),\dots,f(q^kz))=0$ where $p$ is a polynomial and $k$ an nonnegative integer. I wonder about the closure properties of the class ...
0
votes
2answers
538 views

Determining a generating function (of a restricted form)

Inspired by a recent problem for linear recurrence relations I have the following question (which may be too much to hope for). The Catalan numbers (just to give a specific example) have generating ...
4
votes
2answers
390 views

Adem-Wu relations from Bullett-Macdonald identities

Question. Let $p$ be a prime. Let $q$ be a power of $p$. Let $P^0$, $P^1$, $P^2$, ... be elements of some associative $\mathbb F_q$-algebra $A$. (Here, $P^i$ does not mean $P$ to the $i$-th power; ...
13
votes
1answer
545 views

Which sets of lattice points have rational generating functions?

Let $P$ be a subset of $\mathbb N^d$ (or of some normal pointed affine semigroup), and suppose that $f:=\sum_{p\in P}\ t^p\in\mathbb Z[[t_1,\ldots,t_d]]$ is a rational function. What can be said ...
9
votes
3answers
581 views

Identifying the generating function $ G(a,z) = \sum_{n=0}^{\infty} a^n z^{(n+1)(n+2)/2}. $

I have computed a generating function for a problem involving a particular series, and would like to know if anyone has any references or a categorisation for it? It's $$ G(a,z) = \sum_{n=0}^{\infty} ...
0
votes
0answers
643 views

Any tips on finding generating functions from recurrence relations involving minimization and maximization?

Any general tips on or examples of finding interesting generating functions from recurrence relations involving minimization and maximization? I'd imagine the case with one term of a minimization or ...
39
votes
2answers
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, ...
20
votes
2answers
882 views

Partitions to different parts not exceeding $n$

Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
9
votes
5answers
1k views

Coin flipping and a recurrence relation

How can one solve the following recurrence relation? $f(n) = 1 + \frac{1}{2^n} \sum_{k = 0}^n {{n}\choose{k}} f(k)$ $f(0) = 0$ As it happens, I can show $f(n) = \Theta(\log n)$ through other means ...
42
votes
10answers
6k views

The functional equation $f(f(x))=x+f(x)^2$

I'd like to gather information and references on the following functional equation for power series $$f(f(x))=x+f(x)^2,$$$$f(x)=\sum_{k=1}^\infty c_k x^k$$ (so $c_0=0$ is imposed). First things that ...
5
votes
0answers
267 views

When does a triangle of numbers have a zero row sum?

Suppose we have a triangle of numbers defined by the recurrence relation $$\left| n \atop k \right| = f(n,k) \left| n-1 \atop k \right| +g(n,k) \left| n-1 \atop k-1 \right| + [n=k=0],$$ for some ...
1
vote
0answers
302 views

Transfinite Sums Related to a Sequence

Hello, Given a sequence $S$ indexed by the finite ordinals, a limit ordinal $\alpha$, and $k \in \mathbb{N}$, define $S_{\alpha+k}$(the extension of $S$ to $\alpha+k$) to be the sum over the products ...
9
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 ...