login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A306455 Total number of covered falling diagonals in all n X n permutation matrices. 5
0, 1, 3, 14, 73, 454, 3253, 26480, 241505, 2440538, 27075301, 327197452, 4278799105, 60205974230, 907025841317, 14567520651224, 248474458923073, 4485765986251570, 85454391074596165, 1713134893536617348, 36052727133118151201, 794697884305583064302 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

A covered diagonal in a permutation matrix contains at least one 1.

Alternatively: Total number of covered raising diagonals in all n X n permutation matrices.

Also one half of the total number of all covered diagonals in all n X n permutation matrices.

Sum over all permutations p of [n] of the cardinality of the (signed) displacement set {p(i)-i, i=1..n}.

Alternatively: Sum over all permutations p of [n] of the cardinality of the set {p(i)+i, i=1..n}.

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..450

Wikipedia, Permutation

Wikipedia, Permutation matrix

FORMULA

E.g.f.: (exp(-x)*(x+1)+x-1)/(x-1)^2.

a(n) = ((2*n^2-5*n+1)*a(n-1) - (n-1)*(n^2-4*n+2)*a(n-2) - (n-2)*(n-1)^2*a(n-3)) / (n-2) for n > 2, a(n) = n*(n+1)/2 for n < 3.

a(n) = Sum_{k=1..n} k * A125182(n,k).

a(n) = A259834(n+2) - n!.

a(n) = Sum_{k=1-n..n-1} A306461(n,k).

a(n) = Sum_{k=1-n..n-1} |k|! * A306234(n,k).

a(n) mod 2 = 1 - (n mod 2) = A059841(n) for n >= 2.

EXAMPLE

The 6 permutations p of [3]: 123, 132, 213, 231, 312, 321 have (signed) displacement sets {p(i)-i, i=1..3}: {0}, {-1,0,1}, {-1,0,1}, {-2,1}, {-1,2}, {-2,0,2}, representing the indices of covered falling diagonals in the permutation matrices

  [1    ]  [1    ]  [  1  ]  [  1  ]  [    1]  [    1]

  [  1  ]  [    1]  [1    ]  [    1]  [1    ]  [  1  ]

  [    1]  [  1  ]  [    1]  [1    ]  [  1  ]  [1    ] , respectively, the sum of the set cardinalities gives a(3) = 1 + 3 + 3 + 2 + 2 + 3 = 14.

MAPLE

a:= proc(n) option remember; `if`(n<3, n*(n+1)/2,

      ((2*n^2-5*n+1)*a(n-1)-(n-1)*(n^2-4*n+2)*a(n-2)

      -(n-2)*(n-1)^2*a(n-3))/(n-2))

    end:

seq(a(n), n=0..23);

CROSSREFS

Cf. A000142, A059841, A125182, A259834, A306234, A306461.

Sequence in context: A080238 A307443 A213228 * A277939 A210346 A074549

Adjacent sequences:  A306452 A306453 A306454 * A306456 A306457 A306458

KEYWORD

nonn

AUTHOR

Alois P. Heinz, Feb 16 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 25 17:14 EST 2020. Contains 331245 sequences. (Running on oeis4.)