A cornucopia of quasi-Yamanouchi tableaux
George Wang


Bound states of dark solitons and vortices in trapped
multidimensional Bose-Einstein condensates
    A. Muñoz Mateo
    December 30, 2023
================================================================================================




    Quasi-Yamanouchi tableaux are a subset of semistandard Young tableaux and refine standard Young tableaux. They are closely tied to the descent set of standard Young tableaux and were introduced by Assaf and Searles to tighten Gessel's fundamental quasisymmetric expansion of Schur functions. The descent set and descent statistic of standard Young tableaux repeatedly prove themselves useful to consider, and as a result, quasi-Yamanouchi tableaux make appearances in many ways outside of their original purpose.
 Some examples, which we present in this paper, include the Schur expansion of Jack polynomials, the decomposition of Foulkes characters, and the bigraded Frobenius image of the coinvariant algebra. While it would be nice to have a product formula enumeration of quasi-Yamanouchi tableaux in the way that semistandard and standard Young tableaux do, it has previously been shown by the author that there is little hope on that front. The goal of this paper is to address a handful of the numerous alternative enumerative approaches. 
In particular, we present enumerations of quasi-Yamanouchi tableaux using q-hit numbers, semistandard Young tableaux, weighted lattice paths, and symmetric polynomials, as well as the fundamental quasisymmetric and monomial quasisymmetric expansions of their Schur generating function.






§ INTRODUCTION


Schur polynomials have an elegant combinatorial description as a sum of monomials indexed by semistandard Young tableaux. However, as the number of variables increases, the number of semistandard Young tableaux rises dramatically, quickly making a computation using this description intractable. Ira Gessel <cit.> defined the fundamental basis for quasisymmetric polynomials and proved that Schur polynomials can instead be expressed as a sum of fundamental quasisymmetric polynomials indexed by standard Young tableaux. Since the number of standard Young tableaux of a given shape is fixed, this provides a significant computational improvement over the unbounded number of semistandard Young tableaux. Still, when the number of variables is low enough, it turns out that some of the standard Young tableaux contribute nothing to the expansion, indicating that some further improvement can be made. Sami Assaf and Dominic Searles <cit.> introduced the concept of quasi-Yamanouchi tableaux and proved that we can tighten Gessel's expansion by summing over these tableaux instead, which give exactly the nonzero terms.

Quasi-Yamanouchi tableaux are in bijection with standard Young tableaux of the same shape, and through that bijection, quasi-Yamanouchi tableaux refine standard Young tableaux by their descent statistic.
In general, descent statistics have formed a rich and fruitful area, for example in the past with Solomon's descent algebra <cit.> and subsequent study of it <cit.> or, more recently, work on shuffle-compatible permutation statistics by Gessel and Zhuang <cit.>. Descents of standard Young tableaux do not appear to be an exception.
Quasi-Yamanouchi tableaux inherit this value, and consequently, applications are readily found. In §7, we discuss some of these applications, which involve the Schur expansion of Jack polynomials, the decomposition of Foulkes characters into irreducible characters, and the bigraded Frobenius image of the coinvariant algebra. 

Semistandard Young tableaux and standard Young tableaux are each enumerated by celebrated product formulas, and one would hope that the same could be said for quasi-Yamanouchi tableaux. Unfortunately, in <cit.>, the author demonstrates that there is likely only a product formula for certain special cases due to large primes appearing for general shapes. 
The work in this paper takes a number of alternative approaches and was inspired by the surprising appearance of quasi-Yamanouchi tableaux in the coefficients of Jack polynomials under a binomial coefficient basis <cit.> and a hit number interpretation of the same coefficients. Comparing the two equivalent interpretations of the coefficients gives an enumeration of quasi-Yamanouchi tableaux in terms of hit numbers of certain Ferrers boards. We reproduce this enumeration in §3 and prove two q-analogues involving the major index and charge statistics. In §4, we give a summation formula in terms of semistandard Young tableaux, and in §5 we first give an enumeration in terms of weighted lattice paths and then using symmetric polynomials. Finally, we consider the Schur generating function in §6 and give its fundamental quasisymmetric expansion and monomial symmetric expansion.










