A257995 Forests of binary shrubs on 3n vertices avoiding 321.

1, 2, 37, 866, 23285, 679606, 20931998, 669688835, 22040134327, 741386199872, 25376258521393, 880977739374392, 30946637156662975, 1097929752363923490, 39284677690031136567, 1415992852373003788459

Offset: 0

Author

Manda Riehl, May 15 2015

Keywords

• nonn

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
• M. Riehl, Forests of binary shrubs avoiding patterns of length 3

Crossrefs

A001764, A002293, A060941 and A144097 enumerate binary shrubs avoiding other patterns of length 3.

Programs

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 *)