login
A216234
Cumulated number of increasing admissible cuts of rooted plane trees of size n.
0
0, 1, 2, 8, 44, 312, 2772, 30024, 385688, 5737232, 96959396, 1834244296, 38390799592, 880648730416, 21968596282440, 592083291341520, 17144219069647920, 530774988154571040, 17495673315094986180, 611738880367145595720, 22614424027640541372360
OFFSET
0,3
COMMENTS
In concurrency theory, a(n) is also the cumulated sizes of computation trees induced by interleaved concurrent processes of size n.
REFERENCES
O. Bodini, A. Genitrini and F. Peschanski. Enumeration and Random Generation of Concurrent Computations. In proc. 23rd International Meeting on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA'12), Discrete Mathematics and Theoretical Computer Science, pp 83-96, 2012.
LINKS
O. Bodini, A. Genitrini, F. Peschanski, A Quantitative Study of Pure Parallel Processes, arXiv preprint arXiv:1407.1873, 2014
FORMULA
P-recurrence: (16*n-64*n^3)*a(n)+(12+72*n+112*n^2+32*n^3)*a(n+1)+(-26-62*n-4*n^3-36*n^2)*a(n+2)+(5+7*n+2*n^2)*a(n+3) = 0; a(0)=0; a(1)=1; a(2)=2.
a(n) ~ 2^(n-1/2) * n^(n-1) / exp(n-1). - Vaclav Kotesovec, Mar 08 2014
MATHEMATICA
Flatten[{0, RecurrenceTable[{-16*(-3+n)*(-7+2*n)*(-5+2*n)*a[-3+n]+4*(-5+2*n)*(3-12*n+4*n^2)*a[-2+n]-2*(28-23*n+2*n^3)*a[-1+n]+(-2+n)*(-1+2*n)*a[n]==0, a[1]==1, a[2]==2, a[3]==8}, a, {n, 1, 20}]}] (* Vaclav Kotesovec, Mar 08 2014 *)
PROG
(Python)
def a(n):
if n < 3:
return n
l = [0, 1, 2]
for i in range(n-2):
l[i%3] = ( (16*i-64*i**3)*l[i%3]+(12+72*i+112*i**2+32*i**3)*l[(i+1)%3]+(-26-62*i-4*i**3-36*i**2)*l[(i+2)%3] ) / (-5-7*i-2*i**2)
return l[i%3]
CROSSREFS
Cf. A007852.
Sequence in context: A212913 A321628 A005363 * A123307 A293905 A244430
KEYWORD
nonn
AUTHOR
Antoine Genitrini, Mar 14 2013
STATUS
approved