A220097 -id:A220097 - cp's OEIS frontend

A226316 Expansion of g.f. 1/2 + 1/(1+sqrt(1-8x+8x^2)).

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

Offset: 0

N. J. A. Sloane, Jun 09 2013

nonn

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)

			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)

Vincenzo Librandi, Table of n, a(n) for n = 0..100
Daniel Birmajer, Juan B. Gil, David S. Kenepp, and Michael D. Weiner, Restricted generating trees for weak orderings, arXiv:2108.04302 [math.CO], 2021.
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.
Anders Claesson, Giulio Cerbai, Dana C. Ernst, and Hannah Golab, Pattern-avoiding Cayley permutations via combinatorial species, arXiv:2407.19583 [math.CO], 2024.
Robert A. Proctor and 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.

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.

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

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_,_}/;xGus Wiseman, Jun 25 2020 *)

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

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

Original entry on oeis.org

1, 1, 6, 90, 1879, 47024, 1331664, 41250519, 1367533365, 47808569835, 1744233181074, 65905305836049, 2564220925607625, 102277575120518170, 4167486279986250932, 172988069360147449566, 7298137818882637998561, 312349784398279829229533, 13539988681466075755541070

Offset: 0

N. J. A. Sloane, Jan 06 2016

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..580
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; Local copy, pdf file only, no active links

Cf. A220097, A266735.

Column k=3 of A267479.

Conjecture: +3*n*(620202643096396011773 -608794959941727250938*n +146949290712243118000*n^2) *(n+1)^2 *(2*n+1)^2 *a(n) -n*(94389117512395618060544*n^6 -419724075420172456531120*n^5 +442263508538458916585360*n^4 +229131363207555256548194*n^3 -477880029525553894746823*n^2 +160086316440678171209939*n -11163647575735128211914) *a(n-1) -3*(n-1) *(23820522077322908587584*n^6 -1446304460086201780480376*n^5 +11080409117453774846145540*n^4 -35494287160655892321199502*n^3 +57163416479212379649118767*n^2 -45988763994280198223305139*n +14778623468656583258390502) *a(n-2) +36*(n-2) *(41902292735037258217056*n^6 -783254865433733876219472*n^5 +5235970136340811777332552*n^4 -17094365117036393449118734*n^3 +29518557363755878023892305*n^2 -25895204716899392803468055*n +9075752633781608162944050) *a(n-3) -8748*(n-2) *(125877543736438014048*n^2 -450267700517870762570*n +370949541619209268475) *(n-3)^2 *(2*n-7)^2 *a(n-4)=0. - R. J. Mathar, Apr 15 2016

More terms from Alois P. Heinz, Jan 14 2016

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

A220101 Number of ordered set partitions of {1,...,n} into n-1 blocks avoiding the pattern 123.

Original entry on oeis.org

0, 1, 6, 27, 112, 450, 1782, 7007, 27456, 107406, 419900, 1641486, 6418656, 25110020, 98285670, 384942375, 1508593920, 5915896470, 23213240820, 91140287370, 358042932000, 1407342229020, 5534695100220, 21777424274502, 85729014099072, 337635166767500

Offset: 1

Lara Pudwell, Dec 04 2012

Let A(i, j) denote the infinite array such that the i-th row of this array is the sequence obtained by applying the partial sum operator i times to the function n^2 for n > 0. Then A(n, n) equals a(n+1) for all n > 0. - John M. Campbell, Jan 20 2019

			An ordered set partition is a set partition where the order of the blocks is important.  A 123 pattern within such a set partition is a list of 3 elements a from block i, b from block j, and c from block k such that i < j < k and a < b < c.
For n=3, the a(3)=6 ordered partitions are 12/3, 13/2, 23/1, 3/12, 2/13, 23/1.
For n=4, the a(4)=27 ordered partitions are 12/4/3, 3/12/4, 3/4/12, 4/12/3, 4/3/12, 13/4/2, 2/4/13, 4/13/2, 4/2/13, 14/3/2, 2/14/3, 3/2/14, 2/3/14, 23/1/4, 23/4/1, 1/4/23, 4/1/23, 4/23/1, 24/1/3, 24/3/1, 3/1/24, 3/24/1, 34/1/2, 34/2/1, 2/34/1, 2/1/34, 1/34/2.

Lara Pudwell and Giorgio Balzarotti, Table of n, a(n) for n = 1..101 (first 37 terms from Lara Pudwell, terms generated by Maple code below).
W. Y. C. Chen, A. Y. L. Dai and R. D. P. Zhou, Ordered Partitions Avoiding a Permutation of Length 3, arXiv:1304.3187 [math.CO], 2013. See Eq. (2.6).
Anant Godbole, Adam Goyt, Jennifer Herdan, and Lara Pudwell, Pattern Avoidance in Ordered Set Partitions, arXiv:1212.2530 [math.CO], 2012.
Lara Pudwell, Maple code to generate this and other sequences enumerating 123-avoiding ordered set partitions.

