

A220097


Number of words on {1,1,2,2,3,3,...,n,n} avoiding the pattern 123.


13



1, 1, 6, 43, 352, 3114, 29004, 280221, 2782476, 28221784, 291138856, 3045298326, 32222872906, 344293297768, 3709496350512, 40256666304723, 439645950112788, 4828214610825948, 53286643424088024, 590705976259292856, 6574347641664629388, 73433973722458186608
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

a(n) is the number of 123avoiding ordered set partitions of {1,...,2n} where all blocks are of size 2.


LINKS

Lara Pudwell, Enumeration schemes for words avoiding permutations, in Permutation Patterns (2010), S. Linton, N. Ruskuc, and V. Vatter, Eds., vol. 376 of London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 193211. Cambridge: Cambridge University Press.


FORMULA

G.f. = sqrt( 2/(1+2*x+sqrt(112*x))) [Chen et al.]  N. J. A. Sloane, Jun 09 2013
Conjecture: a(n) = (2/Pi)*Integral_{t=0..1} sqrt((1  t)/t)*(16*t^2  4*t)^n = Catalan(2*n)*2F1(12*n,n;1/22*n;1/4).  Benedict W. J. Irwin, Oct 05 2016
a(n) = Sum_{k=0..n} (1)^(n+k)*binomial(n,k)*Catalan(n+k).  Peter Luschny, Aug 15 2017
Dfinite with recurrence: 4*n*(2*n+1)*a(n) +2*(53*n^2+63*n16)*a(n1) +9*(13*n^259*n+62)*a(n2) +18*(n2)*(2*n5)*a(n3)=0.  R. J. Mathar, Feb 21 2020


EXAMPLE

For n=2, the a(2)=6 words are 1122, 1212, 1221, 2112, 2121, 2211. For n=3, 213312 would be counted because it has no increasing subsequence of length 3, but 113223 would not be counted because it does have such an increasing subsequence.
For n=2, the a(2)=6 ordered set partitions are 12/34, 13/24, 14/23, 34/12, 24/13, 23/14. For n=3, 46/23/15 would be counted because there is no way to choose i from the first block, j from the second block, and k from the third block such that i<j<k, but 13/25/46 would not be counted because we may select 1, 2, and 4 as a 123 pattern.


MATHEMATICA

Rest@ CoefficientList[Series[Sqrt[2/(1 + 2 x + Sqrt[1  12 x])], {x, 0, 20}], x] (* Michael De Vlieger, Oct 05 2016 *)
Table[Sum[(1)^(n+k) Binomial[n, k]CatalanNumber[n+k], {k, 0, n}], {n, 1, 20}] (* Peter Luschny, Aug 15 2017 *)


CROSSREFS



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



