A357611 A refinement of the Mahonian numbers (canonical ordering).

1, 1, 1, 1, 2, 2, 1, 1, 3, 5, 3, 3, 5, 3, 1, 1, 4, 9, 9, 6, 4, 16, 11, 11, 16, 4, 6, 9, 9, 4, 1, 1, 5, 14, 19, 10, 14, 35, 5, 40, 26, 19, 61, 10, 40, 26, 35, 35, 26, 40, 10, 61, 19, 26, 40, 5, 35, 14, 10, 19, 14, 5, 1

Offset: 1

Author

Denis K. Sunko, Oct 06 2022

Keywords

• nonn
• tabf

Comments

Let T(N,d) be a Mahonian number.

(1) Find all partitions k(1) >= k(2) >= ... >= k(N) = 0 of the number d with at most N-1 parts, such that k(i) - k(i+1) <= 1 and k(N) = 0.

(2) For each such partition, draw a ribbon Young diagram with N boxes at matrix (row-column) coordinates (k(i), k(i) + i - 1), i = 1, ..., N.

(3) For each ribbon diagram, count all standard Young skew tableaux.

The numbers under (3) will add up to T(N,d), as proven in the cited reference. These refinements appear consecutively as subsequences in the sequence, ordered by increasing N and decreasing d from N(N-1)/2 to 0 for each N. The ordering within each subsequence is reverse-lexicographic by the partitions (1), i.e., from the largest k(1) down.

This ordering is called canonical because it corresponds to the ordering of generating polynomials (from the highest power down). Because of certain symmetries in the sequence (cf. the example), it is the same as increasing d from 0 to N(N-1)/2 and ordering the partitions lexicographically. For the converse convention, cf. A356802.

The sums of rows (3) are A008302. Because the latter is itself a triangle, arranged in the (N, d) plane, the present sequence is actually three-dimensional: each number in the triangle A008302 can be replaced by the row numbers (3), each of which is thus coordinatized by (N, d, m), the last coordinate being its position in the row.

The range of the m coordinate is the number of partitions satisfying the constraint (1). It is proven in the cited reference to be equal to the coefficient of q^d in the q-binomial theorem: coeff[q^d] Product_{k=1..N-1} (1 + q^k).

This is a different ordering of A060351 and A335845 because every standard Young ribbon diagram of a given shape corresponds to a permutation with a given descent set, see the example. - Andrey Zabolotskiy, Oct 08 2024

However, the orderings in A060351 and A335845 cannot be considered a refinement of Mahonians because the terms adding to a single Mahonian do not appear consecutively in them, beginning with N=5 in the example. - Denis K. Sunko, Dec 27 2024

Examples

			The first nontrivial terms in the sequence are a(11) = a(12) = 3, corresponding to the refinement T(4, 3) = 6 = 3 + 3. The terms from a(1) to a(10) are the Mahonian numbers themselves, because the refinement is trivial for them (there is only one partition satisfying the given constraints).
Specifically, the row T(N, d) with N=4 and d=3 corresponds to Young ribbon diagrams with 4 cells such that the sum of the row indices of cells (with the top row having index 0) is equal to 3. There are two such diagrams:
  (A) ##   (B)   #
      #        ###
      #
3 = 2+1+0+0 = 1+1+1+0 are the corresponding integer partitions, which are referenced in the Comments section, listed in the lexicographic order. These partitions have descent sets (indices of elements followed by a smaller element) {1,2} and {3}, respectively (they both sum up to 3, necessarily).
Diagram (A) can be filled in as a standard Young diagram in 3 ways:
   12   14   13
   3    2    2
   4    3    4
Diagram (B) can be filled in in 3 ways, too:
    2    3    1
  134  124  234
Thus, the row T(4, 3) is 3, 3. These standard Young ribbon diagrams, when read bottom-left to top-right, become permutations of 1234 with major index 3, namely 4312, 3214, 4213 with the descent set {1,2} and 1342, 1243, 2341 with the descent set {3} (same descent sets as those of the corresponding partitions!).
The data in triangular form are:
N, d
1, 0    1,
2, 1    1,
   0    1,
3, 3    1,
   2    2,
   1    2,
   0    1,
4, 6    1,
   5    3,
   4    5,
   3    3, 3,
   2    5,
   1    3,
   0    1,
5,10    1,
   9    4,
   8    9,
   7    9, 6,
   6    4, 16,
   5    11, 11,
   4    16, 4,
   3    6, 9,
   2    9,
   1    4,
   0    1,
6,15    1,
  14    5,
  13    14,
  12    19, 10,
  11    14, 35,
  10    5, 40, 26,
   9    19, 61, 10,
   8    40, 26, 35,
   7    35, 26, 40,
   6    10, 61, 19,
   5    26, 40, 5,
   4    35, 14,
   3    10, 19,
   2    14,
   1    5,
   0    1
One can check the generating function for the number of terms in a row, e.g., for N = 4: (1 + q)(1 + q^2)(1 + q^3) = q^6 + q^5 + q^4 + 2q^3 + q^2 + q + 1.
		

Links

• Denis K. Sunko, Evaluation and spanning sets of confluent Vandermonde forms, arXiv:2209.02523 [math-ph], 2022.
• Denis K. Sunko, Evaluation and spanning sets of confluent Vandermonde forms, J. Math. Phys. 63, 082101 (2022).

Crossrefs

Cf. A008302, A356802, A060351, A335845, A360308.

Programs

SageMath

def possible_classes(n, degree):
    for stub in Partitions(degree, max_part = n-1, max_length = n-1, min_slope = -1):
        cls = list(stub)
        if cls:
            if cls[-1] < 2:
                yield cls + (n - len(cls)) * [0]
        else:
            yield n * [0]
#
def count_tableaux(cls):
    inner = []
    outer = [1]
    right = 1
    previous_part = cls[0]
    for part in cls[1:]:
        if part == previous_part:
            right += 1
            outer[-1] = right
        else:
            previous_part = part
            outer += [right]
            if right > 1:
                inner += [right-1]
    outer.reverse()
    inner.reverse()
    return StandardSkewTableaux([outer, inner]).cardinality()
#
def refine_mahonian(N, d, total = False):
    """
    Eq. (50) in DOI:10.48550/arXiv.2209.02523 was
    generated by the call refine_mahonian(8, 16, True).
    """
    res = []
    for cls in possible_classes(N,d):
        res += [count_tableaux(cls)]
    if total:
        res = (res, sum(res)) # the sum should be T(N, d)
    return res
#
def refine_mahonians_table(Nmax, total = False, canonical = True):
    res = []
    for N in range(1, Nmax + 1):
        r = []
        if canonical:
            ordering = range(N * (N - 1) // 2, -1, -1)
        else:
            ordering = range(N * (N - 1) // 2 + 1)
        for d in ordering:
            r += [refine_mahonian(N, d, total = total)]
        res += [r]
    return res
#
def refine_mahonians(Nmax, canonical = True):
    """
    Nmax = 6, canonical = True  gives seq. A357611 in the OEIS.
    Nmax = 6, canonical = False gives seq. A356802 in the OEIS.
    """
    return flatten(refine_mahonians_table(Nmax, total = False, canonical = canonical))

SageMath

from collections import Counter
def part(n, descents):
    r = tuple(sum(i <= d for d in descents) for i in (1..n))
    return (sum(r), r) # replace sum(r) by -sum(r) to obtain A356802 instead
def row(n):
    return [x[1] for x in sorted(Counter((part(n, p.descents()) for p in Permutations(n))).items())]
print(sum([row(n) for n in (1..6)], [])) # Andrey Zabolotskiy, Oct 19 2024