|
%I #36 Jan 01 2022 04:44:04
%S 1,1,3,12,56,284,1516,8384,47600,275808,1624352,9694912,58510912,
%T 356467392,2189331648,13540880384,84265071360,527232146944,
%U 3314742364672,20930141861888,132673039491072,843959152564224,5385800362473472,34470606645280768,221213787774230528,1423139139514138624
%N Expansion of g.f. 1/2 + 1/(1+sqrt(1-8*x+8*x^2)).
%C From _Robert A. Proctor_, Jul 18 2017: (Start)
%C a(n) is the number of words of length n on {1,2,...,r} with positive multiplicities as 1 <= r <= n avoiding the pattern 123. [This is easy to see from the next comment.]
%C a(n) is the number of 123-avoiding ordered set partitions of {1,2,...,n}. [This is Cor. 2.3 of the Chen-Dai-Zhou reference.] (End)
%H Vincenzo Librandi, <a href="/A226316/b226316.txt">Table of n, a(n) for n = 0..100</a>
%H Daniel Birmajer, Juan B. Gil, David S. Kenepp, and Michael D. Weiner, <a href="https://arxiv.org/abs/2108.04302">Restricted generating trees for weak orderings</a>, arXiv:2108.04302 [math.CO], 2021.
%H W. Y. C. Chen, A. Y. L. Dai and R. D. P. Zhou, <a href="https://arxiv.org/abs/1304.3187">Ordered Partitions Avoiding a Permutation of Length 3</a>, arXiv preprint arXiv:1304.3187 [math.CO], 2013.
%H Robert A. Proctor and Matthew J. Willis, <a href="https://arxiv.org/abs/1706.04649">Parabolic Catalan numbers count flagged Schur functions and their appearances as type A Demazure characters (key polynomials)</a>, arXiv preprint arXiv:1706.04649 [math.CO], 2017.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%F a(n) ~ sqrt((sqrt(2)-1)/Pi)*2^(n-1/2)*(2+sqrt(2))^n/n^(3/2). - _Vaclav Kotesovec_, Jun 29 2013
%F Conjecture: (n+1)*a(n) +3*(-3*n+1)*a(n-1) +4*(4*n-5)*a(n-2) +8*(-n+2)*a(n-3)=0. - _R. J. Mathar_, Apr 02 2015
%F a(n) = A000670(n) - A335515(n). - _Gus Wiseman_, Jun 25 2020
%e From _Gus Wiseman_, Jun 25 2020: (Start)
%e The a(0) = 1 through a(3) = 12 words that are (1,2,3)-avoiding and cover an initial interval:
%e () (1) (1,1) (1,1,1)
%e (1,2) (1,1,2)
%e (2,1) (1,2,1)
%e (1,2,2)
%e (1,3,2)
%e (2,1,1)
%e (2,1,2)
%e (2,1,3)
%e (2,2,1)
%e (2,3,1)
%e (3,1,2)
%e (3,2,1)
%e (End)
%p a:= proc(n) option remember; `if`(n<4, [1$2, 3, 12][n+1],
%p ((9*n-3)*a(n-1) -(16*n-20)*a(n-2) +(8*n-16)*a(n-3))/(n+1))
%p end:
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jun 18 2013
%t CoefficientList[Series[1/2 + 1 / (1 + Sqrt[1 - 8 x + 8 x^2]), {x, 0, 30}], x] (* _Vincenzo Librandi_, Jun 18 2013 *)
%t allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
%t Table[Length[Select[Join@@Permutations/@allnorm[n],!MatchQ[#,{___,x_,___,y_,___,z_,___}/;x<y<z]&]],{n,0,6}] (* _Gus Wiseman_, Jun 25 2020 *)
%Y Cf. A220097.
%Y Sequences covering an initial interval are counted by A000670.
%Y (1,2,3)-matching permutations are counted by A056986.
%Y (1,2,3)-avoiding permutations are counted by A000108.
%Y (1,2,3)-matching compositions are counted by A335514.
%Y (1,2,3)-avoiding compositions are counted by A102726.
%Y (1,2,3)-matching patterns are counted by A335515.
%Y (1,2,3)-avoiding patterns are counted by A226316 (this sequence).
%Y (1,2,3)-matching permutations of prime indices are counted by A335520.
%Y (1,2,3)-avoiding permutations of prime indices are counted by A335521.
%Y (1,2,3)-matching compositions are ranked by A335479.
%Y Cf. A158005, A158009, A333217, A335465.
%K nonn
%O 0,3
%A _N. J. A. Sloane_, Jun 09 2013
|
