A246974 Number of 3-ary plane multitrees with n edges.

1, 1, 3, 10, 28, 93, 317, 1090, 3876, 13995, 51182, 189606, 709218, 2675230, 10166639, 38883721, 149559230, 578153160, 2245017535, 8752828951, 34250020397, 134465596581, 529509173245, 2090920335200, 8277633788511, 32846871639751, 130624556118075, 520512049658200

Offset

0,3

Comments

A k-ary plane multitree is a plane tree with edges having multiplicity and the outdegree of any node does not exceed k. The number of plane multitrees with n edges (without restriction on outdegree) is given by A002212(n). - Andrew Howroyd, Feb 24 2020

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..500 (terms 0..200 from Andrew Howroyd)

M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.

Formula

a(n) = Sum_{k=1..n+1} Sum_{i=1..k-1} Sum_{j=0..floor((n-i)/3)} (-1)^j*binomial(k, i)*binomial(i, j)*binomial(n-i, k-i-1)*binomial(n-3*j-1, i-1)/k for n > 0. - Andrew Howroyd, Feb 24 2020

From Vaclav Kotesovec, Feb 08 2026: (Start)

Recurrence: 2*(n+1)*(2*n + 3)*(5624*n^5 - 87500*n^4 + 470944*n^3 - 1040203*n^2 + 802083*n - 40554)*a(n) = (61864*n^7 - 900636*n^6 + 4220812*n^5 - 6229929*n^4 - 2680028*n^3 + 8052201*n^2 + 41976*n - 1216620)*a(n-1) + 2*(44992*n^7 - 722496*n^6 + 4088296*n^5 - 9818067*n^4 + 8239264*n^3 + 2999625*n^2 - 6709050*n + 1815156)*a(n-2) + 4*(64676*n^7 - 1135602*n^6 + 7379357*n^5 - 21941664*n^4 + 27003215*n^3 + 2023899*n^2 - 31858695*n + 18839574)*a(n-3) - 6*(39368*n^7 - 750288*n^6 + 5417176*n^5 - 18123012*n^4 + 25345143*n^3 - 29904*n^2 - 28328457*n + 13367034)*a(n-4) - (28120*n^7 - 578100*n^6 + 4429144*n^5 - 15508935*n^4 + 22679212*n^3 - 2054193*n^2 - 22361724*n + 13731876)*a(n-5) - 2*(n-6)*(5624*n^6 - 90312*n^5 + 473774*n^4 - 929670*n^3 + 343535*n^2 + 862464*n - 927639)*a(n-6) + 3*(n-7)*(n-6)*(5624*n^5 - 59380*n^4 + 177184*n^3 - 96131*n^2 - 187371*n + 110394)*a(n-7).

a(n) ~ c * d^n / n^(3/2), where d = 4.20581461562341012768366723895230421411... is the largest positive real root of the equation -3 + 2*d + 5*d^2 + 42*d^3 - 46*d^4 - 16*d^5 - 11*d^6 + 4*d^7 = 0 and c = 1.121705322778183032677463154770619344... (End)

Mathematica

Join[{1}, Table[Sum[Sum[Sum[(-1)^j * Binomial[k, i] * Binomial[i, j] * Binomial[n-i, k-i-1] * Binomial[n-3*j-1, i-1]/k, {j, 0, Floor[(n-i)/3]}], {i, 1, k-1} ], {k, 1, n+1}], {n, 1, 30}]] (* Vaclav Kotesovec, Feb 08 2026 *)

Prog

(PARI) a(n)={my(m=3); if(n<1, n==0, sum(k=1, n+1, sum(i=1, k-1, sum(j=0, (n-i)\m, (-1)^j*binomial(k, i)*binomial(i, j)*binomial(n-i, k-i-1)*binomial(n-m*j-1, i-1)))/k))} \\ Andrew Howroyd, Feb 24 2020

Crossrefs

Cf. A002212, A128720 (2-ary case), A246975 (4-ary case).

Sequence in context: A307063 A239885 A262251 * A278294 A260811 A108912

Adjacent sequences: A246971 A246972 A246973 * A246975 A246976 A246977

Keyword

nonn

Author

N. J. A. Sloane, Sep 14 2014

Extensions

Terms a(11) and beyond from Andrew Howroyd, Feb 24 2020

Status

approved