|
|
A226316
|
|
Expansion of g.f. 1/2 + 1/(1+sqrt(1-8*x+8*x^2)).
|
|
15
|
|
|
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
|
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
|
|
|
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
|
|
EXAMPLE
|
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:
|
|
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
|
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.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|