cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A373778 Triangle T(n, k) read by rows: Maximum number of patterns of length k in a permutation of length n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 6, 5, 1, 1, 2, 6, 12, 6, 1, 1, 2, 6, 19, 21, 7, 1, 1, 2, 6, 23, 41, 28, 8, 1, 1, 2, 6, 24, 71, 76, 36, 9, 1, 1, 2, 6, 24, 94, 156, 114, 45, 10, 1, 1, 2, 6, 24, 112, 273, 291, 162, 55, 11, 1, 1, 2, 6, 24, 119, 408, 614, 477, 220, 66, 12, 1
Offset: 1

Views

Author

Thomas Scheuerle, Jun 18 2024

Keywords

Comments

Let P be a permutation of the set {1, 2, ..., n}. We consider all subsequences from P of length k and count the different permutation patterns obtained. T(n, k) is the greatest count among all P.
For n > 3 and k = n, the number of permutations that realize the maximum count is given by A002464(n).
Row sums are <= 2^(n-1) (after a result from Herb Wilf).
Row sums are >= A088532(n). This means that a pattern of length k, which realizes the maximum possible downset size, does not always contain only those patterns in its downset, which do again maximize their downset sizes themselves. A088532(n) can be interpreted as the maximum size of a downset in the pattern posets of [n].
Statistical results show that the maximum number of patterns occurs among the permutations that, when represented as a 2D pointset, maximize the average distance between neighboring points.

Examples

			The triangle begins:
   n| k: 1| 2| 3|  4|  5|  6| 7
  =============================
  [1]    1
  [2]    1, 1
  [3]    1, 2, 1
  [4]    1, 2, 4,  1
  [5]    1, 2, 6,  5,  1
  [6]    1, 2, 6, 12,  6, 1
  [7]    1, 2, 6, 19, 21, 7, 1
  ...
T(3, 2) = 2 because we have:
  permutations  subsequences      patterns           number of patterns
  {1,2,3} : {1,2},{1,3},{2,3} : [1,2],[1,2],[1,2] :  1.
  {1,3,2} : {1,3},{1,2},{3,2} : [1,2],[1,2],[2,1] :  2.
  {2,1,3} : {2,1},{2,3},{1,3} : [2,1],[1,2],[1,2] :  2.
  {2,3,1} : {2,3},{2,1},{3,1} : [1,2],[2,1],[2,1] :  2.
  {3,1,2} : {3,1},{3,2},{1,2} : [2,1],[2,1],[1,2] :  2.
  {3,2,1} : {3,2},{3,1},{2,1} : [2,1],[2,1],[2,1] :  1.
A pattern is a set of indices that may sort a selected subsequence into an increasing sequence.

Crossrefs

Cf. A002464, A088532, A124188, A342474.
Cf. A371823, A373877, A374411.

Programs

  • PARI
    row(n) = my(rowp = vector(n!, i, numtoperm(n, i)), v = vector(n)); for (j=1, n, for (i=1, #rowp, my(r = rowp[i], list = List()); forsubset([n,j], s, my(ss = Vec(s)); vp = vector(j, ik, r[ss[ik]]); vs = Vec(vecsort(vp,,1)); listput(list, vs);); v[j] = max(v[j], #Set(list)););); v; \\ Michel Marcus, Jun 20 2024

Formula

T(n, k) = k!, if n >= A342474(k).
T(n, k) >= A371823(n, k).
T(n, k) >= A374411(n+1, k+1)/(k+1).

Extensions

a(41)-a(59) from Michel Marcus, Jun 20 2024
a(60)-a(78) from Jinyuan Wang, Jul 23 2025

A371823 Triangle T(n, k) read by rows: Maximum number of patterns of length k in a permutation from row n in A371822.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 6, 5, 1, 1, 2, 6, 12, 6, 1, 1, 2, 6, 17, 21, 7, 1, 1, 2, 6, 22, 41, 28, 8, 1, 1, 2, 6, 24, 69, 73, 36, 9, 1, 1, 2, 6, 24, 94, 156, 113, 45, 10, 1, 1, 2, 6, 24, 109, 273, 291, 162, 55, 11, 1, 1, 2, 6, 24, 118, 408, 614, 477, 220, 66, 12, 1, 1, 2, 6, 24, 120, 526, 1094, 1127, 699, 286, 78, 13, 1
Offset: 1

Views

Author

Thomas Scheuerle, Jun 22 2024

Keywords

Comments

The row sums agree for n = 1..8 and 10..11 with A088532(n), where n = 11 was the last known value of A088532. The process described in A371822 gives in row 9 the permutation {6,1,9,4,7,2,5,8,3} but the closest optimal permutation would have been: {6,2,9,4,7,1,5,8,3}.

Examples

			The triangle begins:
   n| k: 1| 2| 3|  4|  5|  6|  7| 8| 9
  ====================================
  [1]    1
  [2]    1, 1
  [3]    1, 2, 1
  [4]    1, 2, 4,  1
  [5]    1, 2, 6,  5,  1
  [6]    1, 2, 6, 12,  6,  1
  [7]    1, 2, 6, 17, 21,  7,  1
  [8]    1, 2, 6, 22, 41, 28,  8, 1
  [9]    1, 2, 6, 24, 69, 73, 36, 9, 1

Crossrefs

Cf. A371822.
Cf. A088532, A342474, A373778.

Formula

T(n, k) <= A373778(n, k).
Conjecture: T(n, n-2) = ceiling(n*(n-1)/2), for n > 6. This is expected because this triangle does asymptotically approximate the factorial numbers from the left to the right and Pascal's triangle from right to the left.

A092603 a(n) = Sum_{k=1..n} min(k!, binomial(n,k)).

Original entry on oeis.org

1, 2, 4, 8, 15, 31, 62, 126, 283, 539, 1177, 2459, 4969, 10781, 22297, 45116, 95759, 201615, 400755, 830859, 1741455, 3505627, 7099561, 14607199, 30112789, 60176505, 121626832, 247652036, 504389269, 1010060135, 2030792857, 4102303316, 8289676399, 16659582365
Offset: 1

Views

Author

Rob Pratt, Apr 10 2004

Keywords

Comments

Upper bound on A088532(n).
The number of patterns of length k in a permutation of length n is bounded above by k! and binomial(n,k). The total number of patterns in a permutation of length n is therefore bounded above by the sum of the smaller of these two upper bounds.

Crossrefs

Cf. A088532.

Programs

  • Magma
    [&+[Min(Factorial(k),Binomial(n,k)):k in [1..n]]:n in [1..34]]; // Marius A. Burtea, Nov 14 2019
  • Mathematica
    Table[Sum[Min[k!, Binomial[n, k]], {k, 1, n}], {n, 1, 40}]
  • PARI
    a(n) = sum(k=1, n, min(k!, binomial(n, k))); \\ Michel Marcus, Nov 14 2019

Formula

a(n) ~ 2^n. - Vaclav Kotesovec, Aug 03 2015
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.