4
$\begingroup$

Question: Is there a nice (or any) formula for the generating function $$T(x,y) = \sum_{m,n} t_{m,n} x^my^n,$$ where $t_{m,n}$ is the number of trees with $m$ vertices and $n$ endpoints?

Here only the case of unlabeled and unrooted trees is considered.

The hope is that $T(x,-1)$ will have visibly nonnegative coefficients, thereby proving (if true) that for a given number of vertices, there are never more trees with an odd number of endpoints than with an even number. (The trivial case of a single vertex is excluded).

Thank you.

Improve this question
$\endgroup$
3
  • $\begingroup$ My guess is that the coefficient of $x^my^n$ in $T(x,y)$ accounts for trees with $m$ vertices and $n$ endpoints. $\endgroup$
    – Max Alekseyev
    Sep 16, 2015 at 13:40
  • $\begingroup$ yes - sorry it was unclear $\endgroup$
    – user2052
    Sep 19, 2015 at 23:55
  • $\begingroup$ I've edited the question to clarify that. Also, I confirm your conjecture for $m\leq 50$ -- see oeis.org/A262395 $\endgroup$
    – Max Alekseyev
    Sep 22, 2015 at 4:01

1 Answer 1

Reset to default
4
$\begingroup$

A table of counts, and mention of the generating function is on OEIS at A055290.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks very much for the reference. Unfortunately, just plugging in y = -1 appears far from conclusive and so the nonnegativity above apparently remains open . $\endgroup$
    – user2052
    Sep 19, 2015 at 23:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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