login
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 }).
1
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
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
KEYWORD
nonn,tabl
AUTHOR
Jordan Weaver, Dec 10 2018
STATUS
approved