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

1, 1, 2, 6, 34, 342, 6408

Offset

1,3

Comments

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

Links

Table of n, a(n) for n=1..7.

Nantel Bergeron and Sara Billey, RC-Graphs and Schubert Polynomials, Experimental Mathematics, Vol. 2, No. 4 (1993), pp. 257-269; Project Euclid link.

Moriah Elkin, Three Formulas for CSM Classes of Open Quiver Loci, arXiv:2511.17723 [math.CO], 2025-2026.

Example

For n = 4, the not-necessarily-reduced pipe dreams that represent the identity permutation are shown below.
In this visualization, 1 represents a cross, and 0 represents a bump. There are 6 total.
  [0 0 0 0]  [0 1 0 0]  [0 0 1 0]  [0 0 1 0]  [0 0 0 0]  [0 1 1 0]
  [0 0 0 0]  [1 0 0 0]  [0 1 0 0]  [0 0 0 0]  [0 1 0 0]  [1 0 0 0]
  [0 0 0 0]  [0 0 0 0]  [0 0 0 0]  [1 0 0 0]  [1 0 0 0]  [1 0 0 0]
  [0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0], [0 0 0 0]

Prog

(SageMath)
from itertools import combinations
from sage.all import *
def mats(n):
    """
    Generate all n x n matrices with entries in {0, 1}
    such that all 1s occur strictly above the antidiagonal.
    """
    # Positions strictly above the antidiagonal:
    # i + j < n - 1
    positions = [
        (i, j)
        for i in range(n)
        for j in range(n)
        if i + j < n - 1
    ]
    mats = []
    # For every subset of allowed positions
    for r in range(len(positions) + 1):
        for subset in combinations(positions, r):
            M = matrix(ZZ, n, n)
            for (i, j) in subset:
                M[i, j] = 1
            mats.append(M)
    return mats
def diag_pos(n):
    """
    Return positions above the antidiagonal
    ordered by diagonals i-j = const,
    with diagonals listed from top-right
    to bottom-left.
    Within each diagonal, positions are read
    from top to bottom.
    """
    pos = []
    # Possible values of i-j
    # start at the top-right corner and move toward bottom-left
    for d in range(-(n - 2), n - 1):
        diag = []
        for i in range(n):
            j = i - d
            if (
                0 <= j < n and
                i + j < n - 1
            ):
                diag.append((i, j))
        pos.extend(diag)
    return pos
def mat_to_perm(M):
    """
    Associate a permutation to M.
    At position (i, j), associate the simple transposition
        s_{i+j+1} = (i+j+1, i+j+2)
    in Sage's 1-based convention.
    Read entries in diagonal order from top-right
    to bottom-left. Whenever an entry is 1,
    left-multiply by the corresponding simple transposition.
    """
    n = M.nrows()
    W = SymmetricGroup(n)
    w = W.one()
    for (i, j) in diag_pos(n):
        if M[i, j] == 1:
            k = i + j + 1
            s = W.simple_reflection(k)
            w = s * w
    return w
def count_id_PDs(n):
    counter = 0
    for M in mats(n):
        if mat_to_perm(M) == SymmetricGroup(n).one():
            counter +=1
    return counter
def id_PD_seq(n):
    '''
    Prints the sequence of the number of not-necessarily-reduced pipe dreams from 1 to n
    '''
    for i in range(1, n+1):
        print(count_id_PDs(i))

Crossrefs

Sequence in context: A168362 A274711 A076863 * A191742 A181082 A118186

Adjacent sequences: A395861 A395862 A395863 * A395865 A395866 A395867

Keyword

nonn,hard,more

Author

Ariella Petersen, May 07 2026

Status

approved