A188494 Number of permutations p on the set [n] with the properties that abs(p(i)-i) <= 3 for all i and p(1) <= 2.

0, 1, 2, 4, 12, 42, 138, 414, 1235, 3764, 11604, 35664, 109132, 333652, 1021220, 3127709, 9578526, 29326904, 89785684, 274896606, 841682902, 2577075290, 7890425175, 24158602552, 73968049928, 226473538032, 693411153800, 2123068036904, 6500352097064

Offset: 0

Author

N. J. A. Sloane, Apr 01 2011

Keywords

• nonn
• easy

Comments

a(n) is also the permanent of the n X n matrix that has ones on its diagonal, ones on its three superdiagonals, ones on its three subdiagonals (with the exception of zeros in the (3,1) and (4,1)-entries), and is zero elsewhere.

This is row 8 of Kløve's Table 3.

Links

• Harvey P. Dale, Table of n, a(n) for n = 0..1000(first 93 terms from Nathaniel Johnston)
• Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.
• Index entries for linear recurrences with constant coefficients, signature (1,3,3,13,21,19,3,-7,-9,-5,-3,-3,-1).

Programs

Maple

with(LinearAlgebra):
A188494:= n-> `if`(n=0, 0, Permanent(Matrix(n, (i, j)->
              `if`(abs(j-i)<4 and [i, j]<>[3, 1] and [i, j]<>[4, 1], 1, 0)))):
seq(A188494(n), n=0..20);

Mathematica

LinearRecurrence[{1,3,3,13,21,19,3,-7,-9,-5,-3,-3,-1},{0,1,2,4,12,42,138,414,1235,3764,11604,35664,109132},30] (* Harvey P. Dale, Dec 27 2015 *)

PARI

concat(0, Vec(x*(x^6 +x^5 -x^4 -x^3 -x^2 +x +1) / (x^13 +3*x^12 +3*x^11 +5*x^10 +9*x^9 +7*x^8 -3*x^7 -19*x^6 -21*x^5 -13*x^4 -3*x^3 -3*x^2 -x +1) + O(x^100))) \\ Colin Barker, Dec 13 2014

Formula

From Nathaniel Johnston, Apr 10 2011: (Start)

a(n) = A188491(n+1) - A002528(n) - A002526(n).

a(n) = A002526(n-1) + A002527(n-1).

(End)

G.f.: x*(x^6 +x^5 -x^4 -x^3 -x^2 +x +1) / (x^13 +3*x^12 +3*x^11 +5*x^10 +9*x^9 +7*x^8 -3*x^7 -19*x^6 -21*x^5 -13*x^4 -3*x^3 -3*x^2 -x +1). - Colin Barker, Dec 13 2014

Extensions

Name and comments edited, and a(12)-a(28) from Nathaniel Johnston, Apr 10 2011