ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 21 (2021) #P2.03 / 201–217
https://doi.org/10.26493/1855-3974.2260.c0e
(Also available at http://amc-journal.eu)
A generalization of balanced tableaux and
marriage problems with unique solutions
Brian Tianyao Chan *
KeyFi, First Floor, First St. Vincent Bank Ltd. Building James Street, Kingstown,
St. Vincent and the Grenadines
Received 22 February 2020, accepted 24 February 2021, published online 30 September 2021
Abstract
We consider families of finite sets that we call flagged and that have been character-
ized by Chang as being the families of sets that admit unique solutions to Hall’s mar-
riage problem and we consider generalizations of Edelman and Greene’s balanced tableaux
previously investigated by Viard. In this paper, we introduce a natural generalization of
Edelman and Greene’s balanced tableaux that involves families of sets that satisfy Hall’s
marriage condition and certain words in [m]n, then prove that flagged families can be char-
acterized by a strong existence condition relating to this generalization. As a consequence
of this characterization, we show that the arithmetic mean of the sizes of subclasses of such
generalized tableaux is given by a generalization of the hook-length formula.
Keywords: Balanced tableaux, Hall’s marriage condition, shelling.
Math. Subj. Class. (2020): 05A20, 05C70, 05E45
1 Introduction
Hall’s Marriage Theorem is a combinatorial theorem proved by Hall [11] that asserts that
a finite family of sets has a transversal if and only if this family satisfies the marriage con-
dition. This theorem is known to be equivalent to at least six other theorems which include
Dilworth’s Theorem, Menger’s Theorem, and the Max-Flow Min-Cut Theorem [20]. Hall
Jr. proved [10] that Hall’s Marriage Theorem also holds for arbitrary families of finite sets,
where by arbitrary we mean families of finite sets that do not necessarily have a finite num-
ber of members. Afterwards, Chang [3] noted how Hall Jr.’s work in [10] can be used to
characterize marriage problems with unique solutions.
*The author would like to thank Stephanie van Willigenburg for her guidance and advice during the develop-
ment of this paper. Furthermore, the author gratefully acknowledges the insightful advice and feedback from the
anonymous referees. The author was supported in part by the Natural Sciences and Engineering Research Council
of Canada [funding reference number PGSD2 - 519022 - 2018]. https://sites.google.com/view/btchan
E-mail address: bchan600@gmail.com (Brian Tianyao Chan)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
202 Ars Math. Contemp. 21 (2021) #P2.03 / 201–217
Standard skew tableaux are well-known and intensively studied in algebraic combina-
torics, for example [15, 18, 19, 21]. Moreover, another class of tableaux was introduced by
Edelman and Greene in [5, 4], where they defined balanced tableaux on partition shapes.
In investigating the number of maximal chains in the weak Bruhat order of the symmet-
ric group, Edelman and Greene proved [5, 4] that the number of balanced tableaux of a
given partition shape equals the number of standard Young tableaux of that shape. Since
then, connections to random sorting networks [1], the Lascoux-Schützenberger tree [16],
and a generalization of balanced tableaux pertaining to Schubert polynomials [7] have been
explored.
In this paper we consider a new perspective for marriage problems with unique so-
lutions by interpreting such objects as shapes for generalized tableaux. Specifically we
call the families of finite sets that admit marriage problems with unique solutions flagged
and give a new characterization of these families of sets in Theorem 3.10. In this char-
acterization, we generalize standard skew tableaux and Edelman and Greene’s balanced
tableaux to families with systems of distinct representatives, we generalize hook sets to
members of such families, and we generalize bijective fillings of tableaux to certain words
in [m]n. We then use our characterization of marriage problems with unique solutions to
show in Theorem 3.25 that the arithmetic mean of the sizes of subclasses of such gener-
alized tableaux is given by a generalization of the hook-length formula. The hook-length
formula was discovered by Frame, Robinson, and Thrall and they proved that it enumerates
the number of standard Young tableaux of a given partition shape [8]. The formula consists
of parameters known as hook-lengths. Subsequent to Frame, Robinson and Thrall’s work,
hook-lengths have been shown to be connected to many known properties of tableaux.
They are integral, for instance, in work by Edelman and Greene on balanced tableaux [4]
and in results established by Morales, Pak, and Panova [17, 18]. Properties of Edelman
and Greene’s balanced tableaux and related notions are of interest [6, 7]. Moreover, gen-
eralizations of balanced tableaux were investigated by Viard. In [24, 23], Viard proved
what is equivalent to the following which we state using the terminology in this paper.
If F is a flagged family, if t is a transversal of F , and if f is a configuration of t, then
there exists a permutation σ that satisfies f . Moreover, Viard proved [24] what is equiv-
alent to the following which we also state using the terminology in this paper. Let S
be a finite subset of N2 and let F be the family of hooks {H(i,j) : (i, j) ∈ S} where
H(i,j) = {(i, j)} ∪ {(i, j′) ∈ S : j′ > j} ∪ {(i′, j) ∈ S : i′ > i}. Furthermore, let t be
the transversal of F defined by t(H(i,j)) = (i, j) for all (i, j) ∈ S. Then the average value
of An,n(f) over all configurations f of t satisfying An,n(f) ≥ 1 is given by the hook-
length formula n!/
∏
(i,j)∈S h(i,j) where h(i,j) = |H(i,j)| for all (i, j) ∈ S. Afterwards,
we indicate how our generalization of standard skew tableaux and balanced tableaux can
be analysed using Naruse’s Formula for skew tableaux and how such an approach can be
extended to skew shifted shapes [9, 17, 19] and likely to certain d-complete posets [9, 19].
2 Preliminaries
Throughout this paper, let N denote the set of positive integers and for all n ∈ N, define
[n] = {1, 2, . . . , n}. For all X ′ ⊆ X , let the restriction of f to X ′, which we denote by
f |X′ , be the function g : X ′ → Y defined by g(r) = f(r) for all r ∈ X ′. For all m,n ∈ N,
say that a function f : [n] → [m] is order-preserving if for all 1 ≤ i ≤ j ≤ n, f(i) ≤
f(j). Lastly, we write examples of permutations using one-line notation. When describing
B. T. Chan: A generalization of balanced tableaux and marriage problems with . . . 203
families of sets, call F ∈ F a member of F . We treat families of sets as multisets, so the
members of F are counted with multiplicity. That is, |F| = |I| if F = {Fi : i ∈ I}.
An illustrative class of examples that we use in this paper will come from skew shapes.
Hence, we recall them below and describe the notation we will use. A partition λ is a
weakly decreasing sequence of positive integers. We write λ = (λ1, λ2, . . . , λℓ) to denote
such a partition, where λi ∈ N for all 1 ≤ i ≤ ℓ. If λ is a partition, then we will also rep-
resent it as a Young diagram, which we also denote by λ. Specifically, the Young diagram
of λ = (λ1, λ2, . . . , λℓ) is a subset of N2 defined by
ℓ⋃
i=1
{(i, j) : 1 ≤ j ≤ λi}.
Moreover, if λ and µ are Young diagrams such that µ ⊂ λ, then define a skew shape λ/µ
to be the set λ\µ. We also consider a Young diagram λ as the skew shape λ/µ where µ
is the empty partition. We use the English convention for depicting Young diagrams and
skew shapes. In order to follow this convention, we call the elements of λ/µ the cells of
λ/µ, the non-empty subsets of the form {(i′, j′) ∈ λ/µ : i′ = i} the rows of λ/µ, and the
non-empty subsets of the form {(i′, j′) ∈ λ/µ : j′ = j} the columns of λ/µ.
3 Flagged families of sets and words in [m]n
We investigate families of sets that satisfy Hall’s marriage condition and generalizations of
Edelman and Greene’s balanced tableaux by proving relationships between these classes of
structures. In Section 3.1, we introduce marriage problems with unique solutions as flagged
families and generalizations of balanced tableaux, then we give a new characterization of
marriage problems with unique solutions in terms of these tableaux. In Section 3.2, we
explain how our results relate to tableaux on skew shapes. Lastly, in Section 3.3, we show
that the arithmetic mean of the sizes of subclasses of the above generalized tableaux is
given by a generalization of the hook-length formula.
3.1 A new characterization
A well-known notion for families of sets is the following.
Definition 3.1 (Folklore [14]). Let n ∈ N, and let F be a finite family of subsets of [n].
Then a transversal of F is an injective function t : F → [n] such that t(F ) ∈ F for all
F ∈ F . The set {t(F ) : F ∈ F} is called a system of distinct representatives of F .
Families of sets that have transversals are of great interest. Exemplary of this is Hall’s
Marriage Theorem, which we present below.
Definition 3.2 (Marriage condition, Hall [11]). Let n ∈ N, and let F be a finite family of
subsets of [n]. Then F satisfies the marriage condition if for all subfamilies F ′ of F ,
|F ′| ≤
∣∣∣∣ ⋃
F∈F ′
F
∣∣∣∣.
Theorem 3.3 (Marriage Theorem, Hall [11]). Let n ∈ N, and let F be a family of non-
empty subsets of [n]. Then F has a transversal if and only if F satisfies the marriage
condition.
204 Ars Math. Contemp. 21 (2021) #P2.03 / 201–217
In order to meaningfully use the families of sets in Hall’s Marriage Theorem, we will
define more structure on them.
Definition 3.4. Let n ∈ N, let F be a family of non-empty subsets of [n], and let t be a
transversal of F . Then a configuration f of t is a function f : [n] → N such that for all
F ∈ F ,
f(t(F )) ≤ |F |.
Moreover, for m ∈ [n], a surjective map σ : [n] → [m] satisfies f if for all F ∈ F , the
positive integer σ(t(F )) is the kth smallest element of the set σ(F ), where k = f(t(F )).
Example 3.5. Let F = {F1, F2} be a family of sets on [2] where F1 = [2] and F2 = [2].
The injective function t : F → [2] defined by t(F1) = 1 and t(F2) = 2 is a transversal of
F . Consider three configurations f ′, f ′′, and f ′′′ of t defined by f ′(1) = 1 and f ′(2) = 1,
f ′′(1) = 1 and f ′′(2) = 2, and f ′′′(1) = 2 and f ′′′(2) = 2.
Note σ : [2] → [1] satisfies f ′ because σ(1) = 1 is the smallest element of σ(F1) =
σ([2]) = [1] and because σ(2) = 1 is the smallest element of σ(F2) = σ([2]) = [1]. How-
ever, no permutation σ : [2] → [2] can satisfy f ′. It can also be checked that the surjective
map σ : [2] → [1] and the permutation σ = 21 do not satisfy f ′′ but the permutation
σ = 12 satisfies f ′′. Moreover, for all m ∈ [2] and for all surjective maps σ : [2] → [m], σ
does not satisfy f ′′′.
Now, we define the following stronger form of the marriage condition.
Definition 3.6 (cf. [3]). Let n ∈ N, let F be a finite family of subsets of [n], and write
m = |F|. Then F is flagged if there exists a bijection σF : [m] → F such that for all
k ∈ [m], ∣∣∣∣ k⋃
i=1
σF (i)
∣∣∣∣ = k. (3.1)
Informally, σF maps each k to a subset, such that the union of the first k subsets has
cardinality k.
In [3], Chang noted the following as a simple consequence of Hall Jr.’s work ([10],
Theorem 2).
Proposition 3.7 (Chang [3]). If n ∈ N, then a finite family F of subsets of [n] has exactly
one transversal if and only if F is flagged.
In particular, by Theorem 3.3, all flagged families satisfy the marriage condition. The
families of sets F in Proposition 3.7 are referred to as marriage problems with unique
solutions [13, 12].
Remark 3.8. When describing a flagged family F , we will use total orderings on the
members of this family by fixing orderings F1, F2, . . . , Fn of the members of F that
satisfy
F = {Fi : 1 ≤ i ≤ n},
and, for all 1 ≤ k ≤ n, ∣∣∣∣ k⋃
i=1
Fi
∣∣∣∣ = k.
B. T. Chan: A generalization of balanced tableaux and marriage problems with . . . 205
We observe that no flagged family is a multi-set. Let F be a flagged family and fix an
ordering F1, F2, · · · , Fn of the members of F as described in Remark 3.8. Suppose that
Fj = Fj′ for some j < j′. Then,
j⋃
i=1
Fi =
j′⋃
i=1
Fi,
contradicting Equation (3.1) of Definition 3.6.
Before proving the main result of this paper, we prove the following lemma.
Lemma 3.9. Let F be a flagged family of subsets of [n]. Moreover, let S ⊆ [n] be the set
of elements k ∈ [n] such that k ∈ F for exactly one member F of F . Then S is not empty.
Proof. Let m = |F|. Because F is flagged, Definition 3.6 and Equation (3.1) imply that
there exists a bijection σF : [m] → F and an element k ∈ [n] such that
m−1⋃
i=1
σF (i) =
( m⋃
i=1
σF (i)
)
\{k}.
So as k ∈ σF (m) and as, for all 1 ≤ i < m, k /∈ σF (i), it follows that k ∈ S and that S is
non-empty.
Now, we prove the main result of this paper.
Theorem 3.10. Let n ∈ N, let F be a family of subsets of [n] such that |F| = n, assume
that F satisfies the marriage condition, and let t be a transversal of F . Moreover, let
S ⊆ [n] be the set of elements k ∈ [n] such that k ∈ F for exactly one member F of F .
Lastly, let m be an integer satisfying
min(n, n− |S|+ 1) ≤ m ≤ n.
Then F is flagged if and only if for all configurations f of t, there exists a surjective map
σ : [n] → [m] such that σ satisfies f .
Proof. Let n, F , t, S, and m be as described in the theorem. First assume that for all
configurations f of t, there exists a surjective map σ : [n] → [m] that satisfies f . If n = 1,
then the only family of {1} with a transversal is the family F = {{1}}, which is flagged.
So assume without loss of generality that n ≥ 2. Consider the configuration f1 of t
defined by f1(t(F )) = |F | for all F ∈ F . By assumption, there exists a surjective map
σ′ : [n] → [m] that satisfies f1. Moreover, let k ∈ [n − 1], and assume that we can fix an
ordering F = {F ′i : i ∈ [n]} of F so that the following holds for all integers 0 ≤ j ≤ k−1.∣∣∣∣ n−j⋃
i=1
F ′i
∣∣∣∣ = n− j (3.2)
Note that Equation (3.2) holds if k = 1 because the fact that F has a transversal implies
that
⋃
F∈F F = [n].
Next, let 1 ≤ s ≤ n− k + 1 satisfy
σ′(t(F ′s)) = max
1≤j≤n−k+1
σ′(t(F ′j)). (3.3)
206 Ars Math. Contemp. 21 (2021) #P2.03 / 201–217
Suppose that there exists an element j ∈ [n] such that 1 ≤ j ≤ n − k + 1, j ̸= s,
and t(F ′s) ∈ F ′j . By Equation (3.3), σ′(t(F ′j)) ≤ σ′(t(F ′s)). So as t(F ′s) ∈ F ′j and
t(F ′s) ̸= t(F ′j), it follows that for some 1 ≤ ℓ ≤ |F ′j | − 1, σ′(t(F ′j)) is an ℓth smallest
element of σ′(F ′j). But then, as f1(t(F
′
j)) = |F ′j |, σ′ does not satisfy f1, contradicting the
assumption that σ′ satisfies f1.
Hence, t(F ′s) /∈ F ′i for all 1 ≤ i ≤ n − k + 1 satisfying i ̸= s. In particular, fix an
ordering F = {F ′′i : i ∈ [n]} of the members of F so that F ′′i = F ′i if i > n− k + 1 and
F ′′n−k+1 = F
′
s, where s is as described in the above paragraph. By Equation (3.2) and the
fact that t(F ′s) /∈ F ′i for all 1 ≤ i ≤ n− k+1 satisfying i ̸= s, it follows that this ordering
of the members of F satisfies the following equation for all integers 0 ≤ j ≤ k.∣∣∣∣ n−j⋃
i=1
F ′′i
∣∣∣∣ = n− j
As the choice of k ∈ [n − 1] is arbitrary, it follows that there exists an ordering F =
{F1, F2, . . . , Fn} of F such that ∣∣∣∣ k⋃
i=1
Fi
∣∣∣∣ = k
for all 1 ≤ k ≤ n. Hence, F satisfies Equation (3.1) of Definition 3.6. So, by Defini-
tion 3.6, F is flagged.
Next, assume that F is flagged. We proceed by strong induction on n. Because F is
flagged, we will use the total orderings as described in Remark 3.8 to describe the members
of this family.
If n = 1, then the only family of subsets of {1} with a transversal is the family F =
{{1}}. Moreover, with t being the transversal of F defined by mapping {1} to 1, the
only configuration f of t is the function f : {1} → N defined by f(1) = 1, S = {1},
min(n, n− |S|+ 1) = 1, and the surjective map σ : {1} → {1} satisfies f .
So assume that n ≥ 2 and let f be a configuration of t. Since S is not empty by
Lemma 3.9, min(n, n − |S| + 1) = n − |S| + 1, implying that n − |S| + 1 ≤ m ≤ n.
Assume without loss of generality that
S = {n−m′ + 1, n−m′ + 2, . . . , n} (3.4)
for some m′ ∈ [n]. If m = 1, then n − |S| + 1 ≤ 1, implying that n = |S|. Hence, as
|F| = n and S = [n], every element of [n] is contained in exactly one element of F , that is
F = {{k} : k ∈ [n]}. So in this case, t({k}) = k for all k ∈ [n], the only configuration f
of t is the map defined by f(k) = 1 for all k ∈ [n], and the surjective map σ : [n] → [m],
defined by σ(k) = 1 for all k ∈ [n], satisfies f . So assume without loss of generality that
m ≥ 2.
Since n− |S|+ 1 ≤ m ≤ n, m satisfies the inequality n−m′ + 1 ≤ m ≤ n. As F is
flagged, there is an ordering F ′1, F
′
2, . . . , F
′
n of the members of F such that∣∣∣∣ k⋃
i=1
F ′i
∣∣∣∣ = k (3.5)
for all 1 ≤ k ≤ n. Define the following subfamilies of F ,
F0 = {F ∈ F : t(F ) ≤ m− 1}
B. T. Chan: A generalization of balanced tableaux and marriage problems with . . . 207
and
F1 = {F ∈ F : t(F ) ≥ m}.
We first prove that F0 is flagged. Because S is the set of elements k ∈ [n] such that
k ∈ F for exactly one member F of F , Equation (3.4) and the fact that n−m′+1 ≤ m ≤ n
implies that for all m ≤ k ≤ n, k is contained in exactly one member of F and that for all
F ∈ F1,
|F ∩ {m,m+ 1, . . . , n}| = 1.
In particular, F0 is an (m− 1)-member family of subsets of [m− 1].
Assume that there exists an integer 1 ≤ j ≤ n− 1 such that F ′j ∈ F1 and F ′j+1 ∈ F0.
Write
Xj =
j−1⋃
i=1
F ′i ,
where we assume that Xj = ∅ if j = 1. Since F ′j ∈ F1, t(F ′j) ∈ {m,m + 1, . . . , n} and
no member of F other than F ′j contains t(F ′j). Moreover, by Equation (3.5), |F ′j ∪Xj | =
|Xj | + 1. So as t(F ′j) ∈ F ′j , it follows that [m − 1] ∩ (F ′j ∪Xj) = [m − 1] ∩Xj . Since
F ′j+1 ∈ F0, F ′j+1 ⊆ [m−1]. Moreover, by Equation (3.5), |Xj∪F ′j∪F ′j+1| = |Xj∪F ′j |+1.
It follows that F ′j+1\Xj = F ′j+1\(Xj ∪ F ′j) = {k} for some k ∈ [m− 1], implying that
|F ′j+1 ∪Xj | = |Xj |+ 1. (3.6)
So the ordering F = {F ′′1 , F ′′2 , . . . , F ′′n } of the members of F , such that F ′′j = F ′j+1,
F ′′j+1 = F
′
j , and F
′′
i = F
′
i for all i ∈ [n]\{j, j+1}, satisfies the following by Equation (3.5)
and Equation (3.6). For all 1 ≤ k ≤ n,∣∣∣∣ k⋃
i=1
F ′′i
∣∣∣∣ = k. (3.7)
Furthermore, F ′′j ∈ F0 and F ′′j+1 ∈ F1. If there exists an integer 1 ≤ j′ ≤ n− 1 such that
F ′′j′ ∈ F1 and F ′′j′+1 ∈ F0, then argue again as above. Repeating this argument at most a
finite number of times, we obtain an ordering F = {F1, F2, . . . , Fn} of the members of F
where ∣∣∣∣ k⋃
i=1
Fi
∣∣∣∣ = k (3.8)
for all 1 ≤ k ≤ n, F0 = {Fk : 1 ≤ k ≤ m − 1}, and F1 = {Fk : m ≤ k ≤ n}.
In particular, Equation (3.8) holds for all 1 ≤ k ≤ m − 1, implying that F0 satisfies
Equation (3.1) of Definition 3.6. It follows, by Definition 3.6, that F0 is a flagged family
of subsets of [m− 1].
So consider the ordering F1, F2, . . . , Fn of the members of F as above and assume
without loss of generality that for all m ≤ i ≤ n, t(Fi) = i. Let t′ be the transversal of
F0 defined by t′(F ) = t(F ) for all F ∈ F0. Moreover, let f ′ = f |[m−1], where f |[m−1]
denotes the restriction of f to [m− 1]. In particular, f ′ is a configuration of t′.
Since it is assumed in the theorem that min(n, n − |S| + 1) ≤ m ≤ n, and since a
surjective map σ : [n] → [m] is a permutation if m = n, the following holds. Because F0
is flagged, because |F0| = m − 1, and because |[m − 1]| < n, the induction hypothesis
implies that there exists a permutation σ′ : [m− 1] → [m− 1] such that σ′ satisfies f ′.
208 Ars Math. Contemp. 21 (2021) #P2.03 / 201–217
If there exists an integer m ≤ j ≤ n such that f(j) = |Fj |, then there exists a surjective
map κ′ : [n] → [m] such that κ′(i) = i for all 1 ≤ i ≤ m − 1 and the following two
properties hold for all m ≤ i ≤ n.
• If f(i) = |Fi|, then κ′(i) = m.
• If f(i) < |Fi|, then κ′(i) is equal to the f(i)th smallest element of σ′(Fi\{i}).
Otherwise, if f(i) < |Fi| for all m ≤ i ≤ n, the following holds. Write σ′(Fn\{n}) =
{r1, r2, · · · , rt} where t = |Fn| − 1 and r1 < r2 < · · · < rt. Since f(n) < |Fn|, there
exists a map κ∗ : [m − 1] → [m] such that κ∗ is injective and order-preserving and such
that, with x ∈ [m]\κ∗([m−1]), x < κ∗(r1) if f(n) = 1 and κ∗(rf(n)−1) < x < κ∗(rf(n))
if f(n) ≥ 2. So there exists a surjective map κ′′ : [n] → [m] such that κ′′|[m−1] = κ∗ and
such that the following two properties hold.
• If m ≤ i < n, then κ′′(i) is equal to the f(i)th smallest element of κ′′(σ′(Fi\{i})).
• If i = n, then κ′′(i) /∈ κ′′([m− 1]) and κ′′(i) is equal to the f(i)th smallest element
of κ′′(i) ∪ κ′′(σ′(Fi\{i})).
We note that κ′′|[m−1] is injective and order-preserving because κ∗ is injective and
order-preserving.
So define a surjective map κ : [n] → [m] as follows. If there exists an integer m ≤ j ≤
n such that f(j) = |Fj |, then define κ = κ′. Otherwise, if f(i) < |Fi| for all m ≤ i ≤ n,
define κ = κ′′. Now, define the map σ : [n] → [m] by
σ(i) =
{
κ(σ′(i)) if 1 ≤ i ≤ m− 1
κ(i) if m ≤ i ≤ n.
Because σ′ : [m−1] → [m−1] is a bijection, the definition of κ implies that σ is surjective.
Moreover, because σ′ satisfies f ′ and because, for all integers m ≤ i ≤ n, i is contained in
exactly one member of F and Fi ∩ {m,m + 1, . . . , n} = {i}, the definition of κ and the
definition of σ imply that σ satisfies f . From this, the theorem follows.
A natural consequence of the above is the following which, combined with Theo-
rem 3.10, gives another characterization of flagged families of sets.
Corollary 3.11. Let F be a family of subsets of [n] such that |F| = n, assume that F
satisfies the marriage condition, and let t be a transversal of F . Moreover, let S be as
in Theorem 3.10. Lastly, let f0 be the configuration of t defined by f0(t(F )) = 1 for all
F ∈ F . Then f0 is satisfied by some permutation σ : [n] → [n] if and only if for all
integers n − |S| + 1 ≤ m ≤ n and for all configurations f of t, there exists a surjective
map σ : [n] → [m] that satisfies f .
Proof. Let f1 be the configuration of t defined by f1(t(F )) = |F | for all F ∈ F . Then
a permutation σ : [n] → [n] satisfies f0 if and only if the permutation σ′ : [n] → [n]
defined by σ′(i) = n− σ(i) + 1 for all i ∈ [n] satisfies f1. In particular, f0 is satisfied by
some permutation if and only if f1 is. The first half of the proof of Theorem 3.10 implies
that if f1 is satisfied by some permutation σ : [n] → [n], then F is flagged. Furthermore,
by Theorem 3.10, if F is flagged, then for all integers n − |S| + 1 ≤ m ≤ n and for all
configurations f of t, there exists a surjective map σ : [n] → [m] that satisfies f . From
this, the corollary follows.
B. T. Chan: A generalization of balanced tableaux and marriage problems with . . . 209
Remark 3.12. A family F of subsets of [n] such that |
⋃
F∈F F | = |F| = n is called
a critical block in [10] by Hall Jr.. He used this notion as a very important ingredient in
extending Hall’s Marriage Theorem to infinite families of finite sets.
3.2 The case of skew shapes
To explain how the results in the previous subsection relate to skew shapes, we will need
the following definitions.
Definition 3.13. Let λ/µ be a skew shape with n cells, and let 1 ≤ m ≤ n be an integer.
Then a surjective tableau of shape λ/µ is a surjective function T : λ/µ → [m] and ele-
ments in the range of T are called the entries in T . In the case m = n a surjective tableau is
a bijective tableau. Moreover, a standard skew tableau of shape λ/µ is a bijective tableau
of shape λ/µ such that the entries along every row increase from left to right and the entries
along every column increase from top to bottom.
Example 3.14. The tableaux
T1 =
3 5
6 1 2
4
, T2 =
2 3
1 5 6
4
, and T3 = 2 3
3 1 2
2
have shape (4, 3, 1)/(2). Here, T1 and T2 are bijective and T2 is standard. All three are
surjective. Moreover, for T1 and T2, m = 6 and for T3, m = 3.
In order to fully relate Definition 3.13 to Definition 3.4, we will use the following
standard definitions.
Definition 3.15. Let λ/µ be a skew shape. For any cell (i, j) ∈ λ/µ, define the corre-
sponding hook H(i,j) to be
H(i,j) = {(i, j)} ∪A(i,j) ∪ L(i,j),
where
A(i,j) = {(i, j′) ∈ λ/µ : j′ > j}
is the arm of H(i,j) and where
L(i,j) = {(i′, j) ∈ λ/µ : i′ > i}
is the leg of H(i,j). Define the corresponding hook-length h(i,j) to be
h(i,j) = |H(i,j)|.
Example 3.16. Consider the following skew shape λ/µ, where λ = (5, 4, 3, 3) and µ =
(2, 2, 1). Then r = (2, 3) is the cell of λ/µ depicted below that is filled with a bullet. The
entries of Hr are filled with asterisks, bullets or circles, so hr = 4. Moreover, the entry of
Ar is filled with an asterisk and the entries of Lr are filled with circles.
• ∗
◦
◦
210 Ars Math. Contemp. 21 (2021) #P2.03 / 201–217
Definition 3.17. Let λ/µ be a skew shape. Then define Fλ/µ to be the set
{Hr : r ∈ λ/µ}.
Example 3.18. If λ/µ is the skew shape depicted below
,
then, as λ/µ = {(1, 2), (1, 3), (2, 2), (2, 3)},
Fλ/µ = {{(1, 2), (2, 2), (1, 3)}, {(1, 3)}, {(2, 1), (2, 2)}, {(2, 2)}}.
Many families of sets that satisfy the marriage condition are not flagged. For instance,
the family F = {F1, F2}, where F1 = F2 = {1, 2}, satisfies the marriage condition but is
not flagged. However, Definition 3.6 is a very broad definition. Let λ be a Young diagram.
Then an inner corner of λ is a cell r ∈ λ such that deleting r from λ results in another
Young diagram. For instance, if λ = (4, 2, 2), then the inner corners of λ are the cells filled
with bullets.
•
•
With this definition in mind, let λ/µ be a skew shape with n cells, and consider the family
F of sets defined by F = Fλ/µ. Let r1, r2, . . . , rn be a sequence of cells in λ/µ such that:
• The cell r1 is an inner corner of λ.
• For all k ∈ [n− 1], the cell rk+1 is an inner corner of λ\{r1, r2, · · · , rk}.
Define σF : [n] → F by letting σF (k) = Hrk for all k ∈ [n]. It can be checked that
the bijection σF satisfies Equation (3.1). Now, because the skew shape λ/µ is a finite
set, regard λ/µ as being the set [n], where n is the number of cells in λ/µ. In particular,
regard Fλ/µ as a family of subsets of [n]. Then, by the above and by Definition 3.6,
F is flagged. In particular, by Proposition 3.7, F has a unique transversal. The unique
transversal tλ/µ : F → λ/µ of F is given by tλ/µ(Hr) = r for all r ∈ λ/µ.
As we are regarding the cells of a skew shape with n cells as being the elements of
[n], we can regard any surjective tableau T of shape λ/µ as being a surjective function
T : [n] → [m] in which T (i) = j if j is the entry of T in the cell of T corresponding
to i. Taking m = n, we can also regard any bijective tableau of shape λ/µ as being a
permutation T : [n] → [n]. Lastly, as we are regarding the skew shape λ/µ as being the
set [n] and as we are regarding Fλ/µ as a family of subsets of [n], we define configurations
f : λ/µ → N of tλ/µ, where tλ/µ is the unique transversal of Fλ/µ, and surjective maps
σ : λ/µ → [m] that satisfy f analogously to Definition 3.4.
Next, let λ/µ be a skew shape with n cells, consider the flagged family of sets Fλ/µ,
and let tλ/µ be the unique transversal of F . We define the configuration f0 of tλ/µ by
f0(r) = 1 for all r ∈ λ/µ. It can be seen that the standard skew tableaux of shape λ/µ
are the bijective tableaux of shape λ/µ that satisfy f0. Since we regard λ/µ as being the
set [n], we can regard f0 as being the function f0 : [n] → N defined by f0(k) = 1 for
B. T. Chan: A generalization of balanced tableaux and marriage problems with . . . 211
all k ∈ [n]. So as we regard Fλ/µ as being a family of subsets of [n], the standard skew
tableaux of shape λ/µ can be regarded as being the permutations σ : [n] → [n] that satisfy
f0.
Example 3.19. Consider the following surjective tableau of shape λ = (4, 3, 2).
1 2 3 3
1 2 3
3 3
Next, consider Fλ. Let tλ be the unique transversal of Fλ, and let f : λ → N be the
configuration of tλ defined by f(r) = 1 for all r ∈ λ/µ. It can be checked that the above
tableau satisfies f .
Edelman and Greene introduced the following class of bijective tableaux, which we
re-formulate in terms of the configurations we defined in this paper.
Definition 3.20 (Edelman and Greene [5]). Let λ be a Young diagram containing n cells.
Moreover, let tλ be the transversal of Fλ defined by tλ(Hr) = r for all r ∈ λ and let f be
the configuration defined by
f(r) = |Lr|+ 1
for all r ∈ λ. Then a balanced tableau of shape λ is a bijective tableau of shape λ that
satisfies f .
Example 3.21. Let λ = (4, 3, 2), and let tλ and f be defined from Fλ as described in
Definition 3.20. Then
T = 4 5 8 3
6 7 9
1 2
is balanced because T satisfies f . For instance, f((2, 1)) = 2 since L(2,1) = {(3, 1)} and
|Lr| + 1 = 2. So as T ((2, 1)) = 6, H(2,1) = {(2, 1), (2, 2), (2, 3), (3, 1)}, and the set of
entries in T that are contained in a cell of H(2,1) is {1, 6, 7, 9}, it follows that T ((2, 1)) is
the f((2, 1))th-smallest element of {1, 6, 7, 9}.
Remark 3.22. The surjective tableaux from Definition 3.13 that satisfy the configuration
f : [n] → N defined by f(k) = 1 for all k ∈ [n] do not correspond to semistandard
tableaux, nor do they correspond to the semistandard balanced labelings in [7].
Balanced tableaux can be regarded as permutations σ : [n] → [n] that satisfy f(r) =
|Lr| + 1. The function f(r) = |Lr| + 1 was called the hook rank of r by Edelman and
Greene and they used it to define balanced tableaux [5].
Lastly, we give examples illustrating Theorem 3.10 and Corollary 3.11.
Example 3.23. We give an example in which the lower bound min(n, n − |S| + 1) from
Theorem 3.10 cannot be improved on. Consider λ = (3, 2, 1). Next, let F = Fλ and let
t be the unique transversal of F . As discussed earlier, F is flagged. Now, let f be the
configuration of Fλ defined by f((1, 1)) = 5, f((1, 2)) = 3, f((1, 3)) = 1, f((2, 1)) = 3,
f((2, 2)) = 1, and f((3, 1)) = 1. We depict the configuration f with the below diagram.
212 Ars Math. Contemp. 21 (2021) #P2.03 / 201–217
5 3 1
3 1
1
There is exactly one cell in the Young diagram λ, the cell (1, 1), that is contained in
exactly one member of F = {Hr : r ∈ λ}. Hence, S = {(1, 1)} and min(n, n−|S|+1) =
n− |S|+1. With this in mind, set n = 6 and, as n− |S|+1 = 6− 1+1 = 6, assume that
m is an integer satisfying 1 ≤ m ≤ 5. Suppose that there exists a surjective tableau T of
shape λ, and with entries from [m], such that T satisfies the configuration f defined above.
The cells (1, 1), (1, 2) and (2, 1) are cells r ∈ λ that satisfy f(r) = hr. Moreover, because
T satisfies f , f(r) = hr implies that no two entries of T in Hr are the same and that the
entry of T in cell r is the hthr smallest element of the set of entries of T that are contained
in Hr.
So consider the cell (2, 2) of λ. Since m ≤ 5, some two entries of T in H(1,1) are the
same, or the entry of T in cell (2, 2) equals to the entry of T in some other cell, (i1, j1), in
λ. Since f((1, 1)) = 5 = h(1,1), no two entries of T in H(1,1) are the same. So the entry of
T in cell (2, 2) equals to the entry of T in some other cell, (i1, j1), in λ. If (i1, j1) = (1, 1),
then the entry of T in cell (2, 2) of λ is larger than the entries of T in cells (1, 2) and (2, 1)
of λ. But that is impossible by the above. If (i1, j1) = (2, 1) or if (i1, j1) = (3, 1), then
the entry of T in cell (2, 1) of λ is the kth smallest element of the set of entries of T that
are contained in H(2,1) for some k ≤ 2. But that is impossible by the above. By symmetry,
it is impossible for (i1, j1) = (1, 2) or for (i1, j1) = (1, 3). Hence, we have reached a
contradiction. It follows that there is no such surjective tableau T .
Example 3.24. Consider a skew shape λ/µ with n cells, and let S denote the set of cells
of λ/µ that are contained in exactly one member of {Hr : r ∈ λ/µ}. The elements of S
are also known as the outer corners of µ. Clearly, there exists a standard skew tableau of
shape λ/µ. Corollary 3.11 implies that such a tableau exists if and only if for all integers
n− |S|+ 1 ≤ m ≤ n and for all configurations f of λ/µ, there exists a surjective tableau
T of shape λ/µ, with [m] as the set of entries of T , such that T satisfies f .
3.3 The average number of generalized tableaux
Let S(n,m) denote the Stirling number of the second kind, namely the number of set
partitions of [n] into m parts. Let F be a family of subsets of [n] that satisfies the marriage
condition, let m ∈ [n], and let t be a transversal of F . If f is a configuration of t, then let
An,m(f) denote the number of surjective maps σ : [n] → [m] that satisfy f . Moreover,
let X be the set of configurations f of t such that An,m(f) ≥ 1. Then define the average
value of An,m(f) over all configurations f of t satisfying An,m(f) ≥ 1 to be
1
|X|
∑
f∈X
An,m(f)
if |X| > 0, and 0 otherwise.
Theorem 3.25. Let F be a flagged family of subsets of [n] such that |F| = n and let t be
the transversal of F . Moreover, let S ⊆ [n] be the set of elements k ∈ [n] such that k ∈ F
for exactly one member F of F , and let m be an integer satisfying
n− |S|+ 1 ≤ m ≤ n.
B. T. Chan: A generalization of balanced tableaux and marriage problems with . . . 213
Then the average value of An,m(f) over all configurations f of t satisfying
An,m(f) ≥ 1
is
m!S(n,m)∏
F∈F |F |
. (3.9)
Remark 3.26. Consider the sequence (pk(x))k=0,1,2,... of polynomials in Q[x] such that
p0(x) = 1 and, for all k,
pk+1(x)− pk+1(x− 1) = x pk(x).
If k = n−m, then S(n,m) = pk(m) (see [2, 22]). So if k is fixed, then we can compute
closed-form expressions for S(n,m). For instance, Expression 3.9 becomes
m!∏
F∈F |F |
if n = m, (
m+ 1
2
)
m!∏
F∈F |F |
if n = m+ 1, and
1
2
(
m+ 1
2
)((
m+ 1
2
)
+
2m+ 1
3
)
m!∏
F∈F |F |
if n = m+ 2.
In order to prove Theorem 3.25, we prove the following.
Lemma 3.27. Let m,n ∈ N such that m ≤ n, and let F be a family of subsets of [n]
that has a transversal t : F → [n] such that t is surjective. Then every surjective function
σ : [n] → [m] satisfies exactly one configuration f of t.
Proof. Let σ : [n] → [m] be a surjective map. Then σ satisfies the configuration f of t
defined by letting, for all F ∈ F , f(t(F )) = k where σ(t(F )) is the kth smallest element
of the set σ(F ). Now, suppose that σ satisfies more than one configuration of t. Then, let
f1 and f2 be two distinct configurations of t. Because f1 ̸= f2 and because t is surjective,
there is an element F ∈ F such that f1(t(F )) ̸= f2(t(F )). So write k1 = f1(t(F ))
and write k2 = f2(t(F )). Since σ satisfies f1, Definition 3.4 implies that σ(t(F )) is
the kth1 smallest element of σ(F ). Moreover, since σ satisfies f2, Definition 3.4 implies
that σ(t(F )) is the kth2 smallest element of σ(F ). However, this is impossible because
k1 = f1(t(F )) ̸= f2(t(F )) = k2.
Now, we prove Theorem 3.25.
Proof. By Definition 3.4, the total number of configurations of F equals to
∏
F∈F |F |.
Moreover, it is well-known that the number of surjective maps from [n] to [m] is given
by m!S(n,m). By Lemma 3.27, every surjective map satisfies exactly one configuration.
Moreover, by Theorem 3.10, every configuration of F is satisfied by some surjective map
from [n] to [m]. From this, the theorem follows.
214 Ars Math. Contemp. 21 (2021) #P2.03 / 201–217
Theorem 3.25 implies the following consequence relating to how the values An,m(f)
are distributed. By Theorem 3.10, every configuration f of t is satisfied by at least one
surjective map σ : [n] → [m]. Hence, by Theorem 3.25 and the fact that An,m(f) ≥ 1
always holds, it follows that for all constants k ≥ 1 the number of configurations f of t
that satisfy
An,m(f) ≤ k ·
m! S(n,m)∏
F∈F |F |
is at least (
1− 1
k
) ∏
F∈F
|F |.
We now illustrate Theorem 3.25 with some examples and in the process describe its
relationship with the hook-length formula.
Example 3.28. Let λ = (6, 5, 4, 3, 2, 1) and µ = (1). The skew shape λ/µ is depicted
below.
Since λ/µ has eighteen cells, let n = 18. The cells of λ/µ that are contained in exactly one
member of the family Fλ/µ are (1, 3), (2, 2), and (3, 1). Hence, S = {(1, 3), (2, 2), (3, 1)}
and n−|S|+1 = n−2. So let m = n−2 = 16. Then by Theorem 3.25 and Remark 3.26,
the average value of An,m(f) over all configurations f of λ/µ satisfying An,m(f) ≥ 1 is
given by
1
2
(
m+ 1
2
)((
m+ 1
2
)
+
2m+ 1
3
)
m!∏
F∈Fλ/µ |F |
=
=
1
2
(
16 + 1
2
)((
16 + 1
2
)
+
2 · 16 + 1
3
)
16!∏
r∈λ/µ hr
=
1
2
(
17
2
)((
17
2
)
+ 11
)
16!
(7 · 5 · 3 · 1)3 · 5 · 3 · 1 · 3 · 1 · 1
= 4014814003 +
1
5
.
The hook-length formula, first proved by Frame, Robinson, and Thrall [8], is well-
known. It is as follows. A skew shape λ/µ is a straight shape if µ = ∅. Given a Young
diagram λ, call a standard skew tableau of straight shape λ a standard Young tableaux of
shape λ. If λ is a Young diagram with n cells, then the number of standard Young tableaux
of shape λ equals
n!∏
r∈λ hr
.
B. T. Chan: A generalization of balanced tableaux and marriage problems with . . . 215
Moreover, the above formula was also proved by Edelman and Greene to equal the number
of balanced tableaux of shape λ [5]. Furthermore, the hook-length formula does not hold
for skew shapes. Taking m = n in Theorem 3.25, setting F = Fλ, and letting t be the
unique transversal of F , we see that the average value of An,m(f) over all configurations
f of t satisfying An,m(f) ≥ 1 equals to the number of standard Young tableau of shape λ.
Example 3.29. Let λ = (6, 5, 4, 3, 2, 1). The Young diagram λ is depicted below.
Since λ has twenty-one cells, let n = 21. The cell of λ that is contained in exactly one
member of the family Fλ is (1, 1). Hence, S = {(1, 1)} and n − |S| + 1 = n. So let
m = n = 21. Then by Theorem 3.25 and Remark 3.26, the average value of An,m(f) over
all configurations f of λ satisfying An,m(f) ≥ 1 is given by the hook-length formula
m!∏
F∈Fλ |F |
=
21!∏
r∈λ hr
=
21!
16 · 35 · 54 · 73 · 92 · 11
= 1100742656
and is, by the hook-length formula, equal to the number of standard Young tableaux of
shape λ.
Remark 3.30. Theorem 3.25 is versatile. For instance, possible applications of the special
case of Theorem 3.25 in the case of permutations are as follows. There is a formula for the
number of standard skew tableaux of shape λ/µ, known as Naruse’s formula. Asymptotic
properties of Naruse’s formula were analysed by Morales, Pak, and Panova in [17]. In
particular, it turns out that in general, the number of standard skew tableaux of shape λ/µ
divided by
n!∏
r∈λ/µ hr
,
where n is the number of cells of λ/µ, can be arbitrarily large. Hence, we can apply
Theorem 3.25 to Naruse’s formula and, using the work of Morales, Pak, and Panova in [17],
analyse lower bounds on the number of configurations f of λ/µ such that An,n(f) ≥ 1
and An,n(f) is strictly less than
n!∏
r∈λ/µ hr
.
Remark 3.31. Regarding Remark 3.30, there are variants and generalizations of Naruse’s
formula, the formula mentioned in Remark 3.30, for skew shifted shapes [9, 19]. What
we observe about these shapes is that the “hook-sets” for skew shifted shapes as defined
216 Ars Math. Contemp. 21 (2021) #P2.03 / 201–217
in [9, 19] also form examples of flagged families. Hence, the results in this section can
be replicated verbatim to include skew shifted shapes. Moreover, it is claimed by Morales,
Pak, and Panova in [17] that their analysis of Naruse’s formula can be extended to skew
shifted shapes. It also appears that we can even extend the above to involve posets known
as d-complete posets [19], as there is a generalization of Naruse’s formula for such posets
and the “hook-sets” in these formulas are a generalization of the “hook-sets” for the skew
shifted shapes [19].
We conclude this subsection by asking some natural enumerative questions related to
the quantity An,m(f) in Theorem 3.25.
1. Which configurations f as specified in Theorem 3.25 are such that An,m(f) is given
by Equation (3.9)?
2. Which flagged families F with transversal t are such that An,m(f), with m fixed, is
independent of the configuration f of t?
3. If the configuration f as specified in Theorem 3.25 is such that f(F ) = 1 for all
F ∈ F , when is An,m(f) maximal, and can An,m(f) be less than or equal to Equa-
tion (3.9)?
4. Let F be a flagged family and let t be a transversal of F . For m fixed, which config-
urations f of t maximize or minimize the value of An,m(f)?
5. Does the value of m in comparison to n affect answers to any of the above questions?
ORCID iDs
Brian Tianyao Chan https://orcid.org/0000-0003-0525-1362
References
[1] O. Angel, A. E. Holroyd, D. Romik and B. Virág, Random sorting networks, Adv. Math. 215
(2007), 839–868, doi:10.1016/j.aim.2007.05.019.
[2] M. Bóna, A walk through combinatorics, World Scientific Publishing Co., Inc., River Edge, NJ,
2002, doi:10.1142/4918, an introduction to enumeration and graph theory, With a foreword by
Richard Stanley.
[3] G. J. Chang, On the number of SDR of a (t, n)-family, European J. Combin. 10 (1989), 231–
234, doi:10.1016/s0195-6698(89)80056-3.
[4] P. Edelman and C. Greene, Combinatorial correspondences for Young tableaux, balanced
tableaux, and maximal chains in the weak Bruhat order of Sn, in: Combinatorics and alge-
bra (Boulder, Colo., 1983), Amer. Math. Soc., Providence, RI, volume 34 of Contemp. Math.,
pp. 155–162, 1984, doi:10.1090/conm/034/777699.
[5] P. Edelman and C. Greene, Balanced tableaux, Adv. in Math. 63 (1987), 42–99, doi:10.1016/
0001-8708(87)90063-6.
[6] N. J. Y. Fan, Standard Rothe tableaux, Discrete Math. 342 (2019), 3182–3193, doi:10.1016/j.
disc.2019.06.027.
[7] S. Fomin, C. Greene, V. Reiner and M. Shimozono, Balanced labellings and Schubert polyno-
mials, European J. Combin. 18 (1997), 373–389, doi:10.1006/eujc.1996.0109.
[8] J. S. Frame, G. d. B. Robinson and R. M. Thrall, The hook graphs of the symmetric groups,
Canad. J. Math. 6 (1954), 316–324, doi:10.4153/cjm-1954-030-1.
B. T. Chan: A generalization of balanced tableaux and marriage problems with . . . 217
[9] W. Graham and V. Kreiman, Excited Young diagrams, equivariant K-theory, and
Schubert varieties, Trans. Amer. Math. Soc. 367 (2015), 6597–6645, doi:10.1090/
s0002-9947-2015-06288-6.
[10] M. Hall, Jr., Distinct representatives of subsets, Bull. Amer. Math. Soc. 54 (1948), 922–926,
doi:10.1090/s0002-9904-1948-09098-x.
[11] P. Hall, On representatives of subsets, J. London Math. Soc 10 (1935), 26–30, doi:10.1112/
jlms/s1-10.37.26.
[12] J. L. Hirst and N. A. Hughes, Reverse mathematics and marriage problems with unique solu-
tions, Arch. Math. Logic 54 (2015), 49–57, doi:10.1007/s00153-014-0401-z.
[13] J. L. Hirst and N. A. Hughes, Reverse mathematics and marriage problems with finitely many
solutions, Arch. Math. Logic 55 (2016), 1015–1024, doi:10.1007/s00153-016-0509-4.
[14] L. Hurwicz and S. Reiter, Transversals, systems of distinct representatives, mechanism design,
and matching, in: Markets, Games, and Organizations, Springer, Berlin, Heidelberg, 2003,
doi:10.1007/978-3-540-24784-5 10.
[15] M. Konvalinka, A bijective proof of the hook-length formula for skew shapes, European J.
Combin. 88 (2020), 103104, 14, doi:10.1016/j.ejc.2020.103104.
[16] D. P. Little, Combinatorial aspects of the Lascoux-Schützenberger tree, Adv. Math. 174 (2003),
236–253, doi:10.1016/s0001-8708(02)00038-5.
[17] A. H. Morales, I. Pak and G. Panova, Asymptotics of the number of standard Young tableaux
of skew shape, European J. Combin. 70 (2018), 26–49, doi:10.1016/j.ejc.2017.11.007.
[18] A. H. Morales, I. Pak and G. Panova, Hook formulas for skew shapes I. q-analogues and bijec-
tions, J. Combin. Theory Ser. A 154 (2018), 350–405, doi:10.1016/j.jcta.2017.09.002.
[19] H. Naruse and S. Okada, Skew hook formula for d-complete posets via equivariant K-theory,
Algebr. Comb. 2 (2019), 541–571, doi:10.5802/alco.54.
[20] P. F. Reichmeider, The equivalence of some combinatorial matching theorems, Polygonal Publ.
House, Washington, NJ, 1984, doi:10.2307/3615712.
[21] R. P. Stanley, Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies
in Advanced Mathematics, Cambridge University Press, Cambridge, 1999, doi:10.1017/
cbo9780511609589, with a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.
[22] R. P. Stanley, Enumerative Combinatorics. Volume 1, volume 49 of Cambridge Studies in
Advanced Mathematics, Cambridge University Press, Cambridge, 2nd edition, 2012, doi:
10.1017/cbo9781139058520.
[23] F. Viard, A new family of posets generalizing the weak order on some coxeter groups, 2015,
arXiv:1508.06141 [math.CO].
[24] F. Viard, A natural generalization of balanced tableaux, 2016, arXiv:1407.6217v2
[math.CO].