A129535 -id:A129535 - cp's OEIS frontend

A129534 Triangle read by rows: T(n,k) = number of permutations p of 1,...,n, with min(|p(i)-p(i-1)|, i=2..n) = k (n>=2, k>=1).

2, 6, 22, 2, 106, 14, 630, 88, 2, 4394, 614, 32, 35078, 4874, 366, 2, 315258, 43638, 3912, 72, 3149494, 435002, 42808, 1494, 2, 34620010, 4775184, 496222, 25224, 160, 415222566, 57214716, 6164470, 393792, 6054, 2, 5395737242, 742861262, 82190752, 6070408, 160784, 352

Offset: 2

Emeric Deutsch, May 05 2007

Row n has floor(n/2) terms. Row sums are the factorial numbers (A000142). T(n,1) = A129535(n). Sum(T(n,k), k>=2) = A002464(n). If, in the definition, min is replaced by max, then one obtains A064482.

			T(4,2) = 2 because we have 3142 and 2413.
Triangle starts:
     2;
     6;
    22,   2;
   106,  14;
   630,  88,  2;
  4394, 614, 32;
  ...

R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.40.

Alois P. Heinz, Rows n = 2..18, flattened

Cf. A000142, A129535, A002464, A064482.

k:=3: with(combinat): a:=proc(n) local P,ct,i: P:=permute(n): ct:=0: for i from 1 to n! do if min(seq(abs(P[i][j]-P[i][j-1]),j=2..n))=k then ct:=ct+1 else ct:=ct: fi: od: ct: end: seq(a(n),n=2..8); # yields the first 7 entries in any specified column k

More terms from R. J. Mathar, Oct 11 2007

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 }).

Original entry on oeis.org

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

Jordan Weaver, Dec 10 2018

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).

			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;

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.

Column k=2 gives A129535.

Row sums give A000142 (for n>1).

cp's OEIS Frontend

A129534 Triangle read by rows: T(n,k) = number of permutations p of 1,...,n, with min(|p(i)-p(i-1)|, i=2..n) = k (n>=2, k>=1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Extensions