cp's OEIS Frontend

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

%I A378907 #47 Jan 07 2025 15:05:04
%S A378907 0,1,0,2,10,48,270,2004,15406,144656,1399070,15924940,185817038,
%T A378907 2485431096,33966603790,522088434644,8178526719550,142034596036896,
%U A378907 2508925152633918,48582127821078684,955299461042098222,20406401587894276040,442067447198146300718
%N A378907 Number of permutations of [n] with at least one hit on both main diagonals.
%C A378907 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 A378907 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 A378907 a(n) = A000142(n) - 2*A000166(n) + A003471(n).
%e A378907 For n = 3, the a(3) = 2 solutions are:
%e A378907   X . .   . . X
%e A378907   . X .   . X .
%e A378907   . . X   X . .
%e A378907 For n = 4, one of a(4) = 10 solutions is:
%e A378907   X . . .
%e A378907   . . X .
%e A378907   . X . .
%e A378907   . . . X
%e A378907 All a(4) = 10 permutations of 1..4 counted are: 1324, 1342, 1423, 2314, 2431, 3124, 3241, 4132, 4213, 4231.
%o A378907 (PARI) \\ here B(n) gives first terms of A003471 as vector.
%o A378907 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 A378907 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 A378907 (Python)
%o A378907 def generate_A378907(n):
%o A378907     f, A000166, A378907 = 6, 2, [0, 1, 0, 2]
%o A378907     A003471 = [1, 0, 0, 0]
%o A378907     for i in range(4, n):
%o A378907         f *= i
%o A378907         A000166 = i*A000166 + (1 if i%2==0 else -1)
%o A378907         d, e = (2,4) if i%2==0 else (1,2)
%o A378907         A003471.append((i-1)*A003471[-1] + 2*(i-d)*A003471[-e])
%o A378907         A003471 = A003471[1:]
%o A378907         s = f - 2*A000166 + A003471[-1]
%o A378907         A378907.append(s)
%o A378907     return A378907
%o A378907 A378907 = generate_A378907(23)  # _Jwalin Bhatt_, Dec 27 2024
%Y A378907 Cf. A000142, A000166, A002467, A003471.
%K A378907 nonn,easy
%O A378907 0,4
%A A378907 _Vikram Saraph_, Dec 10 2024