login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 14 21:27 EDT 2021. Contains 345041 sequences. (Running on oeis4.)