A382909 Number of possible (area, dinv) interchanging bijections of Dyck paths of length 2n.

1, 1, 1, 1, 16, 165112971264, 7081067777179913483347996561235301491807900639024696524800000000000000000000

Offset

1,5

Comments

a(8) has 435 decimal digits.

This can be computed by taking the product of the factorial of the entries in the q,t-Catalan matrix on or above the anti-diagonal (see the paper by Lee, Li, and Loehr for the q,t-Catalan matrix).

Links

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

James Haglund, The q,t-Catalan Numbers and the Space of Diagonal Harmonics

Blake Jackson, SageMath program

Kyungyong Lee, Li Li, and Nicholas A. Loehr, A Combinatorial Approach to the Symmetry of q,t-Catalan Numbers, SIAM Journal on Discrete Mathematics, Vol. 32, Iss. 1 (2018).

Example

For n=5, the q,t-Catalan number has a matrix representation of the matrix below. By taking the product of the factorials over all entries on or above the anti-diagonal, we get 16. This is the total possible number of bijections that interchange the area and dinv statistics.
[[1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 1. 1. 0. 0. 0. 0. 0. 0. 0. 0.]
 [0. 1. 1. 1. 0. 0. 0. 0. 0. 0. 0.]
 [0. 1. 2. 1. 1. 0. 0. 0. 0. 0. 0.]
 [0. 0. 1. 2. 1. 1. 0. 0. 0. 0. 0.]
 [0. 0. 1. 2. 2. 1. 1. 0. 0. 0. 0.]
 [0. 0. 0. 1. 2. 2. 1. 1. 0. 0. 0.]
 [0. 0. 0. 0. 1. 1. 2. 1. 1. 0. 0.]
 [0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 0.]
 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 1.]]

Prog

(SageMath) # See Links section.
(Python)
from math import factorial, prod
def dyckVectors(n): # all area sequences of length n
    if n == 1: return [[0]]
    return [subword + [i] for subword in dyckVectors(n-1) for i in range(subword[-1] + 2)]
def dyckDinv(d): # diagonal inversion number (dinv statistic)
    return sum(d_i - d_j in [0, 1] for i, d_i in enumerate(d) for d_j in d[i+1:])
def qtCatalanMatrix(n):
    Tn = (n-1)*n//2+1
    mat = [[0]*Tn for _ in range(Tn)]
    for vec in dyckVectors(n):
        i = sum(vec) # area
        j = dyckDinv(vec)
        mat[Tn-i-1][j] += 1
    return mat
def numberOfBijections(n):
    mat = qtCatalanMatrix(n)
    return prod(factorial(x) for i, row in enumerate(mat) for x in row[:-i])
for i in range(1, 9):
    print(i, numberOfBijections(i)) # Andrei Zabolotskii, Sep 26 2025, after Blake Jackson

Crossrefs

Sequence in context: A013878 A058418 A372150 * A291908 A059933 A002488

Adjacent sequences: A382906 A382907 A382908 * A382910 A382911 A382912

Keyword

nonn

Author

Blake Jackson, Apr 08 2025

Status

approved