A378907 Number of permutations of [n] with at least one hit on both main diagonals.

0, 1, 0, 2, 10, 48, 270, 2004, 15406, 144656, 1399070, 15924940, 185817038, 2485431096, 33966603790, 522088434644, 8178526719550, 142034596036896, 2508925152633918, 48582127821078684, 955299461042098222, 20406401587894276040, 442067447198146300718

Offset

0,4

Comments

For a permutation P, a hit on the leading diagonal is a fixed point P(i) = i and a hit on the opposite diagonal is a reverse P(i) = n+1 - i; and here P must have one or more of each.

Equivalently, a(n) is the number of ways to place n marks on an n X n grid so that there is at least one mark in every row and column and also in both of the main diagonals.

Links

Table of n, a(n) for n=0..22.

Formula

a(n) = A000142(n) - 2*A000166(n) + A003471(n).

Example

For n = 3, the a(3) = 2 solutions are:
  X . .   . . X
  . X .   . X .
  . . X   X . .
For n = 4, one of a(4) = 10 solutions is:
  X . . .
  . . X .
  . X . .
  . . . X
All a(4) = 10 permutations of 1..4 counted are: 1324, 1342, 1423, 2314, 2431, 3124, 3241, 4132, 4213, 4231.

Prog

(PARI) \\ here B(n) gives first terms of A003471 as vector.
B(n)={my(a=vector(n+1)); a[1]=1; for(n=4, n, my(m=2-n%2); a[1+n] = (n-1)*a[n] + 2*(n-m)*a[1+n-2*m]); a}
seq(n)={Vec(serlaplace((1 - 2*exp(-x + O(x*x^n)))/(1-x)) + Ser(B(n)), -n-1)} \\ Andrew Howroyd, Dec 11 2024
(Python)
def generate_A378907(n):
    f, A000166, A378907 = 6, 2, [0, 1, 0, 2]
    A003471 = [1, 0, 0, 0]
    for i in range(4, n):
        f *= i
        A000166 = i*A000166 + (1 if i%2==0 else -1)
        d, e = (2, 4) if i%2==0 else (1, 2)
        A003471.append((i-1)*A003471[-1] + 2*(i-d)*A003471[-e])
        A003471 = A003471[1:]
        s = f - 2*A000166 + A003471[-1]
        A378907.append(s)
    return A378907
A378907 = generate_A378907(23)  # Jwalin Bhatt, Dec 27 2024

Crossrefs

Cf. A000142, A000166, A002467, A003471.

Sequence in context: A086853 A036918 A200540 * A166922 A302557 A129118

Adjacent sequences: A378904 A378905 A378906 * A378908 A378909 A378910

Keyword

nonn,easy

Author

Vikram Saraph, Dec 10 2024

Status

approved