0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/Enumerative_combinatorics. Voting to close. $\endgroup$
    – Igor Rivin
    Commented May 8, 2012 at 20:18
  • $\begingroup$ 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. $\endgroup$
    – Alexander Woo
    Commented May 8, 2012 at 20:21
  • $\begingroup$ 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. $\endgroup$
    – Patricia Hersh
    Commented May 8, 2012 at 20:23

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Also, I hesitate to make a blanket statement, but, generating functions are usually regarded as an excellent form for an enumerative result. $\endgroup$
    – Hugh Denoncourt
    Commented May 8, 2012 at 21:07
  • $\begingroup$ 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. $\endgroup$
    – Patricia Hersh
    Commented May 8, 2012 at 22:49
  • $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Commented May 8, 2012 at 23:25
  • 1
    $\begingroup$ 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}$. $\endgroup$
    – Patricia Hersh
    Commented May 9, 2012 at 0:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Patricia Hersh
    Commented May 9, 2012 at 12:27

Not the answer you're looking for? Browse other questions tagged .