A395864 - OEIS

%I #18 May 18 2026 10:10:52

%S 1,1,2,6,34,342,6408

%N Number of not-necessarily-reduced pipe dreams that represent the identity permutation.

%C "Not-necessarily-reduced pipe dreams" in the sense of Moriah Elkin's paper below, proposition 5.5.

%H Nantel Bergeron and Sara Billey, <a href="https://doi.org/10.1080/10586458.1993.10504567">RC-Graphs and Schubert Polynomials</a>, Experimental Mathematics, Vol. 2, No. 4 (1993), pp. 257-269; <a href="https://projecteuclid.org/journals/experimental-mathematics/volume-2/issue-4/RC-graphs-and-Schubert-polynomials/em/1048516036.full">Project Euclid link</a>.

%H Moriah Elkin, <a href="https://doi.org/10.48550/arXiv.2511.17723">Three Formulas for CSM Classes of Open Quiver Loci</a>, arXiv:2511.17723 [math.CO], 2025-2026.

%e For n = 4, the not-necessarily-reduced pipe dreams that represent the identity permutation are shown below.

%e In this visualization, 1 represents a cross, and 0 represents a bump. There are 6 total.

%e   [0 0 0 0]  [0 1 0 0]  [0 0 1 0]  [0 0 1 0]  [0 0 0 0]  [0 1 1 0]

%e   [0 0 0 0]  [1 0 0 0]  [0 1 0 0]  [0 0 0 0]  [0 1 0 0]  [1 0 0 0]

%e   [0 0 0 0]  [0 0 0 0]  [0 0 0 0]  [1 0 0 0]  [1 0 0 0]  [1 0 0 0]

%e   [0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0]

%o (SageMath)

%o from itertools import combinations

%o from sage.all import *

%o def mats(n):

%o     """

%o     Generate all n x n matrices with entries in {0,1}

%o     such that all 1s occur strictly above the antidiagonal.

%o     """

%o     # Positions strictly above the antidiagonal:

%o     # i + j < n - 1

%o     positions = [

%o         (i, j)

%o         for i in range(n)

%o         for j in range(n)

%o         if i + j < n - 1

%o     ]

%o     mats = []

%o     # For every subset of allowed positions

%o     for r in range(len(positions) + 1):

%o         for subset in combinations(positions, r):

%o             M = matrix(ZZ, n, n)

%o             for (i, j) in subset:

%o                 M[i, j] = 1

%o             mats.append(M)

%o     return mats

%o def diag_pos(n):

%o     """

%o     Return positions above the antidiagonal

%o     ordered by diagonals i-j = const,

%o     with diagonals listed from top-right

%o     to bottom-left.

%o     Within each diagonal, positions are read

%o     from top to bottom.

%o     """

%o     pos = []

%o     # Possible values of i-j

%o     # start at the top-right corner and move toward bottom-left

%o     for d in range(-(n - 2), n - 1):

%o         diag = []

%o         for i in range(n):

%o             j = i - d

%o             if (

%o                 0 <= j < n and

%o                 i + j < n - 1

%o             ):

%o                 diag.append((i, j))

%o         pos.extend(diag)

%o     return pos

%o def mat_to_perm(M):

%o     """

%o     Associate a permutation to M.

%o     At position (i,j), associate the simple transposition

%o         s_{i+j+1} = (i+j+1, i+j+2)

%o     in Sage's 1-based convention.

%o     Read entries in diagonal order from top-right

%o     to bottom-left. Whenever an entry is 1,

%o     left-multiply by the corresponding simple transposition.

%o     """

%o     n = M.nrows()

%o     W = SymmetricGroup(n)

%o     w = W.one()

%o     for (i, j) in diag_pos(n):

%o         if M[i, j] == 1:

%o             k = i + j + 1

%o             s = W.simple_reflection(k)

%o             w = s * w

%o     return w

%o def count_id_PDs(n):

%o     counter = 0

%o     for M in mats(n):

%o         if mat_to_perm(M) == SymmetricGroup(n).one():

%o             counter +=1

%o     return counter

%o def id_PD_seq(n):

%o     '''

%o     Prints the sequence of the number of not-necessarily-reduced pipe dreams from 1 to n

%o     '''

%o     for i in range(1,n+1):

%o         print(count_id_PDs(i))

%K nonn,hard,more

%O 1,3

%A _Ariella Petersen_, May 07 2026