A266734 -id:A266734 - cp's OEIS frontend

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

1, 1, 6, 43, 352, 3114, 29004, 280221, 2782476, 28221784, 291138856, 3045298326, 32222872906, 344293297768, 3709496350512, 40256666304723, 439645950112788, 4828214610825948, 53286643424088024, 590705976259292856, 6574347641664629388, 73433973722458186608

Offset: 0

Lara Pudwell, Dec 04 2012

nonn

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

			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.

Alois P. Heinz, Table of n, a(n) for n = 0..931 (terms n=1..25 from Lara Pudwell)
Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, preprint arXiv:1505.01389 [math.CO], 2015.
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.
Robert A. Proctor, Matthew J. Willis, Parabolic Catalan numbers count flagged Schur functions and their appearances as type A Demazure characters (key polynomials), arXiv:1706.04649 [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.
N. Shar, D. Zeilberger, The (Ordinary) Generating Functions Enumerating 123-Avoiding Words with r Occurrences of Each of 1, 2,..., n are Always Algebraic, arXiv preprint arXiv:1411.5052 [math.CO], 2014.

Cf. A266734, A266735, A226316.
Column k=2 of A267479.
Row sums of A288558.

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 *)

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

a(0)=1 prepended by Alois P. Heinz, Nov 15 2019

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

Original entry on oeis.org

1, 1, 6, 90, 2520, 102011, 5176504, 307027744, 20472135280, 1496594831506, 117857270562568, 9869468603141427, 870255083860881152, 80185525536941657225, 7673807618627318341436, 759049283017632212000140, 77292554293281131959377376, 8075621155990277422800518076

Offset: 0

N. J. A. Sloane, Jan 06 2016

nonn

Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, preprint arXiv:1505.01389, 2015.
Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014

Cf. A000680, A220097, A266734.

Column k=4 of A267479.

More terms from Alois P. Heinz, Jan 14 2016

A267479 Number A(n,k) of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 6, 1, 0, 1, 1, 6, 43, 1, 0, 1, 1, 6, 90, 352, 1, 0, 1, 1, 6, 90, 1879, 3114, 1, 0, 1, 1, 6, 90, 2520, 47024, 29004, 1, 0, 1, 1, 6, 90, 2520, 102011, 1331664, 280221, 1, 0, 1, 1, 6, 90, 2520, 113400, 5176504, 41250519, 2782476, 1, 0

Offset: 0

Alois P. Heinz, Jan 15 2016

			Square array A(n,k) begins:
  1, 1,     1,       1,       1,       1,       1, ...
  0, 1,     1,       1,       1,       1,       1, ...
  0, 1,     6,       6,       6,       6,       6, ...
  0, 1,    43,      90,      90,      90,      90, ...
  0, 1,   352,    1879,    2520,    2520,    2520, ...
  0, 1,  3114,   47024,  102011,  113400,  113400, ...
  0, 1, 29004, 1331664, 5176504, 7235651, 7484400, ...

Alois P. Heinz, Antidiagonals n = 0..30, flattened
Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, arXiv:1505.01389, 2015
Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014

Columns k=0-4 give: A000007, A000012, A220097, A266734, A266735.
Main diagonal gives A000680.
First lower diagonal gives A267532.
Cf. A214015, A267480.

A(n,k) = Sum_{i=0..k} A267480(n,i).

A266741 Number of words on {1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,...,n,n,n,n} avoiding the pattern 12345.

Original entry on oeis.org

1, 1, 70, 34650, 63063000, 142951955371, 389426248416626, 1238402046254860022, 4454056622413300252928, 17668055644599543583018570, 75867559322054514745288107364, 347785237467609520037269752908904, 1684035818793607129226446293560872032

Offset: 0

N. J. A. Sloane, Jan 06 2016

nonn

Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, preprint arXiv:1505.01389, 2015.
Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014

Cf. A014608, A220097, A266734, A266735, A266737-A266740.

More terms from Alois P. Heinz, Jan 14 2016

A266737 Number of words on {1,1,1,2,2,2,3,3,3,4,4,4,...,n,n,n} avoiding the pattern 1234.

Original entry on oeis.org

1, 1, 20, 1680, 173891, 21347262, 2977892253, 455912368540, 74876841353159, 12990339123973119, 2354973430941967605, 442587722191655715108, 85717352536181708342445, 17029266882947116165470103, 3457866959157770598680361537, 715559803849259851987691458500

