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
    Commented Sep 16, 2015 at 13:40
  • $\begingroup$ yes - sorry it was unclear $\endgroup$
    – user2052
    Commented 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
    Commented 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
    Commented Sep 19, 2015 at 23:56

You must log in to answer this question.

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