§ PRELIMINARIES



We first present the more general concepts that will be used throughout the paper; the more specific concepts will be located at the start of their relevant section. A partition λ = (λ_1 ≥…≥λ_k > 0) is a weakly decreasing sequence of positive integers. The size of λ is denoted |λ| and is the sum of the integers of the sequence. The length of λ, ℓ(λ), is the number of integers in the partition. Let n(λ) = ∑_i=1^k (i-1)λ_i. We say that a partition λ dominates a partition μ if for all i ≥ 1, λ_1+⋯+λ_i ≥μ_1+⋯+μ_i. 

We identify a partition with its diagram, where rows are counted from bottom to top, the number of boxes in the ith row equals λ_i, and boxes are left justified. The conjugate λ is written λ' and is obtained by reflecting the diagram across the diagonal. We identify u=(i,j) with the box in the ith column and jth row. The content of a square is c(u)=i-j, and the hook-length of a box is h(u), which counts the number of boxes (a,b) such that either a>i or b>j or a=i,b=j.



We write permutations π∈ S_n in one line notation, π = π_1⋯π_n, where π_i = π(i). The descent set of π is Des(π) = { i ∈ [n-1] |  π_i > π_i+1}, and we denote the size |Des(π)| by des(π). The major index for a permutation is maj(π) = ∑_i∈Des(π) i. 

Bases of the ring of symmetric functions are indexed by partitions, and in particular, e_λ, m_λ, and s_λ are the elementary symmetric, monomial symmetric, and Schur functions respectively.
We also write F_σ(x) for the fundamental quasisymmetric function, where σ⊆{1,…, n-1} and 
F_σ(x) = ∑_i_1 ≤⋯≤ i_n 
 j∈σ⇒ i_j < i_j+1 x_i_1⋯ x_i_n.

A semistandard Young tableau (SSYT) is a filling of a partition λ using positive integers that weakly increase to the right and strictly increase upwards, and the set of such fillings is denoted SSYT(λ). When the entries are unbounded, there are infinitely many semistandard Young tableaux of a given shape, so it is sometimes useful to consider instead SSYT_m (λ), the set of SSYT of shape λ with entries at most m. We will engage in some typical abuse of notation by using these to also mean the number of semistandard Young tableaux in the set, and we repeat this abuse later when we define standard Young tableaux and quasi-Yamanouchi tableaux. SSYT_m (λ) is enumerated by Stanley's hook-content formula, which we reproduce below. 

 Given a partition λ, 

    SSYT_m (λ) = ∏_u∈λm+c(u)/h(u).






The weight of an SSYT T is wt(T) = (t_1,t_2,…), where t_i is the number of times that i appears, and given partitions λ,μ, the Kostka numbers K_λμ count the number of SSYT of shape λ and weight μ. 
A standard Young tableau (SYT) of shape λ with size n is a semistandard Young tableau of shape λ with weight (1^n), and the set of such fillings is denoted SYT(λ). Frame, Robinson, and Thrall counted standard fillings using the hook-length formula.

 Given a partition λ,

    SYT(λ) = n!/∏_u∈λ h(u).





The descent set for T∈SYT(λ) is Des(T) = { i ∈ [n-1]  |  i+1  is above  i}.
If we write the descent set as {d_1,d_2,…,d_k-1} in increasing order, then the first run of the tableau is the set of boxes that contain all the entries from 1 to d_1. For 1<i<k, the ith run is the set of boxes containing entries from d_i-1+1 to d_i, and the kth run starts at d_k+1 and ends at n. 




