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,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

M. Riehl, Forests of binary shrubs avoiding patterns of length 3

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

Adjacent sequences: A257992 A257993 A257994 * A257996 A257997 A257998

Keyword

nonn

Author

Manda Riehl, May 15 2015

Status

approved