0

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 function for this enumeration, but not with a closed form for its coefficients.

Can I call this an enumeration result?

flag
1 
 See en.wikipedia.org/wiki/Enumerative_combinatorics. Voting to close. – Igor Rivin May 8 2012 at 20:18
Of course it depends on context. Like almost everything in mathematics, once there is a proof, it's all a matter of taste. But being a matter of taste does not mean it is arbitrary. See the first subchapter of Stanley's Enumerative Combinatorics for his comments. – Alexander Woo May 8 2012 at 20:21

closed as not a real question by Igor Rivin, Benjamin Steinberg, Qiaochu Yuan, Anthony Quas, Igor Pak May 9 2012 at 16:40

2 Answers

2

This should just be a comment, but I don't have enough points yet to do that.

I've heard people speak of ``enumeration'' as either giving a counting formula or else an explicit list of elements. So I'm not sure I'd call this an enumeration. But it's possible other people have different conventions, and in any case generating function equations are often interesting combinatorial results. You should probably listen though to the people on this site who have actually written books on enumerative combinatorics.

link|flag
5

The article ``What is an answer?'' by Herbert Wilf focuses on this question and is good reading. It is from The American Mathematical Monthly, Volume 89, No. 5 (May, 1982), pages 289-292.

link|flag
Also, I hesitate to make a blanket statement, but, generating functions are usually regarded as an excellent form for an enumerative result. – Hugh Denoncourt May 8 2012 at 21:07
I may have misunderstood the posting -- I was thinking the poster was saying that he or she didn't have a closed form for the generating function, but rather had a recurrence it satisfies. It seems quite safe to me to call a closed form for a generating function an enumeration. – Patricia Hersh May 8 2012 at 22:49
It's not clear at all what OP means by "an equation for a generating function", but I don't see how a function (as opposed to a sequence) can satisfy a recurrence. – Gerry Myerson May 8 2012 at 23:25
1 
 Recurrence wasn't really the right word to use. I meant an algebraic equation or differential equation or something like that. For instance, the generating function for Catalan numbers satisfies a degree two algebraic equation that reflects the relationship $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$. – Patricia Hersh May 9 2012 at 0:42
1 
 Agreed. For anyone here who hasn't seen this stuff, an excellent reference on generating functions satisfying algebraic and differential equations is Enumerative Combinatorics, Volume II, chapters 5 and 6, by Richard Stanley. – Patricia Hersh May 9 2012 at 12:27
show 1 more comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.