An SSYT is a quasi-Yamanouchi tableau (QYT) if when i appears in the tableau, some instance of i is in a higher row than some instance of i-1 for all i. We write QYT(λ) to denote the set of QYT of shape λ, QYT_≤ m(λ) to denote those with largest entry at most m, and QYT_=m(λ) to denote those with largest entry exactly m. As mentioned before, at times we will also write these to mean the number of objects in the set. 






It turns out that there is a nice bijection between QYT(λ) and SYT(λ) via the following destandardization map <cit.>. Given a tableau T∈SYT(λ), its destandardization is the SSYT constructed by changing the value of all entries in the ith run of T to i. It is easy to see that the resulting SSYT is also quasi-Yamanouchi and that this map has a well defined inverse, which we call standardization. By construction, it is clear that the map sents SYT with k runs to QYT with maximum value k-1. In this sense, the set {QYT_=m(λ)} refines SYT(λ) by number of descents, and we will often identify a QYT with its standardization. For further discussion on properties of QYT, see <cit.>.

As with permutations, we define the major index of a tableau T∈SYT(λ) to be maj(T) = ∑_i∈Des(T) i. We also have the charge statistic for standard Young tableaux: each entry i in T has a charge defined recursively, where ch(1) = 0, ch(i+1) = ch(i) if i ∉Des(T), ch(i+1) = ch(i) +1 if i ∈Des(T), and ch(T) = ∑_i=1^|λ| ch(i). 
For a quasi-Yamanouchi tableau, we define its descent set, major index, and charge statistic to be those of its standardization.




§ HIT NUMBER FORMULAS


Fix n ∈ℕ. A board B is a subset of [n]× [n], which we view as an n by n array of squares. In particular, a Ferrers board is a board composed of adjacent columns whose heights are weakly increasing from left to right. If λ is a partition of size n, then we can construct a Ferrers board B_λ as follows. Take the contents c_1,…,c_n of λ arranged in weakly decreasing order, then let the heights of the columns of B_λ be (c_i+i-1). Let B_λ× 1 be the board obtained by incrementing the height of every column by one. We note that it is always possible to do this once for any B_λ, as the construction never creates a column with height n. 
From the definitions, we get a relation between B_λ and B_λ'. 

Given a partition λ, the complement of B_λ× 1 is B_λ' up to rotation.





Given a permutation π∈ S_n, the graph of π is Γ(π) = { (i,π_i)  |  1 ≤ i ≤ n}, and the number of hits of π on B is |B∩Γ(π)|. We define the kth hit number h_k(B) to be the number of permutations in S_n which have exactly k hits on B.
Dworkin <cit.> gave a combinatorial interpretation of a q-analogue of hit numbers for Ferrers boards, which we use as the definition. For π∈ S_n, place a cross at each square in Γ(π), and for any square to the right of a cross, put a bullet. Then from each cross, draw circles going up and wrapping around the top edge of the [n]×[n] array, skipping over bullets, and stopping after hitting the top border of the Ferrers board. The q weight of π is the number of circles at the end of this process. The kth q-hit number T_k(B) is the sum of q weights over all permutations that hit the board exactly k times.



In <cit.>, two separate interpretations of the coefficients of the Schur expansion of the one row case of Jack polynomials are given. One is in terms of quasi-Yamanouchi tableaux, and the other is in terms of hit numbers. By comparing these interpretations, we get the following hit number formula for quasi-Yamanouchi tableaux.

Given a partition λ of n and 0≤ k ≤ n-1,

    QYT_=k+1(λ) = h_k(B_λ')/∏_u∈λ h(u).


In this section, we prove two q-analogues of this theorem, where the first weights each tableaux by its major index and the second by its charge. To do this, we use the theory of posets and (P,ω)-partitions, which were introduced by Stanley <cit.>. 


For a partition λ = (λ_1,…,λ_k), let P_λ be the subposet of ℕ×ℕ such that (i,j)∈ P_λ if 1≤ j ≤ k, 1≤ i≤λ_j. Given a poset P with n elements, a labeling ω is a map ω :P → [n]. It is called a natural labeling if it is order preserving and strict if it is order reversing. For P_λ, there are also column-strict labelings, which are strict on columns and natural on rows.





For a fixed ω, a (P,ω)-partition of size p is a map σ : P →ℕ_≥ 0 satisfying 

1) x≤ y ∈ P σ(x)≥σ(y), meaning σ is order reversing.

