login
A257995
Forests of binary shrubs on 3n vertices avoiding 321.
1
1, 2, 37, 866, 23285, 679606, 20931998, 669688835, 22040134327, 741386199872, 25376258521393, 880977739374392, 30946637156662975, 1097929752363923490, 39284677690031136567, 1415992852373003788459
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
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
A001764, A002293, A060941 and A144097 enumerate binary shrubs avoiding other patterns of length 3.
Sequence in context: A123216 A307318 A058245 * A234971 A139108 A165697
KEYWORD
nonn
AUTHOR
Manda Riehl, May 15 2015
STATUS
approved