OFFSET
1,5
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
LINKS
D. K. Sunko, Evaluation and spanning sets of confluent Vandermonde forms, arXiv:2209.02523 [math-ph], 2022.
D. K. Sunko, Evaluation and spanning sets of confluent Vandermonde forms, J. Math. Phys. 63, 082101 (2022).
EXAMPLE
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.
PROG
(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
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Denis K. Sunko, Oct 06 2022
STATUS
approved