login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 7
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,4

COMMENTS

T(n,k) is defined for n,k>=0. The triangle contains only the terms with k<n. T(n,k) = 0 for k>=n.

LINKS

Alois P. Heinz, Rows n = 1..35, flattened

Wikipedia, Permutation

FORMULA

T(n,k) = n! - A306512(n,k).

T(2n,n) = T(2n,0) = A002467(2n) = (2n)! - A306535(n).

EXAMPLE

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;

  ...

MAPLE

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

MATHEMATICA

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

CROSSREFS

Columns k=0-3 give: A002467, A306511, A306524, A324366.

T(n+2,n+1) gives A007680 (for n>=0).

T(2n,n) gives A306675.

Cf. A000142, A010050, A306461, A306512, A306535.

Sequence in context: A345294 A233581 A193628 * A241056 A212618 A066602

Adjacent sequences:  A306503 A306504 A306505 * A306507 A306508 A306509

KEYWORD

nonn,tabl

AUTHOR

Alois P. Heinz, Feb 20 2019

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 24 16:29 EDT 2022. Contains 356943 sequences. (Running on oeis4.)