A378907 - OEIS

%I #47 Jan 07 2025 15:05:04

%S 0,1,0,2,10,48,270,2004,15406,144656,1399070,15924940,185817038,

%T 2485431096,33966603790,522088434644,8178526719550,142034596036896,

%U 2508925152633918,48582127821078684,955299461042098222,20406401587894276040,442067447198146300718

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

%C 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.

%C 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.

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

%e For n = 3, the a(3) = 2 solutions are:

%e   X . .   . . X

%e   . X .   . X .

%e   . . X   X . .

%e For n = 4, one of a(4) = 10 solutions is:

%e   X . . .

%e   . . X .

%e   . X . .

%e   . . . X

%e All a(4) = 10 permutations of 1..4 counted are: 1324, 1342, 1423, 2314, 2431, 3124, 3241, 4132, 4213, 4231.

%o (PARI) \\ here B(n) gives first terms of A003471 as vector.

%o 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}

%o seq(n)={Vec(serlaplace((1 - 2*exp(-x + O(x*x^n)))/(1-x)) + Ser(B(n)), -n-1)} \\ _Andrew Howroyd_, Dec 11 2024

%o (Python)

%o def generate_A378907(n):

%o     f, A000166, A378907 = 6, 2, [0, 1, 0, 2]

%o     A003471 = [1, 0, 0, 0]

%o     for i in range(4, n):

%o         f *= i

%o         A000166 = i*A000166 + (1 if i%2==0 else -1)

%o         d, e = (2,4) if i%2==0 else (1,2)

%o         A003471.append((i-1)*A003471[-1] + 2*(i-d)*A003471[-e])

%o         A003471 = A003471[1:]

%o         s = f - 2*A000166 + A003471[-1]

%o         A378907.append(s)

%o     return A378907

%o A378907 = generate_A378907(23)  # _Jwalin Bhatt_, Dec 27 2024

%Y Cf. A000142, A000166, A002467, A003471.

%K nonn,easy

%O 0,4

%A _Vikram Saraph_, Dec 10 2024