Cf. A220097 (counts 123-avoiding ordered set partitions where all blocks have size 2), A051666, A001622.

List([1..30], n -> 3*(n-1)/(2*n-1)*Binomial(2*n-1,n-2)); # G. C. Greubel, Feb 12 2019

a220101 n = (a051666 (2 * (n - 1)) (n - 1)) `div` 2
-- Reinhard Zumkeller, Aug 05 2013

[3*(n-1)/(2*n-1)*Binomial(2*n-1,n-2): n in [1..30]]; // G. C. Greubel, Feb 12 2019

g:=(2*x^2-7*x+2+3*x*sqrt(1-4*x)-2*sqrt(1-4*x))/(2*x*sqrt(1-4*x));
series(g,x,50);
seriestolist(%); # N. J. A. Sloane, Apr 13 2014
a := n -> 3*2^(-2+2*n)*GAMMA(n-1/2)*(n-1)^2/(sqrt(Pi)*GAMMA(2+n)):
seq(simplify(a(n)), n=1..26); # Peter Luschny, Dec 14 2015

T[n_, 0] := n^2; T[n_, n_] := n^2;
T[n_, k_] := T[n, k] = T[n-1, k-1] + T[n-1, k];
a[n_] := T[2(n-1), n-1]/2;
Array[a, 26] (* Jean-François Alcover, Jul 13 2018, after Reinhard Zumkeller *)
Table[3*(n-1)/(2*n-1)*Binomial[2*n-1,n-2], {n,1,30}] (* G. C. Greubel, Feb 12 2019 *)

vector(30, n, 3*(n-1)/(2*n-1)*binomial(2*n-1,n-2)) \\ G. C. Greubel, Feb 12 2019

[3*(n-1)/(2*n-1)*binomial(2*n-1,n-2) for n in (1..30)] # G. C. Greubel, Feb 12 2019

G.f.: (2*x^2-7*x+2+3*x*sqrt(1-4*x)-2*sqrt(1-4*x))/(2*x*sqrt(1-4*x)) [see Chen et al., 2013 - Bruno Berselli, Dec 05 2012]
a(n)/a(n-1) = 2*(2*n-3)*(n-1)^2/((n+1)*(n-2)^2) for n> 2 . - Bruno Berselli, Dec 05 2012
a(n) = A051666(2*(n-1),n-1) / 2. - Reinhard Zumkeller, Aug 05 2013
a(n) = 3*(n-1)/(2*n-1)*binomial(2*n-1,n-2). [See Godbole et al., Theorem 4.] - Peter Bala, Dec 18 2013
a(n) = 3*2^(-2+2*n)*Gamma(-1/2+n)*(-1+n)^2/(sqrt(Pi)*Gamma(2+n)). - Peter Luschny, Dec 14 2015
a(n) ~ (3/4)*4^n*(1 - (21/8)/n + (393/128)/n^2 - (3055/1024)/n^3 + (99099/32768)/n^4) /sqrt(n*Pi). - Peter Luschny, Dec 16 2015
From Amiram Eldar, Feb 17 2023: (Start)
Sum_{n>=2} 1/a(n) = Pi^2/27 + 11*Pi/(27*sqrt(3)) + 1/9.
Sum_{n>=2} (-1)^n/a(n) = 4*log(phi)^2/3 + 34*log(phi)/(15*sqrt(5)) + 1/15, where phi is the golden ratio (A001622). (End)

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

A288558 Irregular triangle read by rows: distribution of inversion numbers over the set of permutations of the multiset {1,1,2,2,3,3,...,n,n} avoiding the pattern 123.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 0, 0, 0, 0, 3, 3, 6, 7, 9, 7, 5, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 4, 6, 15, 18, 28, 35, 44, 47, 49, 42, 31, 18, 9, 3, 1

Offset: 1

N. J. A. Sloane, Jun 24 2017

			Triangle begins:
1,
1,1,2,1,1,
0,0,0,0,3,3,6,7,9,7,5,2,1,
0,0,0,0,0,0,0,0,1,1,4,6,15,18,28,35,44,47,49,42,31,18,9,3,1,
...

A. M. Baxter, Algorithms for Permutation Statistics, Ph. D. Dissertation, Rutgers University, May 2011. See Table 4.1.

Row sums give A220097.

cp's OEIS Frontend

A226316 Expansion of g.f. 1/2 + 1/(1+sqrt(1-8*x+8*x^2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

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

Views

Author

Keywords

Links

Crossrefs

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

A220101 Number of ordered set partitions of {1,...,n} into n-1 blocks avoiding the pattern 123.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

Sage

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

A226316 Expansion of g.f. 1/2 + 1/(1+sqrt(1-8x+8x^2)).