The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
2answers
251 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 ...
2
votes
1answer
381 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
246 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
727 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
170 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
220 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: $$ ...
14
votes
1answer
363 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
295 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
264 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
643 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
203 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
679 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
813 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
460 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
176 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
517 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
359 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
528 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 ...
8
votes
3answers
563 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
607 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 ...
28
votes
1answer
3k 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
840 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 ...
40
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
261 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
293 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 ...
8
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
644 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, ...
6
votes
1answer
406 views

How to extract the diagonal from a bivariate generating function

Let $ F(s,t)= \sum_{i,j} f(i,j) s^i t^j$, which is a bivariate generating funcion of the number $f(i,j)$ for some enumeration problem. Sometimes we know about $F(s,t)$, but what we really need is the ...
1
vote
1answer
560 views

Asymptotics of Hermite and hypergeometric function

I am looking for the asymptotics of the following integral $\int_{\mathbb{R}} H_m^2(x) {\rm e}^{-2 \alpha^2 x^2} {\rm d} x = 2^{m-1/2} \alpha^{-2m -1} (1-2\alpha^2)^m \ \Gamma(m+1/2) ~ ...
2
votes
1answer
2k views

Solving partial difference equation

I am trying to solve the following partial difference equation: $$A_k^{n+1}=(k+1)A_{k+1}^n+(n+2-k)A_{k-1}^n $$ with initial condition: $$\begin{cases} A_0^0&=1\\ A_1^0&=1 \end{cases}$$ I ...
2
votes
0answers
218 views

Algebraic Dirichlet series and beyond

I wonder what the "right" notion of "algebraic Dirichlet series" might be. Here I'm thinking of formal Dirichlet series $D(s)=\sum_{n\geq 1} a_n/n^s$, say with $a_n$ being rational numbers. I'm ...
41
votes
7answers
6k 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 ...
11
votes
2answers
749 views

Positivity of sequences via generating series

There are different ways of showing that a given sequence $a_0,a_1,a_2,\dots$ of integers, say, is nonnegative. For example, one can show that $a_n$ count something, or express $a_n$ as a (multiple) ...
9
votes
1answer
1k views

Finding recurrence relation for a sequence of polynomials

The sequence A059710 starts 1,0,1,1,4,10,35,... This satisfies the polynomial recurrence relation $$ (n+5)(n+6)a(n)=2(n-1)(2n+5)a(n-1)+(n-1)(19n+18)a(n-2)+14(n-1)(n-2)a(n-3) $$ I have a $q$-analogue ...
17
votes
3answers
2k views

Need help proving that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$

Hello. I have been trying very hard to show that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$ and could not quite get anywhere. This inequality has been verified by computer ...
15
votes
4answers
963 views

Are the q-Catalan numbers q-holonomic?

The generating function $f(z)$ of the Catalan numbers which is characterized by $f(z)=1+zf(z)^2$ is D-finite, or holonomic, i.e. it satisfies a linear differential equation with polynomial ...
6
votes
3answers
790 views

What information do the roots of the generating function of the nontrivial zeroes of the Riemann zeta function encode.

Let $a_{m}$ be the imaginary part of the nontrivial roots of the Riemann zeta function $\zeta(s)$. Suppose we have their generating function $u(x)=\sum_{m=1}^{\infty} ...
5
votes
1answer
707 views

beyond differentially algebraic power series

In a recent question, we learned about the existence of functions that do not satisfy any algebraic differential equation. One nice property of such equations is that there is a good way to ...
12
votes
6answers
787 views

An example of a series that is not differentially algebraic?

Motivated by this question, I remembered a question I was curious about sometime which I am sure has some easy and nice example for it as well, which I just can't think of for some reason. I want an ...
6
votes
1answer
934 views

Solving recurrence equation with indexes from negative infinity to positive infinity

In many cases, the recurrence equations that people are solving involves index of only non-negative values. Here I have a recurrence equation which arises from transport of light in an infinite 1D ...
13
votes
1answer
829 views

How many pairs (M, N) of sets of size n have M + N = {0, 1, …, n^2-1}?

How many pairs (M, N) of sets of size n have M + N = {0, 1, ..., n^2-1}? Manfred Schroeder, in Number Theory in Science and Communication, 4th edition, asks (p. 27): find all pairs of sets $(M,N)$, ...
3
votes
2answers
988 views

How to compute the rook polynomial of a Ferrers board?

Given a Ferrers board of shape $(b_1,\ldots,b_m)$, we define $r_k$ as number of ways to place $k$ non-attacking rooks (as in Chess). In section 2.4 of Stanley's Enumerative Combinatorics (vol. 1) it's ...
-1
votes
2answers
524 views

Where do I turn for help with generating functions?

Please forgive me if this is inappropriate for MathOverflow. I've been working/playing with generating functions for a little while and may have stumbled upon a new technique or methodology. The ...
3
votes
2answers
427 views

Euler characteristics and operator indices as exponents for Laurent polynomials

This question is rather vague. Are there any natural situations which involve Laurent polynomials of the form $$\sum q^{a_i}\in\mathbb{Z}[q,q^{-1}]$$ where the $a_i$'s are either Euler characteristics ...
9
votes
2answers
820 views

Can you find linear recurrence relation for dimensions of invariant tensors?

Let $V$ be a finite dimensional highest weight representation of a (semi)-simple Lie algebra. For each $n\ge 0$ take $a_n$ to be the dimension of the space of invariant tensors in $\otimes^n V$. In ...
2
votes
0answers
755 views

Which Hadamard Products of Generating Functions Are Known?

The Hadamard product, Schur product, or entrywise product of two generating functions is computed as follows: The Hadamard Product, H(x), given two generating functions f(x) and g(x) where $$ f(x) = ...
8
votes
2answers
697 views

What classes am I missing in the Picard lattice of a Kummer K3 surface?

Constructing the Kummer K3 of an Abelian surface $A$, we have an obvious 22-dimensional collection of classes in $H^2(K3, \mathbb{Z})$ given by the 16 (-2)-curves (which by construction do not ...