OFFSET
0,2
COMMENTS
We define a shrub as a rooted, ordered tree with the only vertices being the root and leaves. We then label our shrubs' vertices with integers such that each child has a larger label than its parent. We associate a permutation to a tree by reading the labels from left to right by levels, starting with the root. A forest is an ordered collection of trees where all vertices in the forest have distinct labels. We associate a permutation to a forest by reading the permutation associated to each tree and then concatenating. We then enumerate labeled forests of binary shrubs whose associated permutation avoids 321.
LINKS
David Bevan, Table of n, a(n) for n = 0..993
D Bevan, D Levin, P Nugent, J Pantone, L Pudwell, Pattern avoidance in forests of binary shrubs, arXiv preprint arXiv:1510:08036, 2015
MAPLE
gf := RootOf(_Z^10*z^10+18*_Z^9*z^9+123*_Z^8*z^8+(-3*z^8+420*z^7+54*z^6)*_Z^7+(-36*z^7+751*z^6+486*z^5)*_Z^6+(-138*z^6+354*z^5+1053*z^4)*_Z^5+(3*z^6-228*z^5-213*z^4+162*z^3+729*z^2)*_Z^4+(18*z^5-215*z^4+2*z^3-360*z^2)*_Z^3+(15*z^4+24*z^3-71*z^2-54*z)*_Z^2+(-z^4+24*z^3-8*z^2+54*z-1)*_Z+4*z^2+4*z+1)^(1/2):
seq(coeff(series(gf, z, 21), z, i), i=0..20);
MATHEMATICA
b[k_]:=k(k+1)/2; n[k_]:=n[k]=Join[{b[k+1], b[k+1]-1}, Table[b[i], {i, k, 1, -1}], {1}]; v[1]={1, 0, 1}; v[k_]:=v[k]=Module[{s=MapIndexed[#1n[First@#2]&, v[k-1]]}, Table[Total[If[i>Length@#, 0, #[[i]]]&/@s], {i, Length@Last@s}]]; a[k_]:=a[k]=Total@v[k]; Array[a, 20] (* David Bevan, Oct 27 2015 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Manda Riehl, May 15 2015
STATUS
approved