A061061 -id:A061061 - cp's OEIS frontend

A100354 Maximal number of 1432 patterns in a permutation of 1,2,...,n.

0, 0, 0, 1, 4, 10, 20, 40, 70, 112, 168, 252, 360, 495, 661, 881, 1145, 1457, 1824, 2279, 2804, 3404, 4090, 4906, 5824, 6850, 8000, 9330, 10800, 12417, 14208, 16232, 18440, 20840, 23470, 26395, 29554, 32956, 36652, 40712, 45062, 49712, 54728, 60184

Offset: 1

Vincent Vatter, Nov 18 2004

nonn

			a(20) = 2279; the 20-permutation with the most copies of 1432 is 1, 5, 4, 3, 2, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6.

W. Stromquist, Packing layered posets into posets, manuscript.

M. Bona, B. Sagan, and V. Vatter, Pattern frequency sequences and internal zeros, Advances in Applied Mathematics 28 (2002), pp. 395-420.
M. Hildebrand, B. Sagan, and V. Vatter, Bounding quantities related to the packing density of 1(l+1)l...2, Advances in Applied Mathematics, 33 (2004), pp. 633-653.

Cf. A061061, A100355, A100356.

a(n) = max(a(k) + k*choose(n-k, 3), 1 <= k < n)

A216499 The maximum possible number of rooted triples consistent with any galled-tree (level-1 phylogenetic network) containing exactly n leaves.

Original entry on oeis.org

0, 0, 0, 2, 7, 16, 32, 55, 87, 130, 184, 252, 335, 433, 550, 686, 842, 1022, 1224, 1451, 1706, 1987, 2299, 2642, 3015, 3426, 3870, 4349, 4870, 5428, 6028, 6672, 7357, 8091, 8871, 9696, 10576, 11505, 12486, 13525, 14616, 15766, 16976, 18242, 19574, 20968

Offset: 0

Jesper Jansson, Sep 08 2012

nonn

Chao et al. (2012) proved: lim_{n --> infinity} a(n) / (3 (n choose 3)) = 2 (sqrt(3) - 1)/3 = 0.488033... and: a(n) / (3 (n choose 3)) > 2 (sqrt(3) - 1)/3 = 0.488033... for all n > 2.

a(n) = A061061(n) + (n choose 3).

J. Byrka, P. Gawrychowski, K. T. Huber and S. Kelk. Worst-case optimal approximation algorithms for maximizing triple consistency within phylogenetic networks. Journal of Discrete Algorithms, Vol. 8, Number 1, pp. 65-75, 2010.
K.-M. Chao, A.-C. Chu, J. Jansson, R. S. Lemence and A. Mancheron. Asymptotic Limits of a New Type of Maximization Recurrence with an Application to Bioinformatics. Proceedings of the Ninth Annual Conference on Theory and Applications of Models of Computation (TAMC 2012), Lecture Notes in Computer Science, Vol. 7287, pp. 177-188, Springer-Verlag Berlin Heidelberg, 2012.
J. Jansson, N. B. Nguyen and W.-K. Sung. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network. SIAM Journal on Computing, Vol. 35, Number 5, pp. 1098-1121, Society for Industrial and Applied Mathematics (SIAM), 2006.

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A000292 (the analogous sequence for level-0 phylogenetic networks).

a:= proc(n) option remember; `if`(n=0, 0, max(seq(
      binomial(i, 3) +2*binomial(i, 2)*(n-i)+
      i*binomial(n-i, 2) + a(n-i), i=1..n)))
    end:
seq(a(n), n=0..70);  # Alois P. Heinz, Jan 28 2016

a[0] = 0; a[n_] := a[n] = Max[Table[Binomial[i, 3] + 2*Binomial[i, 2]*(n-i) + i*Binomial[n-i, 2] + a[n-i], {i, 1, n}]]; Table[a[n], {n, 0, 70}] (* Jean-François Alcover, Oct 24 2016 *)

a(0) = 0,

a(n) = max_{1<=i<=n} [C(i,3) +2*C(i,2)*(n-i) +i*C(n-i,2) +a(n-i)] for n>0.

A342646 Maximal number of 4213 patterns in a permutation of 1,2,...,n.

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 6, 13, 24, 40, 62, 96, 138, 192, 264, 354

Offset: 0

Peter Kagey, Mar 20 2021

Equivalently the maximal number of 1342, 2431, and 3124 patterns.

			For n = 7, a(7) = 13 because the permutation 7532146 has 13 instances of the pattern 4213, namely: 7536, 7526, 7516, 7546, 7324, 7326, 7314, 7316, 7214, 7216, 5324, 5314, and 5214.
Moreover, all other permutations in S_7 have 13 or fewer instances of this pattern.

M. H. Albert, M. D. Atkinson, C. C.Handley, D. A. Holton, and W. Stromquist, On packing densities of permutations, The Electronic Journal of Combinatorics, 9(1) (2002).
David Bevan, The permutation class Av(4213,2143), arXiv:1510.06328 [math.CO], 2015.
FindStat, St000750: The number of occurrences of the pattern 4213 in a permutation.
Rob Pratt, Greatest number of occurrences of the pattern 4213 in a permutation, Mathematics Stack Exchange.
Eric Weisstein's World of Mathematics, Permutation Pattern

Analogous for other patterns: A000292 (123), A000332 (1234), A061061 (132), A100354 (1432).

Cf. A005802, A022558

a(10)-a(12) from Rob Pratt

a(13)-a(15) from Bert Dobbelaere, Mar 26 2021

A100355 Maximal number of 15432 patterns in a permutation of 1,2,...,n.

