login
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
OFFSET
0,3
COMMENTS
a(n) is the number of 123-avoiding ordered set partitions of {1,...,2n} where all blocks are of size 2.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..931 (terms n=1..25 from Lara Pudwell)
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.
Anant Godbole, Adam Goyt, Jennifer Herdan, and Lara Pudwell, Pattern Avoidance in Ordered Set Partitions, arXiv preprint arXiv:1212.2530 [math.CO], 2012.
Robert A. Proctor, Matthew J. Willis, Convexity of tableau sets for type A Demazure characters (key polynomials), parabolic Catalan numbers, arXiv preprint arXiv:1706.03094 [math.CO], 2017.
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. 193-211. Cambridge: Cambridge University Press.
Nathaniel Shar, Experimental methods in permutation patterns and bijective proof, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
FORMULA
a(n) ~ 12^n/(sqrt(Pi)*(7*n/3)^(3/2)). - Vaclav Kotesovec, May 22 2013
G.f. = sqrt( 2/(1+2*x+sqrt(1-12*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(-1-2*n,-n;1/2-2*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
D-finite with recurrence: 4*n*(2*n+1)*a(n) +2*(-53*n^2+63*n-16)*a(n-1) +9*(13*n^2-59*n+62)*a(n-2) +18*(n-2)*(2*n-5)*a(n-3)=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
Column k=2 of A267479.
Row sums of A288558.
Sequence in context: A071541 A146966 A240653 * A090010 A176732 A062266
KEYWORD
nonn
AUTHOR
Lara Pudwell, Dec 04 2012
EXTENSIONS
a(0)=1 prepended by Alois P. Heinz, Nov 15 2019
STATUS
approved