login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008305 Triangle read by rows: a(n,k) = number of permutations of [n] allowing i->i+j (mod n), j=0..k-1. 12
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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.

REFERENCES

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

LINKS

Alois P. Heinz, Rows n = 1..22, 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.

FORMULA

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

EXAMPLE

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,

...

MAPLE

with(LinearAlgebra):

a:= (n, k)-> Permanent(Matrix(n,

             (i, j)-> `if`(0<=j-i and j-i<k or j-i<k-n, 1, 0))):

seq(seq(a(n, k), k=1..n), n=1..10);

MATHEMATICA

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 *)

CROSSREFS

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.

Sequence in context: A210227 A208757 A133643 * A208763 A249027 A266183

Adjacent sequences:  A008302 A008303 A008304 * A008306 A008307 A008308

KEYWORD

tabl,nonn

AUTHOR

N. J. A. Sloane.

EXTENSIONS

Comments and more terms from Len Smiley

More terms from Vladeta Jovovic, Oct 02 2003

Edited by Alois P. Heinz, Dec 18 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 22 12:00 EST 2018. Contains 299452 sequences. (Running on oeis4.)