Original entry on oeis.org

0, 0, 0, 0, 1, 5, 15, 35, 70, 140, 252, 420, 660, 990, 1485, 2145, 3003, 4095, 5460, 7280, 9520, 12240, 15504, 19381, 24226, 29926, 36576, 44276, 53135, 63761, 75905, 89705, 105305, 122865, 143340, 166272, 191850, 220270, 251755, 287715, 327395, 371043

Offset: 1

Vincent Vatter, Nov 18 2004

nonn

			a(24) = 19381; the 24-permutation with the most copies of 15432 is 1, 5, 4, 3, 2, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6.

W. Stromquist, Packing layered posets into posets, manuscript.

M. Bona, B. Sagan, and V. Vatter, Pattern frequency sequences and internal zeros, Advances in Applied Mathematics 28 (2002), pp. 395-420.
M. Hildebrand, B. Sagan, and V. Vatter, Bounding quantities related to the packing density of 1(l+1)l...2, Advances in Applied Mathematics, 33 (2004), pp. 633-653.

Cf. A061061, A100354, A100356.

a(n) = max(a(k) + k*choose(n-k, 4), 1 <= k < n)

A100356 Maximal number of 165432 patterns in a permutation of 1,2,...,n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 6, 21, 56, 126, 252, 504, 924, 1584, 2574, 4004, 6006, 9009, 13104, 18564, 25704, 34884, 46512, 62016, 81396, 105336, 134596, 170016, 212520, 265650, 328900, 403650, 491400, 593775, 712531, 855037, 1019467, 1208257, 1424017

Offset: 1

Vincent Vatter, Nov 18 2004

nonn

			a(12) = 502; the 12-permutation with the most copies of 165432 is 2, 1, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3.

W. Stromquist, Packing layered posets into posets, manuscript.

M. Bona, B. Sagan, and V. Vatter, Pattern frequency sequences and internal zeros, Advances in Applied Mathematics 28 (2002), pp. 395-420.
M. Hildebrand, B. Sagan, and V. Vatter, Bounding quantities related to the packing density of 1(l+1)l...2, Advances in Applied Mathematics, 33 (2004), pp. 633-653.

Cf. A061061, A100354, A100355.

a(n) = max(a(k) + k*choose(n-k, 5), 1 <= k < n)

A342853 Maximal number of 1324 patterns in a permutation of 1,2,...,n.

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 6, 13, 24, 42, 68, 106, 153, 217, 300

Offset: 0

Peter Kagey, Mar 25 2021

Equivalently the maximal number of 4231 patterns in a permutation of 1,2,...,n.

			For n = 5, the permutation 14325 has a(5) = 3 subsequences with the same relative order as 1324: 1435, 1425, and 1325.
All other permutations in S_5 have 3 or fewer such subsequences.

M. H. Albert, M. D. Atkinson, C. C.Handley, D. A. Holton, and W. Stromquist, On packing densities of permutations, The Electronic Journal of Combinatorics, 9(1) (2002).
Miklós Bóna. A new record for 1324-avoiding permutations European Journal of Mathematics 1 (2015), 198-206.
Anders Claesson, Vít Jelínek, and Einar Steingrímsson, Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns, Journal of Combinatorial Theory, Series A, 199.8 (2012), 1680-1691.
FindStat, St000405: The number of occurrences of the pattern 1324 in a permutation.
User Noodle9, answer to Patterns in Permutations, Code Golf Stack Exchange.
Eric Weisstein's World of Mathematics, Permutation Pattern

Analogous for other patterns: A000292 (123), A000332 (1234), A061061 (132), A100354 (1432), A342646 (4213), A342854 (2413).

a(11) from Code Golf Stack Exchange link added by Peter Kagey, Mar 25 2021

a(12)-a(14) from Hugo Pfoertner, Mar 26 2021

A342854 Maximal number of 2413 patterns in a permutation of 1,2,...,n.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 5, 9, 17, 26, 41, 60, 88, 120, 163, 213

Offset: 0

Peter Kagey, Mar 25 2021

Equivalently the maximal number of 3142 patterns in a permutation of 1,2,...,n.

			For n = 6, the permutation 246135 has a(6) = 5 subsequences with the same relative order as 2413: 2413, 2613, 2615, 4615, and 4635.
All other permutations in S_6 have 5 or fewer such subsequences.

M. H. Albert, M. D. Atkinson, C. C.Handley, D. A. Holton, and W. Stromquist, On packing densities of permutations, The Electronic Journal of Combinatorics, 9(1) (2002).
Eric Weisstein's World of Mathematics, Permutation Pattern

Analogous for other patterns: A000292 (123), A000332 (1234), A061061 (132), A100354 (1432), A342646 (4213), A342853 (1324).

Cf. A342860.

a(11)-a(14) from Hugo Pfoertner, Mar 26 2021

a(15) from Hugo Pfoertner, Apr 05 2021

cp's OEIS Frontend

A100354 Maximal number of 1432 patterns in a permutation of 1,2,...,n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

A216499 The maximum possible number of rooted triples consistent with any galled-tree (level-1 phylogenetic network) containing exactly n leaves.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A342646 Maximal number of 4213 patterns in a permutation of 1,2,...,n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A100355 Maximal number of 15432 patterns in a permutation of 1,2,...,n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

A100356 Maximal number of 165432 patterns in a permutation of 1,2,...,n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

A342853 Maximal number of 1324 patterns in a permutation of 1,2,...,n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A342854 Maximal number of 2413 patterns in a permutation of 1,2,...,n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions