A053614 -id:A053614 - cp's OEIS frontend

A165542 Number of permutations of length n which avoid the patterns 4231 and 4123.

1, 1, 2, 6, 22, 89, 380, 1677, 7566, 34676, 160808, 752608, 3548325, 16830544, 80234659, 384132724, 1845829988, 8897740300, 43010084460, 208409687323, 1012046126532, 4923952560917, 23997719075657, 117136530812812, 572552052378494, 2802078324448067

Offset: 0

Vincent Vatter, Sep 21 2009

nonn

G.f. conjectured to be non-D-finite (see Albert et al link). - Jay Pantone, Oct 01 2015

			There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.

David Bevan, Jay Pantone, and Nathaniel Shar, Table of n, a(n) for n = 0..1000 (terms 1 through 40 by David Bevan, terms 41 through 70 by Nathaniel Shar)
Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], 2015.
C. Bean, M. Tannock and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015.
Darla Kremer and Wai Chee Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
Wikipedia, Permutation classes avoiding two patterns of length 4.

Cf. A053614, A106228, A165542, A165545, A257561, A257562.

More terms from David Bevan, Feb 04 2014

a(0)=1 prepended by Jay Pantone, Oct 01 2015

A165545 Number of permutations of length n which avoid the patterns 2341 and 3421.

Original entry on oeis.org

1, 1, 2, 6, 22, 89, 382, 1711, 7922, 37663, 182936, 904302, 4535994, 23034564, 118209806, 612165222, 3195359360, 16795435994, 88825567814, 472356139660, 2524292893556, 13549955878141, 73026827854516, 395017112175542, 2143881709415478, 11671226062503926

Offset: 0

Vincent Vatter, Sep 21 2009

nonn

These permutations have an enumeration scheme of depth 4.

G.f. is conjectured to be non-D-finite (see Albert et al link). - Jay Pantone, Oct 01 2015

			There are 22 permutations of length 4 which avoid these two patterns, so a(4)=22.

Jay Pantone, Table of n, a(n) for n = 0..1000
Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], 2015.
Darla Kremer and Wai Chee Shiu, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
V. Vatter, Enumeration schemes for restricted permutations, Combin., Prob. and Comput. 17 (2008), 137-159.
Wikipedia, Permutation classes avoiding two patterns of length 4.

Cf. A053614, A106228, A165542, A165545, A257561, A257562.

a(0)=1 prepended by Jay Pantone, Oct 01 2015

A257562 Number of permutations of length n that avoid the patterns 4123, 4231, and 4312.

Original entry on oeis.org

1, 1, 2, 6, 21, 79, 310, 1251, 5150, 21517, 90921, 387595, 1663936, 7183750, 31158310, 135661904, 592558096, 2595232344, 11392504426, 50109205789, 220777103354, 974162444028, 4303957562319, 19036842605855, 84285643628790, 373502845338552, 1656428550764640, 7351106011540209, 32643855249507805, 145040974005303590, 644756480385363800

Offset: 0

Jay Pantone, Apr 30 2015

nonn

G.f. conjectured to be non-D-finite (see Albert et al. link). Jay Pantone, Oct 01 2015

Unlike A061552, whose g.f. is also conjectured to be non-D-finite, thousands of terms of the counting sequence are known. - David Callan, Aug 29 2017

			a(4) = 21 because there are 24 permutations of length 4 and 3 of them do not avoid 4123, 4231, and 4312.

Jay Pantone, Table of n, a(n) for n = 0..5000
D. Callan, T. Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, arXiv:1705.00933 [math.CO] (2017).
David Callan, Toufik Mansour, Mark Shattuck, Enumeration of permutations avoiding a triple of 4-letter patterns is almost all done, Pure Mathematics and Applications (2019) Vol. 28, Issue 1, 14-69.
Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], (2015).

Cf. A053614, A106228, A165542, A165545, A257561, A257562.

A053617 Number of permutations of length n which avoid the patterns 1234 and 1324.

Original entry on oeis.org

1, 1, 2, 6, 22, 90, 396, 1837, 8864, 44074, 224352, 1163724, 6129840, 32703074, 176351644, 959658200, 5262988330, 29057961666, 161374413196, 900792925199, 5050924332096, 28434661250454, 160644331001476, 910455895039056, 5174722258676440, 29486753617569684

Offset: 0

Moa Apagodu, Mar 20 2000

nonn

These permutations have an "enumeration scheme" of depth 4, see D. Zeilberger's article in the links.
G.f. conjectured to be non-D-finite (see Albert et al. link). - Jay Pantone, Oct 01 2015
a(n) is the number of permutations of length n avoiding the partially ordered pattern (POP) {1>2, 1>3, 2>4, 3>4} of length 4. That is, the number of length n permutations having no subsequences of length 4 in which the first element is the largest and the fourth element is the smallest. - Sergey Kitaev, Dec 10 2020

