A162171 Third column of A162170.

1, 3, 6, 20, 75, 336, 1708, 9792, 62325, 436480, 3334386, 27595776, 245951615, 2348666880, 23923317720, 258910994432, 2966901358185, 35886973648896, 456927138333790, 6108665873694720, 85555744482868275, 1252729007440396288, 19140289332506060676

Offset: 1

Author

Mats Granvik, Jun 27 2009

Keywords

• nonn
• easy

Links

• J. A. Palacios, A. Bhaskar, F. Disanto and N. A. Rosenberg, Enumeration of binary trees compatible with a perfect phylogeny, J. Math. Biol. 84 (2022), 54.

Crossrefs

Cf. A162170, A000111.

Programs

PARI

T(n, k) = if (k % 2, binomial(n-1, k-1) * (-1)^floor((n+k-1)/2), if (n==k, 1 , 0));
lista(nn) = {m = matrix(nn, nn, n, k, if (n>=k, T(n,k), 0)); m = m^(-1); for (n=3, nn, print1(m[n,3], ", "));} \\ Michel Marcus, Jun 17 2015

PARI

lista(nn) = { a = [1]; for(n = 2, nn, a = concat(a, sum(k = 1, j = floor(n/2), (-1)^(j+k) * binomial(n+1, 2*k) * a[2*k-1]))); print(a) } \\ Mike Tryczak, Jun 18 2015

Formula

a(n) = Sum_{k=1..floor(n/2)} (-1)^(floor(n/2)+k) * binomial(n+1, 2*k) * a(2*k-1) for n > 1. - Mike Tryczak, Jun 18 2015

a(n) = n*(n+1)/2 * A000111(n-1) (conjectured). - Mike Tryczak, Jun 17 2015

The above conjecture by Tryczak is correct. With an offset of 2, the e.g.f. is x^2/2!*(sec(x) + tan(x)). - Peter Bala, Sep 08 2021

a(n) is the number of ranked unlabeled binary tree shapes compatible with the binary perfect phylogeny (n,3). - Noah A Rosenberg, Jun 03 2022

Extensions

Sequence corrected and extended by Mike Tryczak, Jun 17 2015