Vikram Saraph - cp's OEIS frontend

User: Vikram Saraph

Vikram Saraph has authored 1 sequences.

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

Vikram Saraph, Dec 10 2024

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.

			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.

Cf. A000142, A000166, A002467, A003471.

\\ 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

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

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

cp's OEIS Frontend

User: Vikram Saraph

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Python

Formula