|
|
A014301
|
|
Number of internal nodes of even outdegree in all ordered rooted trees with n edges.
|
|
23
|
|
|
0, 1, 3, 11, 40, 148, 553, 2083, 7896, 30086, 115126, 442118, 1703052, 6577474, 25461493, 98759971, 383751472, 1493506534, 5820778858, 22714926826, 88745372992, 347087585824, 1358789148058, 5324148664846, 20878676356240, 81937643449468, 321786401450268
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Number of protected vertices in all ordered rooted trees with n edges. A protected vertex in an ordered tree is a vertex at least 2 edges away from its leaf descendants. - Emeric Deutsch, Aug 20 2008
Apparently the number of peaks in all Dyck paths of semilength n+1 that are the same height as the preceding peak. - David Scambler, Apr 22 2013
Define an infinite triangle by T(n,0)=A001045(n) (the first column) and T(r,c) = sum_{k=c-1, c,..,r} T(k,c-1), (the sum of all the terms in the preceding column down to row r. Then T(n,n)=a(n+1). The triangle is 0; 1,1; 1,2,3; 3,5,8,11; 5,10,18,29,40; 11,21,39,68,108,148;... Example: T(5,2)=39=the sum of the terms in column 1 from T(1,1) to T(5,1), namely, 1+2+5+10+21. - J. M. Bergot, May 17 2013
Also for n>=1 the number of unimodal functions f:[n]->[n] with f(1)<>1 and f(i)<>f(i+1). a(4) = 11: [2,3,2,1], [2,3,4,1], [2,3,4,2], [2,3,4,3], [2,4,2,1], [2,4,3,1], [2,4,3,2], [3,4,2,1], [3,4,3,1], [3,4,3,2], [4,3,2,1]. - Alois P. Heinz, May 23 2013
|
|
LINKS
|
|
|
FORMULA
|
a(n) = binomial(2*n-1, n)/3 - A000957(n)/3;
a(n) = (1/2)*Sum_{k=0..n} (-1)^(n-k)*binomial(n+k-1, k). - Vladeta Jovovic, Aug 28 2002
G.f.: (1-2*z-sqrt(1-4*z))/(3*sqrt(1-4*z)-1+4*z).
a(n) = (1/2)*Sum_{j=0..floor(n/2)} binomial(2n-2j-2, n-2).
a(n) = Sum_{k=0..n} (-1)^(n-k)*C(n+k,k-1). - Paul Barry, Jul 18 2006
D-finite with recurrence: 2*n*a(n) +(-9*n+8)*a(n-1) +(3*n-16)*a(n-2) +2*(2*n-5)*a(n-3)=0. - R. J. Mathar, Dec 03 2012
|
|
MATHEMATICA
|
Rest[CoefficientList[Series[(1-2*x-Sqrt[1-4*x])/(3*Sqrt[1-4*x]-1+4*x), {x, 0, 50}], x]] (* G. C. Greubel, Jan 15 2018 *)
|
|
PROG
|
(PARI) x='x+O('x^30); Vec((1-2*x-sqrt(1-4*x))/(3*sqrt(1-4*x)-1+4*x)) \\ G. C. Greubel, Jan 15 2018
(Magma) [(1/2)*(&+[(-1)^(n-k)*Binomial(n+k-1, k): k in [0..n]]): n in [1..30]]; // G. C. Greubel, Jan 15 2018
(Python)
from itertools import count, islice
def A014301_gen(): # generator of terms
yield from (0, 1)
a, b, c = 0, 3, 1
for n in count(1):
yield ((b:=b*((n<<1)+3<<1)//(n+2))-(a:=(c:=c*((n<<2)+2)//(n+2))-a>>1))//3
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|