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!)
A226316 Expansion of g.f. 1/2 + 1/(1+sqrt(1-8*x+8*x^2)). 7
1, 1, 3, 12, 56, 284, 1516, 8384, 47600, 275808, 1624352, 9694912, 58510912, 356467392, 2189331648, 13540880384, 84265071360, 527232146944, 3314742364672, 20930141861888, 132673039491072, 843959152564224, 5385800362473472, 34470606645280768, 221213787774230528, 1423139139514138624 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

From Robert A. Proctor, Jul 18 2017: (Start)

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.]

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)

LINKS

Vincenzo Librandi, Table of n, a(n) for n = 0..100

W. Y. C. Chen, A. Y. L. Dai and R. D. P. Zhou, Ordered Partitions Avoiding a Permutation of Length 3, arXiv preprint arXiv:1304.3187 [math.CO], 2013.

Robert A. Proctor, Matthew J. Willis, Parabolic Catalan numbers count flagged Schur functions and their appearances as type A Demazure characters (key polynomials), arXiv preprint arXiv:1706.04649 [math.CO], 2017.

Wikipedia, Permutation pattern

Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

FORMULA

a(n) ~ sqrt((sqrt(2)-1)/Pi)*2^(n-1/2)*(2+sqrt(2))^n/n^(3/2). - Vaclav Kotesovec, Jun 29 2013

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

a(n) = A000670(n) - A335515(n). - Gus Wiseman, Jun 25 2020

EXAMPLE

From Gus Wiseman, Jun 25 2020: (Start)

The a(0) = 1 through a(3) = 12 words that are (1,2,3)-avoiding and cover an initial interval:

  ()  (1)  (1,1)  (1,1,1)

           (1,2)  (1,1,2)

           (2,1)  (1,2,1)

                  (1,2,2)

                  (1,3,2)

                  (2,1,1)

                  (2,1,2)

                  (2,1,3)

                  (2,2,1)

                  (2,3,1)

                  (3,1,2)

                  (3,2,1)

(End)

MAPLE

a:= proc(n) option remember; `if`(n<4, [1$2, 3, 12][n+1],

      ((9*n-3)*a(n-1) -(16*n-20)*a(n-2) +(8*n-16)*a(n-3))/(n+1))

    end:

seq(a(n), n=0..30);  # Alois P. Heinz, Jun 18 2013

MATHEMATICA

CoefficientList[Series[1/2 + 1 / (1 + Sqrt[1 - 8 x + 8 x^2]), {x, 0, 30}], x] (* Vincenzo Librandi, Jun 18 2013 *)

allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];

Table[Length[Select[Join@@Permutations/@allnorm[n], !MatchQ[#, {___, x_, ___, y_, ___, z_, ___}/; x<y<z]&]], {n, 0, 6}] (* Gus Wiseman, Jun 25 2020 *)

CROSSREFS

Cf. A220097.

Sequences covering an initial interval are counted by A000670.

(1,2,3)-matching permutations are counted by A056986.

(1,2,3)-avoiding permutations are counted by A000108.

(1,2,3)-matching compositions are counted by A335514.

(1,2,3)-avoiding compositions are counted by A102726.

(1,2,3)-matching patterns are counted by A335515.

(1,2,3)-avoiding patterns are counted by A226316 (this sequence).

(1,2,3)-matching permutations of prime indices are counted by A335520.

(1,2,3)-avoiding permutations of prime indices are counted by A335521.

(1,2,3)-matching compositions are ranked by A335479.

Cf. A158005, A158009, A333217, A335465.

Sequence in context: A050147 A259800 A120921 * A195261 A276902 A192132

Adjacent sequences:  A226313 A226314 A226315 * A226317 A226318 A226319

KEYWORD

nonn,changed

AUTHOR

N. J. A. Sloane, Jun 09 2013

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 July 8 04:16 EDT 2020. Contains 335504 sequences. (Running on oeis4.)