A306506
Number T(n,k) of permutations p of [n] having at least one index i with |p(i)-i| = k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.
Original entry on oeis.org
1, 1, 1, 4, 4, 3, 15, 19, 15, 10, 76, 99, 86, 67, 42, 455, 603, 544, 455, 358, 216, 3186, 4248, 3934, 3486, 2921, 2250, 1320, 25487, 34115, 32079, 29296, 25487, 21514, 16296, 9360, 229384, 307875, 292509, 272064, 245806, 214551, 179058, 133800, 75600
Offset: 1
The 6 permutations p of [3]: 123, 132, 213, 231, 312, 321 have absolute displacement sets {|p(i)-i|, i=1..3}: {0}, {0,1}, {0,1}, {1,2}, {1,2}, {0,2}, respectively. Number 0 occurs four times, 1 occurs four times, and 2 occurs thrice. So row n=3 is [4, 4, 3].
Triangle T(n,k) begins:
1;
1, 1;
4, 4, 3;
15, 19, 15, 10;
76, 99, 86, 67, 42;
455, 603, 544, 455, 358, 216;
3186, 4248, 3934, 3486, 2921, 2250, 1320;
25487, 34115, 32079, 29296, 25487, 21514, 16296, 9360;
...
T(n+2,n+1) gives
A007680 (for n>=0).
-
b:= proc(s, d) option remember; (n-> `if`(n=0, add(x^j, j=d),
add(b(s minus {i}, d union {abs(n-i)}), i=s)))(nops(s))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..n-1))(b({$1..n}, {})):
seq(T(n), n=1..9);
# second Maple program:
T:= proc(n, k) option remember; n!-LinearAlgebra[Permanent](
Matrix(n, (i, j)-> `if`(abs(i-j)=k, 0, 1)))
end:
seq(seq(T(n, k), k=0..n-1), n=1..9);
-
T[n_, k_] := n!-Permanent[Table[If[Abs[i-j]==k, 0, 1], {i, 1, n}, {j, 1, n} ]];
Table[T[n, k], {n, 1, 9}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, May 01 2019, from 2nd Maple program *)
A078480
Number of permutations p of {1,2,...,n} such that |p(i)-i| != 1 for all i.
Original entry on oeis.org
1, 1, 1, 2, 5, 21, 117, 792, 6205, 55005, 543597, 5922930, 70518905, 910711193, 12678337945, 189252400480, 3015217932073, 51067619064873, 916176426422089, 17355904144773970, 346195850534379613, 7252654441500887309
Offset: 0
- Vincenzo Librandi, Table of n, a(n) for n = 0..200
- V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 223.
- N. S. Mendelsohn, The asymptotic series for a certain class of permutation problems, Canadian Journal of Mathematics, vol. VIII, No.2, 1956, p.238 (Example 5).
-
(* Explicit formula: *) Table[Sum[Sum[(-1)^k*(i-k)!*Binomial[2i-k,k],{k,0,i}],{i,0,n}],{n,0,21}] (* Vaclav Kotesovec, Mar 28 2011 *)
A306535
Number of permutations p of [2n] having no index i with |p(i)-i| = n.
Original entry on oeis.org
1, 1, 9, 265, 14833, 1334961, 176214841, 32071101049, 7697064251745, 2355301661033953, 895014631192902121, 413496759611120779881, 228250211305338670494289, 148362637348470135821287825, 112162153835443422680893595673, 97581073836835777732377428235481
Offset: 0
-
b:= proc(n, k) b(n, k):= `if`(k=0, n!, b(n+1, k-1) -b(n, k-1)) end:
a:= n-> b(0, 2*n):
seq(a(n), n=0..23);
seq(simplify(KummerU(-2*n, -2*n, -1)), n=0..15); # Peter Luschny, May 10 2022
-
b[n_, k_] := b[n, k] = If[k == 0, n!, b[n + 1, k - 1] - b[n, k - 1]];
a[n_] := b[0, 2n];
a /@ Range[0, 23] (* Jean-François Alcover, Apr 02 2021, after Alois P. Heinz *)
A306523
Number of permutations p of [n] having no index i with |p(i)-i| = 2.
Original entry on oeis.org
1, 1, 2, 3, 9, 34, 176, 1106, 8241, 70371, 676098, 7204713, 84252233, 1072010712, 14738107136, 217656602456, 3435793029849, 57721548509705, 1028183730411650, 19354550056977555, 383876766917923073, 8001053425278668706, 174828593537337033648, 3996207024319062050994
Offset: 0
a(3) = 3: 123, 132, 213.
a(4) = 9: 1234, 1243, 1324, 2134, 2143, 2341, 4123, 4231, 4321.
a(5) = 34: 12345, 12354, 12435, 13245, 13254, 13452, 15234, 15342, 15432, 21345, 21354, 21435, 23415, 23451, 25314, 25341, 25431, 41235, 41352, 42315, 42351, 43215, 43251, 45231, 45312, 51234, 51342, 51432, 52314, 52341, 52431, 53214, 53241, 53412.
-
b[s_, k_] := b[s, k] = With[{n = Length[s]}, If[n == 0, 1, Sum[If[Abs[i-n] == k, 0, b[s~Complement~{i}, k]], {i, s}]]];
A[n_, k_] := If[k >= n, n!, b[Range[n], k]];
a[n_] := A[n, 2];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 23}] (* Jean-François Alcover, Oct 31 2021, after Alois P. Heinz in A306512 *)
A324365
Number of permutations p of [n] having no index i with |p(i)-i| = 3.
Original entry on oeis.org
1, 1, 2, 6, 14, 53, 265, 1554, 11024, 90816, 846032, 8803826, 101011765, 1265197857, 17167351014, 250725968406, 3920074915626, 65310957981693, 1154885557082749, 21599009876309400, 425919898969718528, 8831294211199266816, 192065262001816123136
Offset: 0
a(4) = 14: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2413, 3124, 3142, 3214, 3412.
Showing 1-5 of 5 results.
Comments