Andrew Baxter and Jay Pantone, Table of n, a(n) for n = 0..600 (terms n=1..100 from Andrew Baxter)
Michael H. Albert, Cheyne Homberger, Jay Pantone, Nathaniel Shar, Vincent Vatter, Generating Permutations with Restricted Containers, arXiv:1510.00269 [math.CO], 2015.
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, arXiv:1903.08946 [math.CO], 2019.
Alice L. L. Gao, Sergey Kitaev, On partially ordered patterns of length 4 and 5 in permutations, The Electronic Journal of Combinatorics 26(3) (2019), P3.26.
Kremer, Darla and Shiu, Wai Chee, Finite transition matrices for permutations avoiding pairs of length four patterns, Discrete Math. 268 (2003), 171-183. MR1983276 (2004b:05006). See Table 1.
Wikipedia, Permutation classes avoiding two patterns of length 4.
D. Zeilberger, Enumeration schemes and more importantly their automatic generation, Annals of Combinatorics 2 (1998) 185-195. The link is to an overview on Doron Zeilberger's home page; there is a local copy here [Pdf file only, no active links]

Cf. A032351, A053614, A106228, A165542, A165545, A257561, A257562.

More terms from Andrew Baxter, May 20 2011

A061337 Smallest number of distinct triangular numbers which sum to n (or -1 if not possible).

Original entry on oeis.org

0, 1, -1, 1, 2, -1, 1, 2, -1, 2, 1, 2, -1, 2, 3, 1, 2, 3, 2, 3, 4, 1, 2, -1, 2, 2, 3, 2, 1, 2, 3, 2, 3, -1, 2, 3, 1, 2, 2, 2, 3, 3, 2, 2, 3, 1, 2, 3, 2, 2, 3, 2, 3, 3, 3, 1, 2, 2, 2, 3, 2, 2, 3, 3, 2, 2, 1, 2, 3, 2, 2, 3, 2, 2, 3, 3, 2, 3, 1, 2, 3, 2, 3, 2, 2, 3, 3, 2, 2, 3, 3, 1, 2, 2, 2, 3, 3, 2, 3, 2, 2, 2, 2, 3, 3, 1, 2, 3, 2, 3, 3, 2, 2, 3, 2, 2, 3, 3, 3, 2, 1, 2, 3

Offset: 0

Henry Bottomley, Apr 25 2001

sign

20 is the only case where n>3.

			a(20)=4 since 20=1+3+6+10, a(21)=1 since 21 is triangular, a(22)=2 since 22=1+21, a(23)=-1 since no combination of distinct triangular numbers sum to 23.

Cf. A000217, A002243, A053614, A061208, A061336.

A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.

Original entry on oeis.org

1, 2, 2, 3, 4, 2, 3, 4, 4, 3, 4, 4, 5, 6, 4, 5, 6, 6, 7, 6, 2, 3, 4, 4, 5, 6, 4, 3, 4, 5, 5, 6, 6, 5, 6, 4, 5, 6, 6, 7, 8, 4, 5, 6, 4, 5, 6, 6, 5, 6, 6, 7, 8, 8, 3, 4, 5, 5, 6, 7, 5, 6, 6, 7, 6, 4, 5, 6, 6, 7, 8, 6, 7, 8, 8, 5, 6, 4, 5, 6, 6, 7, 6, 6, 7, 8, 6, 7, 8, 8, 5, 6, 7, 7, 8, 9, 7, 8, 6, 7, 8, 8

Offset: 1

Jonathan Vos Post, Apr 08 2006

nonn

This problem has the optimal substructure property.

			a(1) = 1 because "1" has a single 1.
a(2) = 2 because "1+1" has two 1's.
a(3) = 2 because 3 = T(1+1) has two 1's.
a(6) = 2 because 6 = T(T(1+1)).
a(10) = 3 because 10 = T(T(1+1)+1).
a(12) = 4 because 12 = T(T(1+1)) + T(T(1+1)).
a(15) = 4 because 15 = T(T(1+1)+1+1).
a(21) = 2 because 21 = T(T(T(1+1))).
a(28) = 3 because 28 = T(T(T(1+1))+1).
a(55) = 3 because 55 = T(T(T(1+1)+1)).

W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, 1971.
R. K. Guy, Unsolved Problems Number Theory, Sect. F26.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
W. A. Beyer, M. L. Stein and S. M. Ulam, The Notion of Complexity. Report LA-4822, Los Alamos Scientific Laboratory of the University of California, Los Alamos, NM, December 1971. [Annotated scanned copy]
R. K. Guy, Some suspiciously simple sequences, Amer. Math. Monthly 93 (1986), 186-190; 94 (1987), 965; 96 (1989), 905.
Ed Pegg, Jr., Integer Complexity.
Eric Weisstein's World of Mathematics, Integer Complexity.
Wikipedia, Optimal substructure.

