A219731 - OEIS

A219731

Irregular triangle M_2(n,k) read by rows: number of maximum k-matchings in rooted plane trees of size n, 1<=k<=n/2, 2<=n.

1, 4, 9, 3, 16, 28, 25, 135, 15, 36, 462, 220, 49, 1274, 1638, 91, 64, 3024, 8400, 1820, 81, 6426, 33660, 18360, 612, 100, 12540, 112860, 125970, 15504, 121, 22869, 330330, 665665, 197505, 4389, 144, 39468, 868296, 2900898, 1700160, 134596, 169, 65065, 2091375, 10883600, 11182600, 2072070, 32890

(list; graph; refs; listen; history; text; internal format)

OFFSET

2,2

LINKS

Table of n, a(n) for n=2..50.

Stephan G. Wagner, On the number of macthings of a tree, Eu. J. Combinat. 28 (4) (2007) 1322-1330.

FORMULA

M(n,k) = sum_{l=max(n-2k,1) .. n-k} binomial(l,n-2*k)*binomial(2*n-3*k-l-1,n-k-l)*binomial(3*k+l-2,l-1)/l.

EXAMPLE

9,3;

16,28;

25,135,15;

36,462,220;

49,1274,1638,91;

64,3024,8400,1820;

81,6426,33660,18360,612;

100,12540,112860,125970,15504;

121,22869,330330,665665,197505,4389;

144,39468,868296,2900898,1700160,134596;

CROSSREFS

Sequence in context: A120869 A070436 A259450 * A217393 A285323 A365325

Adjacent sequences: A219728 A219729 A219730 * A219732 A219733 A219734

KEYWORD

nonn,tabf

AUTHOR

R. J. Mathar, Nov 26 2012

STATUS

approved