A004306 -id:A004306 - cp's OEIS frontend

A008305 Triangle read by rows: a(n,k) = number of permutations of [n] allowing i->i+j (mod n), j=0..k-1.

1, 1, 2, 1, 2, 6, 1, 2, 9, 24, 1, 2, 13, 44, 120, 1, 2, 20, 80, 265, 720, 1, 2, 31, 144, 579, 1854, 5040, 1, 2, 49, 264, 1265, 4738, 14833, 40320, 1, 2, 78, 484, 2783, 12072, 43387, 133496, 362880, 1, 2, 125, 888, 6208, 30818, 126565, 439792, 1334961, 3628800

Offset: 1

N. J. A. Sloane

The point is, we are counting permutations of [n] = {1,2,...,n} with the restriction that i cannot move by more than k places. Hence the phrase "permutations with restricted displacements". - N. J. A. Sloane, Mar 07 2014

The triangle could have been defined as an infinite square array by setting a(n,k) = n! for k >= n.

			a(4,3) = 9 because 9 permutations of {1,2,3,4} are allowed if each i can be placed on 3 positions i+0, i+1, i+2 (mod 4): 1234, 1423, 1432, 3124, 3214, 3412, 4123, 4132, 4213.
Triangle begins:
  1,
  1, 2,
  1, 2,   6,
  1, 2,   9,  24,
  1, 2,  13,  44,  120,
  1, 2,  20,  80,  265,   720,
  1, 2,  31, 144,  579,  1854,   5040,
  1, 2,  49, 264, 1265,  4738,  14833,  40320,
  1, 2,  78, 484, 2783, 12072,  43387, 133496,  362880,
  1, 2, 125, 888, 6208, 30818, 126565, 439792, 1334961, 3628800,
  ...

H. Minc, Permanents, Encyc. Math. #6, 1978, p. 48

Alois P. Heinz, Rows n = 1..23, flattened
Henry Beker and Chris Mitchell, Permutations with restricted displacement, SIAM J. Algebraic Discrete Methods 8 (1987), no. 3, 338--363. MR0897734 (89f:05009)
N. S. Mendelsohn, Permutations with confined displacement, Canad. Math. Bull., 4 (1961), 29-38.
N. Metropolis, M. L. Stein, P. R. Stein, Permanents of cyclic (0,1) matrices, J. Combin. Theory, 7 (1969), 291-321.
Wikipedia, Permanent (mathematics)

Diagonals (from the right): A000142, A000166, A000179, A000183, A004307, A189389, A184965.
Diagonals (from the left): A000211 or A048162, 4*A000382 or A004306 or A000803, A000804, A000805.
a(n,ceiling(n/2)) gives A306738.
Cf. A002467, A306714.