2) x < y ∈ P and ω(x)>ω(y) σ(x) > σ(y).

3) |σ| = ∑_x∈ Pσ(x) = p.

The values σ(x) are called the parts of σ, and a (P,ω;m)-partition is a (P,ω)-partition with largest part at most m. 𝒜(P,ω) denotes the set of (P,ω)-partitions, and 𝒜(P,ω;m) denotes the set of (P,ω;m)-partitions, which have generating function

    U_m(P,ω;m) = ∑_σ∈𝒜(P,ω;m) q^|σ|.

The ω-separator ℒ(P,ω) is the set of permutations in S_n of the form ω(x_i_1),…,ω(x_i_n) where x_i_1<…<x_i_n forms a linear extension of P. For each 0≤ k≤ n-1, define

    W_k(P,ω) = W_k(P,ω;q) = ∑_π q^maj(π),

where the sum is over all π∈ℒ(P,ω) with des(π) = k. 






 §.§ Major index formula

Fix a partition λ, and let ω be a column-strict labeling on P_λ. By Proposition 21.3 of <cit.>,

    U_m(P_λ,ω;m) = q^n(λ)∏_u∈λ[m+c(u)+1]/[h(u)].

By the definition of W_k(P_λ,ω), when ω is column-strict,

    W_k(P_λ,ω) = ∑_T∈QYT_=k+1(λ) q^maj(T).

Proposition 8.2 of <cit.> gives

    U_m(P_λ,ω) = ∑_k=0^n-1m+n-k n W_k(P_λ,ω).

Then since there is no restriction on m, it follows that

    ∑_k=0^n-1x+n-k n W_k(P_λ,ω) = q^n(λ)∏_u∈λ[x+c(u)+1]/[h(u)].

We then apply to the right hand side the following q-analogue <cit.> of the Goldman, Joichi, Write identity <cit.> 

    ∏_i=1^n [x+b_i -i +1] = ∑_k=0^n x+k n T_k(B),

where B is a Ferrers board with column heights b_i. Comparing coefficients of x+k n gives the following theorem.

Given a partition λ and 0≤ k ≤ n-1,

    ∑_T∈QYT_=k+1(λ) q^maj(T) = q^n(λ)/∏_u∈λ[h(u)]T_n-k(B_λ× 1).


Setting q=1 and applying Proposition <ref> recovers Theorem <ref>.
We note that since T_k(B) is Mahonian <cit.> for a Ferrers board, summing over k gives a nice (known) q-analogue of the hook-length formula,

    ∑_T∈SYT(λ) q^maj(T) = q^n(λ)[n]!/∏_u∈λ [h(u)].

We briefly attempted to prove Theorem <ref> bijectively but were unsuccessful. It would be nice to know what such a bijective algorithm might look like, and such an algorithm could be an interesting project to revisit in the future. 




 §.§ Charge formula

Fix a permutation λ of size n, and let ω be a column-strict labeling on P_λ. We write P_λ^* for the dual of P_λ and write ω^* for the labeling defined by ω^*(x_i) = n+1-ω(x_i) for all x_i∈ P_λ. 
Proposition 12.1 of <cit.> details what this dualization on P_λ and ω does to W_k, which is that

    W_k(P_λ^*,ω^*;q) = q^nk W_k(P_λ,ω;1/q).

We note that since there are k descents,

    q^nkW_k(P_λ,ω;1/q) = ∑_T∈QYT_=k+1(λ)q^nk-maj(T) = ∑_T∈QYT_=k+1(λ)∑_i∈Des(T) q^n-i.

