%I #67 Oct 19 2024 21:24:44
%S 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,
%T 5,14,19,10,14,35,5,40,26,19,61,10,40,26,35,35,26,40,10,61,19,26,40,5,
%U 35,14,10,19,14,5,1
%N A refinement of the Mahonian numbers (canonical ordering).
%C Let T(N,d) be a Mahonian number.
%C (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.
%C (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.
%C (3) For each ribbon diagram, count all standard Young skew tableaux.
%C 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.
%C 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.
%C 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.
%C 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).
%C 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
%H D. K. Sunko, <a href="https://arxiv.org/abs/2209.02523">Evaluation and spanning sets of confluent Vandermonde forms</a>, arXiv:2209.02523 [math-ph], 2022.
%H D. K. Sunko, <a href="https://doi.org/10.1063/5.0075576">Evaluation and spanning sets of confluent Vandermonde forms</a>, J. Math. Phys. 63, 082101 (2022).
%e 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).
%e 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:
%e (A) ## (B) #
%e # ###
%e #
%e 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).
%e Diagram (A) can be filled in as a standard Young diagram in 3 ways:
%e 12 14 13
%e 3 2 2
%e 4 3 4
%e Diagram (B) can be filled in in 3 ways, too:
%e 2 3 1
%e 134 124 234
%e 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!).
%e The data in triangular form are:
%e N, d
%e 1, 0 1,
%e 2, 1 1,
%e 0 1,
%e 3, 3 1,
%e 2 2,
%e 1 2,
%e 0 1,
%e 4, 6 1,
%e 5 3,
%e 4 5,
%e 3 3, 3,
%e 2 5,
%e 1 3,
%e 0 1,
%e 5,10 1,
%e 9 4,
%e 8 9,
%e 7 9, 6,
%e 6 4, 16,
%e 5 11, 11,
%e 4 16, 4,
%e 3 6, 9,
%e 2 9,
%e 1 4,
%e 0 1,
%e 6,15 1,
%e 14 5,
%e 13 14,
%e 12 19, 10,
%e 11 14, 35,
%e 10 5, 40, 26,
%e 9 19, 61, 10,
%e 8 40, 26, 35,
%e 7 35, 26, 40,
%e 6 10, 61, 19,
%e 5 26, 40, 5,
%e 4 35, 14,
%e 3 10, 19,
%e 2 14,
%e 1 5,
%e 0 1
%e 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.
%o (SageMath)
%o def possible_classes(n, degree):
%o for stub in Partitions(degree, max_part = n-1, max_length = n-1, min_slope = -1):
%o cls = list(stub)
%o if cls:
%o if cls[-1] < 2:
%o yield cls + (n - len(cls)) * [0]
%o else:
%o yield n * [0]
%o #
%o def count_tableaux(cls):
%o inner = []
%o outer = [1]
%o right = 1
%o previous_part = cls[0]
%o for part in cls[1:]:
%o if part == previous_part:
%o right += 1
%o outer[-1] = right
%o else:
%o previous_part = part
%o outer += [right]
%o if right > 1:
%o inner += [right-1]
%o outer.reverse()
%o inner.reverse()
%o return StandardSkewTableaux([outer, inner]).cardinality()
%o #
%o def refine_mahonian(N, d, total = False):
%o """
%o Eq. (50) in DOI:10.48550/arXiv.2209.02523 was
%o generated by the call refine_mahonian(8, 16, True).
%o """
%o res = []
%o for cls in possible_classes(N,d):
%o res += [count_tableaux(cls)]
%o if total:
%o res = (res, sum(res)) # the sum should be T(N, d)
%o return res
%o #
%o def refine_mahonians_table(Nmax, total = False, canonical = True):
%o res = []
%o for N in range(1, Nmax + 1):
%o r = []
%o if canonical:
%o ordering = range(N * (N - 1) // 2, -1, -1)
%o else:
%o ordering = range(N * (N - 1) // 2 + 1)
%o for d in ordering:
%o r += [refine_mahonian(N, d, total = total)]
%o res += [r]
%o return res
%o #
%o def refine_mahonians(Nmax, canonical = True):
%o """
%o Nmax = 6, canonical = True gives seq. A357611 in the OEIS.
%o Nmax = 6, canonical = False gives seq. A356802 in the OEIS.
%o """
%o return flatten(refine_mahonians_table(Nmax, total = False, canonical = canonical))
%o (SageMath)
%o from collections import Counter
%o def part(n, descents):
%o r = tuple(sum(i <= d for d in descents) for i in (1..n))
%o return (sum(r), r) # replace sum(r) by -sum(r) to obtain A356802 instead
%o def row(n):
%o return [x[1] for x in sorted(Counter((part(n, p.descents()) for p in Permutations(n))).items())]
%o print(sum([row(n) for n in (1..6)], [])) # _Andrey Zabolotskiy_, Oct 19 2024
%Y Cf. A008302, A356802, A060351, A335845.
%K nonn,tabf
%O 1,5
%A _Denis K. Sunko_, Oct 06 2022