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

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

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;

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