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

Author

Vikram Saraph, Dec 10 2024

Keywords

• nonn
• easy

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.

Examples

			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.
		

Crossrefs

Cf. A000142, A000166, A002467, A003471.

Programs

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

Formula

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