|
|
A076540
|
|
Number of branches in all ordered trees with n edges.
|
|
7
|
|
|
1, 3, 11, 41, 154, 582, 2211, 8437, 32318, 124202, 478686, 1849498, 7161556, 27784460, 107980515, 420300045, 1638238710, 6393535170, 24980504010, 97704407790, 382509199020, 1498824792660, 5877754713870, 23067328421826, 90590960500524, 356002519839652
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
a(n) is the number of parking functions of size n avoiding the patterns 213, 312, and 321. - Lara Pudwell, Apr 10 2023
|
|
LINKS
|
|
|
FORMULA
|
a(n) = (3*n^2-2*n+1)*binomial(2*n, n)/(2*(n+1)*(2*n-1)).
G.f.: (1-z)*(C-1)/sqrt(1-4*z), where C=(1-sqrt(1-4*z))/(2*z) is the Catalan function.
a(n) = binomial(2n-1, n-2) + binomial(2n-2, n-1). - David Callan, Nov 06 2003
a(n+1) = [x^n](1 + x + x^2)*(1 + x)^(2*n) = binomial(2*n,n) + binomial(2*n,n-1) + binomial(2*n,n-2). - Peter Bala, Jun 15 2015
D-finite with recurrence (n+1)*a(n) +(-7*n+1)*a(n-1) +2*(7*n-12)*a(n-2) +4*(-2*n+7)*a(n-3)=0. - R. J. Mathar, Jul 26 2022
|
|
EXAMPLE
|
a(3)=11 because the five ordered trees with 3 edges have 1+3+2+2+3 = 11 branches altogether.
|
|
MATHEMATICA
|
Table[Binomial[2 n, n] + Binomial[2 n, n-1] + Binomial[2 n, n-2], {n, 0, 30}] (* Vincenzo Librandi, Jun 17 2015 *)
|
|
PROG
|
(PARI) vector(30, n, binomial(2*n-1, n-2)+binomial(2*n-2, n-1)) \\ Michel Marcus, Jun 17 2015
(Magma) [Binomial(2*n, n)+Binomial(2*n, n-1)+Binomial(2*n, n-2): n in [0..30]]; // Vincenzo Librandi, Jun 17 2015
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|