The tag has no wiki summary.

learn more… | top users | synonyms

6
votes
1answer
324 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
116 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
600 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
349 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
96 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
201 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 ...
8
votes
0answers
482 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
457 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
347 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
293 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
794 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
364 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
698 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
773 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
259 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
444 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
788 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
250 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
428 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
325 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
662 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
725 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
962 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
180 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
535 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
388 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
544 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
579 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
641 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
4k 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
879 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 ...
8
votes
2answers
1k views

Expressions involving Eulerian numbers of the second kind: trying to show $\sum_{m=0}^{n} (-1)^m(m)m!(2n-m-2)!\left\langle\left\langle n\atop m\right\rangle\right\rangle\neq0$ for even $n$.

Considering the success of a previous question involving Eulerian numbers, I thought I might throw this question into the mix. It comes from some localization computations in GW theory, but in this ...
9
votes
3answers
1k views

Solving a general two-term combinatorial recurrence relation

What is known about explicit (not necessarily closed-form) solutions to the recurrence $$R^n_k= (\alpha n) R^{n-1}_k + (\alpha' n + \beta' k) R^{n-1} _{k-1},$$ with initial condition $R_0^0 = 1$ and ...
1
vote
1answer
659 views

Infinite graphs as functional operators

Original Question Consider an infinite tree of constant degree $k$. For such a tree we can consider the total number of nodes at depth $n$, $g(f)$, and the total number of paths from the root, ...