The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
1answer
202 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
669 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
776 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
454 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
174 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
503 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
349 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
524 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
545 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
604 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
2k 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
829 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 ...
35
votes
10answers
5k 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
259 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
291 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
996 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
638 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
396 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
547 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
217 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 ...
39
votes
7answers
5k 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
744 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
949 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
778 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
703 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
781 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
906 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
809 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
976 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
520 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
426 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
812 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
733 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) = ...
7
votes
2answers
679 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 ...
2
votes
5answers
552 views

Generating-functions: is there a relationship between a generating function and the corresponding squared generating function

Let's say we have a sequence $T(n)$ with the corresponding generating function $$A(t) = \sum_{n = 0}^\infty T(n) t^n$$ Is there some relationship between the two functions $A(t)$ and $A(t^2)$? And ...
4
votes
3answers
976 views

Asymptotics of a hypergeometric series/Taylor series coefficient.

I was planning on figuring this problem out for myself, but I also wanted to try out mathoverflow. Here goes: I wanted to know the asymptotics of the sum of the absolute values of the Fourier-Walsh ...