Then since a descent at position i increments the charge value of the n-i remaining entries by one, we get

    W_k(P_λ^*,ω^*;q) = ∑_T∈QYT_=k+1(λ) q^ch(T).

Using the facts that [k]↦ [k]1/q^k-1 when substituting 1/q and that ∑_u∈λ h(u) = n + n(λ) + n(λ'), we get

    W_k(P_λ,ω;1/q) = q^n(λ')/∏_u∈λ [h(u)] T_n-k^*(B_λ× 1),

where T_k^*(B_λ× 1) gives a weight of 1/q to each circle instead of q. Multiplying this by q^n 2 changes the circles to a q^0 weight and empty squares to a q^1 weight, which is identical to drawing circles downwards instead of upwards from crosses and giving circles a q^1 weight. Then by Proposition <ref>, taking the complement of the board and reflecting vertically gives B_λ' up to column permutation. By Theorem 7.13 of <cit.>, T_k(B) is invariant on column permutations for Ferrers boards, so it follows that

    T_n-k^*(B_λ× 1) = T_k(B_λ')/q^n 2.

This gives the following result, which clearly reduces to Theorem <ref> when q=1. 
 
Given a partition λ and 0≤ k ≤ n-1,

    ∑_T∈QYT_=k+1(λ) q^ch(T) = q^nk+n(λ')-n 2/∏_u∈λ [h(u)] T_k(B_λ').


Summing over k in this case also gives some sort of q-analogue of the hook-length formula, although it does not appear to immediately give a nice form.



§ A SUMMATION FORMULA

We prove the following theorem in two ways, first with a q-hit number identity and then using (P,ω)-partitions. This gives a relatively clean enumeration for quasi-Yamanouchi tableaux compared to the product formula of <cit.>, the downside being that it is not a positive summation. 

Given a partition λ and 0≤ k ≤ n-1

    QYT_=k+1(λ) = ∑_m=0^kn+1 k-m(-1)^k-mSSYT_m+1(λ).





Setting t=n in equation (24) in <cit.> gives 

    T_n-k(B)/∏_i=1^n [d_i]! = ∑_m=0^k n+1  k-m (-1)^k-m q^k-m 2∏_i=1^nm+H_i-D_i + d_i  d_i,

where d_i =1 for all i, D_i = i, and H_i is the height of the ith column of B. By the way B_λ is constructed, the sequence H_i-D_i for B_λ×1 becomes exactly the cell contents of λ, so setting q=1 gives

    h_n-k(B_λ× 1) =∑_m=0^k n+1 k-m(-1)^k-m∏_i=1^n (m+c_i+1).

Substituting this into Theorem <ref> after applying Proposition <ref> and comparing with the hook-content formula proves Theorem <ref>.



When ω is a column-strict labeling on P_λ, 𝒜(P_λ,ω;m) is the set of SSYT_m+1(λ) with each entry decremented by one. Therefore, setting q=1 in U_m(P_λ,ω) gives |SSYT_m+1(λ)|. Proposition 8.4 in <cit.> says that

    W_k(P,ω) = ∑_m=0^k (-1)^m q^n 2n+1 m U_k-m(P,ω).

Then setting q=1, and reversing the order of summation proves Theorem <ref>.




§ THE POLYNOMIALS P_N,K


For any partition λ with |λ|=n, we can actually express QYT_=k+1(λ) in terms of certain symmetric functions P_n,k. We begin with Lemma 4 of <cit.>, where we set q=1, t=n, d_i=1, e_i ∈{0,1}, E_i the partial sums of the e_i, and D_i = i. We also recall as before that for B=B_λ× 1, we have H_i-D_i=c_i, the cell contents of λ in some order. After all of that, we get

    h_n-k(B_λ×1) = ∑_e_1+⋯+e_n = k∏_i=1^n c_i+E_i+d_i-e_i d_i-e_ii-1-c_i-E_i+e_i  e_i.

Since exactly one of d_i-e_i or e_i are 1 and the other is 0, we get

    h_n-k(B_λ×1) = ∑_e_1+⋯+e_n = k∏_i=1^n (c_i+E_i+1)^d_i-e_i(i-c_i-E_i)^e_i.

This is the same as summing over weighted lattice paths with n steps from (0,0) to (k,n-k). Let E_i count the cumulative east steps and N_i=i-E_i count the cumulative north steps. Then for each path, weight the ith step by x_i+E_i+1 if it is a north step and N_i-x_i if it is an east step, and let the weight of a path be the product of the weights of its steps.





Let P_n,k(x_1,…,x_n) denote the sum of the weights of all such paths. This gives the following weighted lattice path interpretation for QYT enumeration. 

Given a partition λ of n with contents c_1,…,c_n and 0≤ k≤ n,

    QYT_=k+1(λ) = P_n,k(c_1,…,c_n)/∏_u∈λh(u).


Such paths can be split recursively into ones that end on an east step and ones that end on a north step.

The polynomials P_n,k satisfy the relation

    P_n,k(x_1,…,x_n) = (x_n + k + 1) P_n-1,k(x_1,…,x_n-1) + (n-k-x_n)P_n-1,k-1(x_1,…,x_n-1).


We can use this to get a more concrete idea of what these polynomials look like. By their construction, it is not obvious that these polynomials are symmetric, but computing small cases seems to indicate they are.

    P_1,0(x_1) =    e_1(x_1)+1 
    
    P_1,1(x_1) =    e_1(x_1)
    
    P_2,0(x_1,x_2) =    e_2(x_1,x_2) + e_1(x_1,x_2) + 1
    
    P_2,1(x_1,x_2) =    -2e_2(x_1,x_2) -e_1(x_1,x_2) +1
    
    P_2,2(x_1,x_2) =    e_2(x_1,x_2)
    
    P_3,0(x_1,x_2,x_3) =    e_3(x_1,x_2,x_3) + e_2(x_1,x_2,x_3) + e_1(x_1,x_2,x_3) + 1
    
    P_3,1(x_1,x_2,x_3) =    -3e_3(x_1,x_2,x_3) -2 e_2(x_1,x_2,x_3) +4
    
    P_3,2(x_1,x_2,x_3) =    3e_3(x_1,x_2,x_3)+e_2(x_1,x_2,x_3)-e_1(x_1,x_2,x_3)+1
    
    P_3,3(x_1,x_2,x_3) =    e_3(x_1,x_2,x_3)


Let a(n,k,m) denote the coefficient of e_m in P_n,k, and assume that P_i,k is symmetric for i<n. Using the recursion, it is clear that the coefficient of the degree m monomials containing x_n in P_n,k is a(n-1,k,m-1) - a(n-1,k-1,m-1) and that the coefficient of the degree m monomials not containing x_n is (k+1)a(n-1,k,m)+(n-k)a(n-1,k-1,m). Then to show that P_n,k is symmetric, it is sufficient to show that a(n-1,k,m-1) - a(n-1,k-1,m-1)=(k+1)a(n-1,k,m)+(n-k)a(n-1,k-1,m), which can be done with a straightforward induction argument. 

Given a partition λ of n with contents c_1,…,c_n and 0≤ k ≤ n,

    QYT_=k+1(λ) = ∑_m=0^n a(n,k,m) e_m(c_1,…,c_n)/∏_u∈λh(u).



By the recursion and initial conditions, we have that a(n,k,0) is the Eulerian number A(n,k) and that for 1<m≤ n, it is easy to generate these coefficients recursively using the relation a(n,k,m) = a(n-1,k,m-1) - a(n-1,k-1,m-1). We also note that for a fixed value of n-m with varying n and k, this gives something close to a Pascal's triangle for the coefficients. Each term contributes its positive absolute value and its negative absolute value to the next line of the triangle, so summing over a line gives 0 except when m=0. Therefore, summing over P_n,k for all 0 ≤ k ≤ n leaves only the constant terms, and the hook-length formula is easily recovered.