See also A023361 = number of compositions into sums of triangular numbers, A053614 = numbers that are not the sum of triangular numbers. Iterated triangular numbers: A050536, A050542, A050548, A050909, A007501.

Cf. A000217, A005245, A005520, A003313, A076142, A076091, A061373, A005421, A023361, A053614, A064097, A025280, A003037, A099129, A050536, A050542, A050548, A050909, A007501.

a:= proc(n) option remember; local m; m:= floor (sqrt (n*2));
      if n<3 then n
    elif n=m*(m+1)/2 then a(m)
    else min (seq (a(i)+a(n-i), i=1..floor(n/2)))
      fi
    end:
seq (a(n), n=1..110);  # Alois P. Heinz, Jan 05 2011

a[n_] := a[n] = Module[{m = Floor[Sqrt[n*2]]}, If[n < 3, n, If[n == m*(m + 1)/2, a[m], Min[Table[a[i] + a[n - i], {i, 1, Floor[n/2]}]]]]];
Array[a, 110] (* Jean-François Alcover, Jun 02 2018, from Maple *)

I do not know how many of these entries have been proved to be minimal. - N. J. A. Sloane, Apr 15 2006

Corrected and extended by Alois P. Heinz, Jan 05 2011

A176661 Partial sums of A061262.

Original entry on oeis.org

0, 3, 15, 36, 88, 145, 236, 357, 493, 704, 896, 1122, 1531, 1862, 2229, 2635, 3146, 3653, 4539, 5176, 5948, 6669, 7540, 8492, 9594, 10660, 11887, 13079, 14720, 16341, 17737, 19118, 20619, 22351, 24143, 26070, 28012, 30413, 33024, 35575, 37997

Offset: 0

Jonathan Vos Post, Apr 23 2010

nonn

Partial sums of smallest number representable as the sum of 3 triangular numbers in exactly n ways. The subsequence of triangular numbers in the partial sum begins: 3, 15, 36. The subsequence of primes in the partial sum begins: 3, 1531, 11887, 17737, 37997, 43441.

			a(13) = 0 + 3 + 12 + 21 + 52 + 57 + 91 + 121 + 136 + 211 + 192 + 226 + 409 = 1531 is prime.

Cf. A061262, A000217, A053614, A060773, A002636, A124978.

a(n) = SUM[i=0..n] A061262(i).

A334385 E.g.f.: Product_{k>=1} (1 + x^(k(k + 1)/2) / (k(k + 1)/2)!).

Original entry on oeis.org

1, 1, 0, 1, 4, 0, 1, 7, 0, 84, 841, 11, 0, 286, 4004, 1, 8024, 136136, 816, 7775256, 155195040, 54265, 1193830, 0, 109832360, 2749077760, 84987760, 296010, 10716746041, 310545275069, 1201800600, 2444026056820, 77016647623040, 0, 14402113079955304, 504073957798435640

Offset: 0

Ilya Gutkovskiy, May 11 2020

nonn

Cf. A007837, A032310, A053614 (positions of 0's), A115278, A205799.

nmax = 35; CoefficientList[Series[Product[(1 + x^(k (k + 1)/2)/(k (k + 1)/2)!), {k, 1, nmax}], {x, 0, nmax}], x] Range[0, nmax]!
a[n_] := a[n] = If[n == 0, 1, (n - 1)! Sum[DivisorSum[k, -#/(-#!)^(k/#) &, IntegerQ[Sqrt[8 # + 1]] &] a[n - k]/(n - k)!, {k, 1, n}]]; Table[a[n], {n, 0, 35}]

cp's OEIS Frontend

A165542 Number of permutations of length n which avoid the patterns 4231 and 4123.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A165545 Number of permutations of length n which avoid the patterns 2341 and 3421.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A257562 Number of permutations of length n that avoid the patterns 4123, 4231, and 4312.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A053617 Number of permutations of length n which avoid the patterns 1234 and 1324.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A061337 Smallest number of distinct triangular numbers which sum to n (or -1 if not possible).

Views

Author

Keywords

Comments

Examples

Crossrefs

A117632 Number of 1's required to build n using {+,T} and parentheses, where T(i) = i*(i+1)/2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A176661 Partial sums of A061262.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A334385 E.g.f.: Product_{k>=1} (1 + x^(k*(k + 1)/2) / (k*(k + 1)/2)!).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A334385 E.g.f.: Product_{k>=1} (1 + x^(k(k + 1)/2) / (k(k + 1)/2)!).