|
| |
|
|
A324563
|
|
Number T(n,k) of permutations p of [n] such that k is the maximum of 0 and the number of elements in any integer interval [p(i)..i+n*[i<p(i)]]; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
|
|
20
|
|
|
|
1, 0, 1, 0, 1, 1, 0, 1, 1, 4, 0, 1, 1, 7, 15, 0, 1, 1, 11, 31, 76, 0, 1, 1, 18, 60, 185, 455, 0, 1, 1, 29, 113, 435, 1275, 3186, 0, 1, 1, 47, 215, 1001, 3473, 10095, 25487, 0, 1, 1, 76, 406, 2299, 9289, 31315, 90109, 229384, 0, 1, 1, 123, 763, 5320, 24610, 95747, 313227, 895169, 2293839
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,10
|
|
|
COMMENTS
|
Mirror image of triangle A324564.
Or as array: Number A(n,k) of permutations p of [n+k] such that k is the maximum of 0 and the number of elements in any integer interval [p(i)..i+(n+k)*[i<p(i)]]; square array A(n,k), n>=0, k>=0, read by antidiagonals upwards.
|
|
|
LINKS
|
Alois P. Heinz, Rows n = 0..23, flattened
Wikipedia, Integer intervals
Wikipedia, Iverson bracket
Wikipedia, Permanent (mathematics)
Wikipedia, Permutation
Wikipedia, Symmetric group
|
|
|
FORMULA
|
T(n,k) = |{ p in S_n : k = max_{i=1..n} (1+i-p(i)+n*[i<p(i)]) }| for n>0, T(0,0) = 1.
T(n,k) = A008305(n,k) - A008305(n,k-1) for k > 0, T(n,0) = A000007(n).
|
|
|
EXAMPLE
|
T(4,1) = A(3,1) = 1: 1234.
T(4,2) = A(2,2) = 1: 4123.
T(4,3) = A(1,3) = 7: 1423, 1432, 3124, 3214, 3412, 4132, 4213.
T(4,4) = A(0,4) = 15: 1243, 1324, 1342, 2134, 2143, 2314, 2341, 2413, 2431, 3142, 3241, 3421, 4231, 4312, 4321.
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 1, 1, 4;
0, 1, 1, 7, 15;
0, 1, 1, 11, 31, 76;
0, 1, 1, 18, 60, 185, 455;
0, 1, 1, 29, 113, 435, 1275, 3186;
0, 1, 1, 47, 215, 1001, 3473, 10095, 25487;
...
Square array A(n,k) begins:
1, 1, 1, 4, 15, 76, 455, 3186, ...
0, 1, 1, 7, 31, 185, 1275, 10095, ...
0, 1, 1, 11, 60, 435, 3473, 31315, ...
0, 1, 1, 18, 113, 1001, 9289, 95747, ...
0, 1, 1, 29, 215, 2299, 24610, 290203, ...
0, 1, 1, 47, 406, 5320, 65209, 876865, ...
...
|
|
|
MAPLE
|
b:= proc(n, k) option remember; `if`(n=k, n!,
LinearAlgebra[Permanent](Matrix(n, (i, j)->
`if`(i<=j and j<k+i or n+j<k+i, 1, 0))))
end:
# as triangle:
T:= (n, k)-> b(n, k)-`if`(k=0, 0, b(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..10);
# as array:
A:= (n, k)-> b(n+k, k)-`if`(k=0, 0, b(n+k, k-1)):
seq(seq(A(d-k, k), k=0..d), d=0..10);
|
|
|
MATHEMATICA
|
b[n_, k_] := b[n, k] = If[n == k, n!, Permanent[Table[If[i <= j && j < k + i || n + j < k + i, 1, 0], {i, 1, n}, {j, 1, n}]]];
(* as triangle: *)
T[n_, k_] := b[n, k] - If[k == 0, 0, b[n, k - 1]]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten
(* as array: *)
A[n_, k_] := b[n + k, k] - If[k == 0, 0, b[n + k, k - 1]]; Table[A[d - k, k], {d, 0, 10}, {k, 0, d}] // Flatten (* Jean-François Alcover, May 08 2019, after Alois P. Heinz *)
|
|
|
CROSSREFS
|
Columns k=0, (1+2), 3-10 give: A000007, A000012, A000032 (for n>=3), A324631, A324632, A324633, A324634, A324635, A324636, A324637.
Diagonals of the triangle (rows of the array) n=0-10 give: A002467 (for k>0), A324621, A324622, A324623, A324624, A324625, A324626, A324627, A324628, A324629, A324630.
Row sums give A000142.
T(2n,n) or A(n,n) gives A324638.
Cf. A008305, A324564.
Sequence in context: A096459 A293301 A218453 * A186372 A200893 A294583
Adjacent sequences: A324560 A324561 A324562 * A324564 A324565 A324566
|
|
|
KEYWORD
|
nonn,tabl
|
|
|
AUTHOR
|
Alois P. Heinz, Mar 06 2019
|
|
|
STATUS
|
approved
|
| |
|
|
