A259784 Number T(n,k) of permutations p of [n] with no fixed points where the maximal displacement of an element equals k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
1, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 1, 3, 5, 0, 0, 0, 6, 18, 20, 0, 0, 1, 12, 44, 111, 97, 0, 0, 0, 24, 116, 396, 744, 574, 0, 0, 1, 44, 331, 1285, 3628, 5571, 3973, 0, 0, 0, 84, 932, 4312, 15038, 34948, 46662, 31520, 0, 0, 1, 159, 2532, 15437, 59963, 181193, 359724, 434127, 281825, 0
Offset: 0
Examples
Triangle T(n,k) begins: 1; 0, 0; 0, 1, 0; 0, 0, 2, 0; 0, 1, 3, 5, 0; 0, 0, 6, 18, 20, 0; 0, 1, 12, 44, 111, 97, 0; 0, 0, 24, 116, 396, 744, 574, 0; 0, 1, 44, 331, 1285, 3628, 5571, 3973, 0;
Links
- Alois P. Heinz, Rows n = 0..20, flattened
Crossrefs
Programs
-
Maple
b:= proc(n, s, k) option remember; `if`(n=0, 1, `if`(n+k in s, b(n-1, (s minus {n+k}) union `if`(n-k>1, {n-k-1}, {}), k), add(`if`(j=n, 0, b(n-1, (s minus {j}) union `if`(n-k>1, {n-k-1}, {}), k)), j=s))) end: A:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), b(n, {$max(1, n-k)..n}, k)): T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)): seq(seq(T(n, k), k=0..n), n=0..12); -
Mathematica
b[n_, s_, k_] := b[n, s, k] = If[n==0, 1, If[MemberQ[s, n+k], b[n-1, (s ~Complement~ {n+k}) ~Union~ If[n-k>1, {n-k-1}, {}], k], Sum[If[j==n, 0, b[n-1, (s ~Complement~ {j}) ~Union~ If[n-k>1, {n-k-1}, {}], k]], {j, s}]] ]; A[n_, k_] := If[k == 0, If[n == 0, 1, 0], b[n, Range[Max[1, n-k], n], k]]; T[n_, k_] := A[n, k] - If[k == 0, 0, A[n, k-1]]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 05 2019, after Alois P. Heinz *)