A259776
Number A(n,k) of permutations p of [n] with no fixed points and displacement of elements restricted by k: 1 <= |p(i)-i| <= k, square array A(n,k), n>=0, k>=0, read by antidiagonals.
Original entry on oeis.org
1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 2, 4, 0, 0, 1, 0, 1, 2, 9, 6, 1, 0, 1, 0, 1, 2, 9, 24, 13, 0, 0, 1, 0, 1, 2, 9, 44, 57, 24, 1, 0, 1, 0, 1, 2, 9, 44, 168, 140, 45, 0, 0, 1, 0, 1, 2, 9, 44, 265, 536, 376, 84, 1, 0
Offset: 0
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
0, 0, 0, 0, 0, 0, 0, 0, ...
0, 1, 1, 1, 1, 1, 1, 1, ...
0, 0, 2, 2, 2, 2, 2, 2, ...
0, 1, 4, 9, 9, 9, 9, 9, ...
0, 0, 6, 24, 44, 44, 44, 44, ...
0, 1, 13, 57, 168, 265, 265, 265, ...
0, 0, 24, 140, 536, 1280, 1854, 1854, ...
Columns k=0-10 give:
A000007,
A059841,
A033305,
A079997,
A259777,
A259778,
A259779,
A259780,
A259781,
A259782,
A259783.
-
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)):
seq(seq(A(n, d-n), n=0..d), d=0..12);
-
b[n_, s_, k_] := b[n, s, k] = If[n==0, 1, If[MemberQ[s, n+k], b[n-1, Join[s ~Complement~ {n+k}] ~Union~ If[n-k>1, {n-k-1}, {}], k], Sum[If[j==n, 0, b[n -1, Join[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]];
Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Mar 29 2017, translated from Maple *)
A260081
Number of permutations p of [n] with no fixed points and cyclic displacement of elements restricted by three: p(i)<>i and (i-p(i) mod n <= 3 or p(i)-i mod n <= 3).
Original entry on oeis.org
1, 0, 1, 2, 9, 44, 265, 1854, 4752, 12072, 30500, 76038, 190656, 481318, 1224852, 3117528, 7944464, 20283046, 51912320, 133129054, 341972624, 879678624, 2266157892, 5846150862, 15101728320, 39058470566, 101135401556, 262158219552, 680253580304, 1766843951390
Offset: 0
a(8) = 4752: 21436587, 21436785, 21436857, 21437586, ..., 87653421, 87654123, 87654312, 87654321.
-
a:= n-> `if`(n=0, 1, LinearAlgebra[Permanent](Matrix(n, (i, j)->
`if`(i<>j and (i-j mod n<=3 or j-i mod n<=3), 1, 0)))):
seq(a(n), n=0..15);
-
a[n_] := If[n == 0, 1, Permanent[Table[If[i != j && (Mod[i - j, n] <= 3 || Mod[j - i, n] <= 3), 1, 0], {i, 1, n}, {j, 1, n}]]]; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jan 06 2016, adapted from Maple *)
A188966
T(n,k)=Number of nXk array permutations with each element moved and moved by a city block distance of no more than three.
Original entry on oeis.org
0, 1, 1, 2, 9, 2, 9, 265, 265, 9, 24, 8132, 78976, 8132, 24, 57, 154564, 22666641, 22666641, 154564, 57, 140, 2790864, 4064659324, 62394485617, 4064659324, 2790864, 140, 376, 55327556, 741295637637, 109564294856817, 109564294856817
Offset: 1
Some solutions for 5X3
..1..0..3....1..0..3....1..0..3....1..0..3....1..0..3....1..0..3....1..0..3
..2..7..6....2..7..8....2..7..6....2..7..8....2..7..8....2..7..8....2..7..8
..8..5.13....4.14.10....8.14..5....9..6..5...12..4.13....4..9.13....5.10..4
.14.12..4...13..5..6...13.11..4...13.14..4....6..9.14...11.14..5...12..9..6
.10..9.11....9.11.12...10.12..9...10.12.11...11.10..5...10..6.12...11.14.13
A376743
Number of permutations (p(1),p(2),...,p(n)) of (1,2,...,n) such that p(i)-i is in {-2,-1,4} for all i=1,...,n.
Original entry on oeis.org
1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 5, 5, 6, 8, 11, 15, 25, 35, 46, 61, 85, 125, 175, 245, 341, 470, 650, 925, 1300, 1810, 2521, 3520, 4915, 6880, 9640, 13476, 18801, 26251, 36721, 51346, 71776, 100335, 140210, 195886, 273813, 382821, 535105, 747850, 1045220
Offset: 0
- D. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), North-Holland, Amsterdam, 1970, pp. 755-770.
- Michael A. Allen and Kenneth Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, Lin. Multilin. Alg. 72:13 (2024) 2091-2103.
- Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics, 4(1) (2010), 119-135.
- Kenneth Edwards and Michael A. Allen, Strongly restricted permutations and tiling with fences, Discrete Applied Mathematics, 187 (2015), 82-90.
- Index entries for linear recurrences with constant coefficients, signature (0,0,1,1,1,2,1,0,-2,-2,0,-1,0,0,1).
See comments for other sequences related to strongly restricted permutations.
-
CoefficientList[Series[(1 - x^3 - x^4 - x^6 + x^9)/(1 - x^3 - x^4 - x^5 - 2*x^6 - x^7 + 2*x^9 + 2*x^10 + x^12 - x^15),{x,0,49}],x]
LinearRecurrence[{0, 0, 1, 1, 1, 2, 1, 0, -2, -2, 0, -1, 0, 0, 1}, {1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 5, 5, 6, 8}, 50]
A321049
Number of permutations of [n] with no fixed points where the maximal displacement of an element equals three.
Original entry on oeis.org
0, 5, 18, 44, 116, 331, 932, 2532, 6720, 17804, 47280, 125460, 331736, 874973, 2305750, 6075184, 16001968, 42130767, 110885496, 291792264, 767776064, 2020061968, 5314529928, 13981117152, 36779372688, 96751538581, 254510051546, 669494097852, 1761102380100
Offset: 3
- Alois P. Heinz, Table of n, a(n) for n = 3..1000
- Index entries for linear recurrences with constant coefficients, signature (3,0,-3,6,-7,-11,-14,0,16,18,6,-7,1,-2,1,-2,-1,1).
A321050
Number of permutations of [n] with no fixed points where the maximal displacement of an element equals four.
Original entry on oeis.org
0, 20, 111, 396, 1285, 4312, 15437, 55572, 196288, 678270, 2311191, 7856610, 26732463, 90996552, 309390463, 1049670138, 3554983881, 12027825752, 40676758809, 137534141216, 464908099716, 1571078027012, 5307751810223, 17928124690902, 60548310641344
Offset: 4
Showing 1-6 of 6 results.
Comments