login
Expansion of g.f. 1/2 + 1/(1+sqrt(1-8*x+8*x^2)).
15

%I #40 Jul 30 2024 04:29:37

%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 Anders Claesson, Giulio Cerbai, Dana C. Ernst, and Hannah Golab, <a href="https://arxiv.org/abs/2407.19583">Pattern-avoiding Cayley permutations via combinatorial species</a>, arXiv:2407.19583 [math.CO], 2024.

%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