Offset: 0

N. J. A. Sloane, Jan 06 2016

nonn

Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, preprint arXiv:1505.01389, 2015.
Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014

Cf. A014606, A220097, A266734, A266735, A266736-A266741.

More terms from Alois P. Heinz, Jan 14 2016

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

Original entry on oeis.org

1, 1, 20, 374, 8124, 190893, 4727788, 121543500, 3212914524, 86782926068, 2384725558736, 66456350375566, 1873703883228900, 53351152389518550, 1531960347453263112, 44311785923563130392, 1289909841595078198172, 37760636720455988917420, 1110927659386926734186992

Offset: 0

N. J. A. Sloane, Jan 06 2016

nonn

Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, preprint arXiv:1505.01389 [math.CO], 2015.
Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014
Nathaniel Shar, Experimental methods in permutation patterns and bijective proof, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.

Cf. A220097, A266734, A266735, A266737-A266741.

Conjecture: a(n) = (2/Pi)*Integral_{t=0..1} sqrt((1 - t)/t)*(64*t^3 - 32*t^2)^n = Catalan(3*n)*2F1(-1-3*n,-n;1/2-3*n;1/2). - Benedict W. J. Irwin, Oct 05 2016

More terms from Alois P. Heinz, Jan 14 2016

A266740 Number of words on {1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,...,n,n,n,n} avoiding the pattern 1234.

Original entry on oeis.org

1, 1, 70, 34650, 16140983, 8854463421, 5532980565456, 3798011394008444, 2798461806432513085, 2179251644112128926809, 1774029308605731224234922, 1497612094060753803137726582, 1303178757814574200714348639251, 1163471249071555286949793002571005

Offset: 0

N. J. A. Sloane, Jan 06 2016

nonn

Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, preprint arXiv:1505.01389, 2015.
Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014

Cf. A220097, A266734, A266735, A266737-A266741.

More terms from Alois P. Heinz, Jan 14 2016

A266738 Number of words on {1,1,1,2,2,2,3,3,3,4,4,4,...,n,n,n} avoiding the pattern 12345.

Original entry on oeis.org

1, 1, 20, 1680, 369600, 117392909, 46121962742, 21198300356500, 11003612776114008, 6290031043253973544, 3887357166155963541538, 2562077915376091538040250, 1782153151031487742187453640, 1297781266782084301101836538690, 983066960483171632842827775906144

Offset: 0

N. J. A. Sloane, Jan 06 2016

nonn

Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, preprint arXiv:1505.01389, 2015.
Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014

Cf. A014606, A220097, A266734, A266735, A266736-A266741.

More terms from Alois P. Heinz, Jan 14 2016

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

Original entry on oeis.org

1, 1, 70, 3199, 173860, 10203181, 631326526, 40553993125, 2678871322640, 180830423671450, 12418980645870820, 864996624914197495, 60957211831578399100, 4338372535640598835279, 311386494956413595138930, 22513820432313175983170649, 1638226907374445245497453464

Offset: 0

N. J. A. Sloane, Jan 06 2016

nonn

Ferenc Balogh, A generalization of Gessel's generating function to enumerate words with double or triple occurrences in each letter and without increasing subsequences of a given length, preprint arXiv:1505.01389, 2015.
Shalosh B. Ekhad and Doron Zeilberger, The Generating Functions Enumerating 12..d-Avoiding Words with r occurrences of each of 1,2, ..., n are D-finite for all d and all r, 2014
Nathaniel Shar, Experimental methods in permutation patterns and bijective proof, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.

Cf. A220097, A266734, A266735, A266737-A266741.

More terms from Alois P. Heinz, Jan 14 2016

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Extensions

A267479 Number A(n,k) of words on {1,1,2,2,...,n,n} with longest increasing subsequence of length <= k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A266741 Number of words on {1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,...,n,n,n,n} avoiding the pattern 12345.

Views

Author

Keywords

Links

Crossrefs

Extensions

A266737 Number of words on {1,1,1,2,2,2,3,3,3,4,4,4,...,n,n,n} avoiding the pattern 1234.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A266740 Number of words on {1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,...,n,n,n,n} avoiding the pattern 1234.

Views

Author

Keywords

Links

Crossrefs

Extensions

A266738 Number of words on {1,1,1,2,2,2,3,3,3,4,4,4,...,n,n,n} avoiding the pattern 12345.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Extensions