A383370 Number of partial orders on {1,2,...,n} that are contained in the usual linear order, whose dual is given by the relabelling k -> n+1-k.

1, 1, 2, 3, 12, 25, 172, 482, 5318, 19675, 333768, 1609846, 40832554, 254370640, 9459449890, 75546875426, 4061670272088

Offset: 0

Author

Ludovic Schwob, Apr 24 2025

Keywords

• nonn
• hard
• more

Comments

a(n) is the number of n X n upper triangular Boolean matrices B with all diagonal entries 1 such that B = B^2, which are symmetric about the antidiagonal. These matrices can be seen as closed sets of inversions (pairs (i,j) with 1 <= i < j <= n). A set of inversions E is closed if for all i < j < k, if E contains (i,j) and (j,k) then it contains (i,k).

Examples

			The Boolean matrices corresponding to a(4) = 12:
  1 0 0 0    1 0 0 1    1 0 0 0    1 0 0 1
  0 1 0 0    0 1 0 0    0 1 1 0    0 1 1 0
  0 0 1 0    0 0 1 0    0 0 1 0    0 0 1 0
  0 0 0 1    0 0 0 1    0 0 0 1    0 0 0 1
.
  1 0 1 0    1 0 1 1    1 0 1 0    1 0 1 1
  0 1 0 1    0 1 0 1    0 1 1 1    0 1 1 1
  0 0 1 0    0 0 1 0    0 0 1 0    0 0 1 0
  0 0 0 1    0 0 0 1    0 0 0 1    0 0 0 1
.
  1 1 0 0    1 1 0 1    1 1 1 1    1 1 1 1
  0 1 0 0    0 1 0 0    0 1 0 1    0 1 1 1
  0 0 1 1    0 0 1 1    0 0 1 1    0 0 1 1
  0 0 0 1    0 0 0 1    0 0 0 1    0 0 0 1
		

Crossrefs

Cf. A006455, A037223.

Programs

SageMath

def a(n):
    S = set()
    for P in Posets(n):
        if P.is_isomorphic(P.dual()):
            for l in P.linear_extensions():
                t = tuple(tuple(int(P.is_lequal(l[j],l[i])) for j in range(i)) for i in range(1,len(l)))
                if all(t[j][i]==t[n-i-2][n-j-2] for i in range((n-1)//2) for j in range(i,n-i-2)):
                    S.add(t)
    return len(S)

Extensions

a(10)-a(16) from Christian Sievers, May 02 2025