A322481 Permutation breadth triangle: B(n,k) is the number of permutations w in S_n with breadth(w) = k, where breadth(w) = min({ |i-j|+|w(i)-w(j)| : 1 <= i < j <= n }).

0, 0, 2, 0, 6, 0, 0, 22, 2, 0, 0, 106, 14, 0, 0, 0, 630, 90, 0, 0, 0, 0, 4394, 644, 2, 0, 0, 0, 0, 35078, 5222, 20, 0, 0, 0, 0, 0, 315258, 47464, 158, 0, 0, 0, 0, 0, 0, 3149494, 477346, 1960, 0, 0, 0, 0, 0, 0

Offset

1,3

Comments

B(n,1) = 0 for all n, because for any 1<=i,j<=n and any w in S_n, 2 <= |i-j|+|w(i)-w(j)| <= breadth(w).

Links

Table of n, a(n) for n=1..55.

D. Bevan, C. Homberger, and B. E. Tenner, Prolific permutations and permuted packings: downsets containing many large patterns, arXiv:1608.06931 [math.CO], 2016_2017; J. Combin. Theory A., 153:98-121, 2018.

Example

For n=4, k=3, the B(4,3) = 2 permutations in S_4 with breadth 3 are [2,4,1,3] and [3,1,4,2] in one-line notation.
Triangle: B(n,k) begins:
  0;
  0,       2;
  0,       6,      0;
  0,      22,      2,    0;
  0,     106,     14,    0, 0;
  0,     630,     90,    0, 0, 0;
  0,    4394,    644,    2, 0, 0, 0;
  0,   35078,   5222,   20, 0, 0, 0, 0;
  0,  315258,  47464,  158, 0, 0, 0, 0, 0;
  0, 3149494, 477346, 1960, 0, 0, 0, 0, 0, 0;

Crossrefs

Column k=2 gives A129535.

Row sums give A000142 (for n>1).

Sequence in context: A329893 A047918 A321981 * A262886 A138701 A332400

Adjacent sequences: A322478 A322479 A322480 * A322482 A322483 A322484

Keyword

nonn,tabl

Author

Jordan Weaver, Dec 10 2018

Status

approved