|
%I #29 Sep 27 2016 12:21:49
%S 1,2,37,866,23285,679606,20931998,669688835,22040134327,741386199872,
%T 25376258521393,880977739374392,30946637156662975,1097929752363923490,
%U 39284677690031136567,1415992852373003788459
%N Forests of binary shrubs on 3n vertices avoiding 321.
%C 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.
%H David Bevan, <a href="/A257995/b257995.txt">Table of n, a(n) for n = 0..993</a>
%H D Bevan, D Levin, P Nugent, J Pantone, L Pudwell, <a href="http://arxiv.org/abs/1510.08036">Pattern avoidance in forests of binary shrubs</a>, arXiv preprint arXiv:1510:08036, 2015
%H M. Riehl, <a href="https://goo.gl/XQufr6">Forests of binary shrubs avoiding patterns of length 3</a>
%p 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):
%p seq(coeff(series(gf,z,21),z,i),i=0..20);
%t 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 *)
%Y A001764, A002293, A060941 and A144097 enumerate binary shrubs avoiding other patterns of length 3.
%K nonn
%O 0,2
%A _Manda Riehl_, May 15 2015
|