with(LinearAlgebra):
a:= (n, k)-> Permanent(Matrix(n,
             (i, j)-> `if`(0<=j-i and j-i

a[n_, k_] := Permanent[Table[If[0 <= j-i && j-i < k || j-i < k-n, 1, 0], {i, 1,n}, {j, 1, n}]]; Table[Table[a[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Mar 10 2014, after Alois P. Heinz *)

a(n,k) = per(sum(P^j, j=0..k-1)), where P is n X n, P[ i, i+1 (mod n) ]=1, 0's otherwise.

a(n,n) - a(n,n-1) = A002467(n). - Alois P. Heinz, Mar 06 2019

Comments and more terms from Len Smiley
More terms from Vladeta Jovovic, Oct 02 2003
Edited by Alois P. Heinz, Dec 18 2010

A000803 a(n+3) = a(n+2) + a(n+1) + a(n) - 4.

Original entry on oeis.org

0, 0, 8, 4, 8, 16, 24, 44, 80, 144, 264, 484, 888, 1632, 3000, 5516, 10144, 18656, 34312, 63108, 116072, 213488, 392664, 722220, 1328368, 2443248, 4493832, 8265444, 15202520, 27961792, 51429752, 94594060, 173985600, 320009408

Offset: 0

N. J. A. Sloane

This sequence and A004306 coincide from the term "24" onwards. This follows easily by studying the two g.f.'s. - R. J. Mathar and Andrew S. Plewe, Dec 04 2007

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..400
Henry Beker and Chris Mitchell, Permutations with restricted displacement, SIAM J. Algebraic Discrete Methods 8 (1987), no. 3, 338--363. MR0897734 (89f:05009).
N. Metropolis, M. L. Stein, P. R. Stein, Permanents of cyclic (0,1) matrices, J. Combin. Theory, 7 (1969), 291-321.
H. Minc, Permanents of (0,1)-circulants, Canad. Math. Bull., 7 (1964), 253-263.
Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1).

Cf. A000804, A000805, A004306.

a000803 n = a000803_list !! n
a000803_list = 0 : 0 : 8 : zipWith (+)
               (tail $ zipWith (+) (tail a000803_list) a000803_list)
               (map (subtract 4) a000803_list)
-- Reinhard Zumkeller, Nov 18 2011

LinearRecurrence[{2,0,0,-1},{0,0,8,4},40] (* Harvey P. Dale, Mar 25 2013 *)

concat([0,0],Vec((8-12*x)/(1-2*x+x^4)+O(x^97))) \\ Charles R Greathouse IV, Nov 18 2011

G.f.: -4x^2*(3x-2) /((x-1)(x^3+x^2+x-1)) = 2(-5x^2+1)/(x^3+x^2+x-1)-2/(x-1). - R. J. Mathar, Dec 04 2007

a(0)=0, a(1)=0, a(2)=8, a(3)=4, a(n) = 2*a(n-1) - a(n-4). - Harvey P. Dale, Mar 25 2013

More terms from Larry Reeves (larryr(AT)acm.org), Mar 17 2000

A259985 Triangle read by rows: coefficients of rook polynomials.

Original entry on oeis.org

1, 1, 1, 1, 4, 2, 1, 9, 18, 6, 1, 16, 72, 96, 24, 1, 20, 130, 320, 265, 44, 1, 24, 204, 752, 1185, 672, 80, 1, 28, 294, 1456, 3521, 3892, 1617, 144, 1, 32, 400, 2496, 8264, 14272, 11776, 3776, 264, 1, 36, 522, 3936, 16659, 39924, 52071, 33480, 8577, 484, 1, 40, 660, 5840, 30210, 93568, 171060, 175360, 90745, 19080, 888, 1, 44, 814, 8272, 50677, 193556, 461208, 667832, 554532, 236808, 41745, 1632

Offset: 0

N. J. A. Sloane, Jul 13 2015

			Triangle begins:
1;
1,  1;
1,  4,  2;
1,  9,  18,    6;
1, 16,  72,   96,    24;
1, 20, 130,  320,   265,    44;
1, 24, 204,  752,  1185,   672,     80;
1, 28, 294, 1456,  3521,  3892,   1617,    144;
1, 32, 400, 2496,  8264, 14272,  11776,   3776,   264;
1, 36, 522, 3936, 16659, 39924,  52071,  33480,  8577,   484;
1, 40, 660, 5840, 30210, 93568, 171060, 175360, 90745, 19080, 888; ...

Earl Glen Whitehead, Jr., Four-discordant permutations, J. Austral. Math. Soc. Ser. A 28 (1979), no. 3, 369-377.
Earl Glen Whitehead, Jr., Four-discordant permutations (Table 1) (Annotated scanned table)

Diagonals give A004306, A005777, A005778.

cp's OEIS Frontend

A008305 Triangle read by rows: a(n,k) = number of permutations of [n] allowing i->i+j (mod n), j=0..k-1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A000803 a(n+3) = a(n+2) + a(n+1) + a(n) - 4.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A259985 Triangle read by rows: coefficients of rook polynomials.

Views

Author

Keywords

Examples

Links

Crossrefs