=Paper= {{Paper |id=Vol-2113/paper5 |storemode=property |title=Rectangular Young tableaux with local decreases and the density method for uniform random generation |pdfUrl=https://ceur-ws.org/Vol-2113/paper5.pdf |volume=Vol-2113 |authors=Cyril Banderier,Philippe Marchal,Michael Wallner |dblpUrl=https://dblp.org/rec/conf/gascom/BanderierMW18 }} ==Rectangular Young tableaux with local decreases and the density method for uniform random generation== https://ceur-ws.org/Vol-2113/paper5.pdf

Rectangular Young tableaux with local decreases and
the density method for uniform random generation

Cyril Banderier
LIPN (UMR CNRS 7030)
Université de Paris Nord, France
http://lipn.univ-paris13.fr/~banderier/

Philippe Marchal
LAGA (UMR CNRS 7539)
Université de Paris Nord, France
https://www.math.univ-paris13.fr/~marchal

Michael Wallner
LaBRI (UMR CNRS 5800)
Université de Bordeaux, France
http://dmg.tuwien.ac.at/mwallner/

Abstract
In this article, we consider a generalization of Young tableaux in which
we allow some consecutive pairs of cells with decreasing labels. We show
that this leads to a rich variety of combinatorial formulas, which suggest
that these new objects could be related to deeper structures, similarly
to the ubiquitous Young tableaux. Our methods rely on variants of
hook-length type formulas, and also on a new efficient generic method
(which we call the density method) which allows not only to generate
constrained combinatorial objects, but also to enumerate them. We
also investigate some repercussions of this method on the D-finiteness
of the generating functions of combinatorial objects encoded by linear
extension diagrams, and give a limit law result for the average number
of local decreases.

Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: L. Ferrari, M. Vamvakari (eds.): Proceedings of the GASCom 2018 Workshop, Athens, Greece, 18–20 June 2018, published at
http://ceur-ws.org

60
1 Introduction

As predicted by Anatoly Vershik in [Ver01], the 21st century should see a lot of challenges and advances on the
links of probability theory with (algebraic) combinatorics. A key role is played here by Young tableaux, because
of their ubiquity in representation theory [Mac15] and in algebraic combinatorics, as well as their relevance in
many other different fields (see e.g. [Sta11]).
Young tableaux are tableaux with n cells labelled from 1 to n, with the additional constraint that these labels
increase among each row and each column (starting from the lower left cell). Here we consider the following
variant: What happens if we allow exceptionally some consecutive cells with decreasing labels? Does this variant
lead to nice formulas if these local decreases are regularly placed? Is it related to other mathematical objects or
theorems? How to generate them? This article gives some answers to these questions.
As illustrated in Figure 1, we put a bold red edge between the cells which are allowed to be decreasing.
Therefore these two adjacent cells can have decreasing labels (like 19 and 12 in the top row of Figure 1, or 11 and
10 in the untrustable Fifth column), or as usual increasing labels (like 13 and 15 in the bottom row of Figure 1).
We call these bold red edges “walls”.

7 18 19 12 21 20 17
2 6 8 9 10 14 16
1 3 4 5 11 13 15
Figure 1: We consider Young tableaux in which some pairs of (horizontally or vertically) consecutive cells are
allowed to have decreasing labels. Such places where a decrease is allowed (but not compulsory) are drawn by a
bold red edge, which we call a “wall”.

For Young tableaux of shape1 n × 2 several cases lead directly to nice enumerative formulas for the total
number of specific tableaux with 2n cells:

1. Walls everywhere: (2n)!

2. Horizontal walls everywhere: (2n)!
2n

3. Horizontal walls everywhere in left (or right) column: (2n − 1)!! = (2n)!
2n n!

2n
= (2n)!

4. Vertical walls everywhere: n (n!)2

1 2n
(2n)!
5. No walls: n+1 n = (n+1)(n!)2

In this article we are interested in the enumeration and the generation of Young tableaux (of different rect-
angular shapes) with such local decreases, and we investigate to which other mathematical notions they are
related. Section 2 focuses on the case of horizontal walls: We give a link with the Chung–Feller Theorem, bi-
nomial numbers and a Gaussian limit law. Section 3 focuses on the case of vertical walls: We give a link with
hook-length type formulas. Section 4 presents a generic method, which allows us to enumerate many variants
of Young tableaux (or more generally, linear extensions of posets), and which also offers an efficient uniform
random generation algorithm, and links with D-finiteness.

1 We will refer to “n × m Young tableaux”, or “Young tableaux of shape n × m”, for rectangular Young tableaux with n rows

and m columns. They are trivially in bijection with m × n Young tableaux.

61
2 Vertical walls, Chung–Feller and binomial numbers
In this section we consider a family of Young tableaux having some local decreases at
places indicated by vertical walls, see Figure 2.
Theorem 2.1. The number of n × 2 Young tableaux with k vertical walls is equal to

n 2n
14 12
vn,k = .
n+1−k k n

Proof. We apply a bijection between two-column Young tableaux of size 2n with k walls
10 13
and Dyck paths without the positivity constraint of length 2n and k coloured down steps.
These paths start at the origin, end on the x-axis and are composed out of up steps (1, 1), 9 11
and coloured down steps (1, −1) which are either red or blue.
Given an arbitrary two-column Young tableau, the m-th step of the associated path is
an up step if the entry m appears in the left column, while the m-th step is a down step, 8 7
if the m-th entry appears in the right column. Furthermore, we associate colours to the
down steps: If the m-th down step is in a row with a wall we colour it red, and blue
otherwise.
4 6
Thus, vn,k counts the number of paths with exactly k red down steps. Note that the
down steps of a path below the x-axis are always red because a wall has to be involved,
yet above the x-axis down steps can have any colour. We decompose paths with k
3 5
coloured down steps with respect to the number of steps which are below the x-axis. By
the Chung–Feller Theorem [CF49] (see also [Che08] for a bijective proof) the number of 2 1
Dyck paths of length 2n with i down steps below the x-axis is independent of i and equal
1 2n
to the Catalan number Catn = n+1 n . When i steps are below the x-axis we have to Figure 2: Example
colour k − i of the remaining n − i steps above the x-axis red. This gives
of one of our n × 2
k Young tableaux with
X n−i n+1 walls.
vn,k = Catn = Catn ,
i=0
k − i k

and the claim follows.
As a simple consequence, we get the following result.
Corollary 2.2. The average number of linear extensions of a random n × 2 Young tableau with k walls, where
the location of these walls is chosen uniformly at random, is

1 2n
.
n+1−k n
Proof. In a two-column Young tableau of size 2n we have nk possibilities to add k walls.

We now conclude this section with a limit law result.
Theorem 2.3. Let Xn be the random variable for the number of walls in a random n × 2 Young tableau
n −n/2
chosen uniformly at random. The rescaled random variable X√ converges to the standard normal distribution
n/4
N (0, 1).
Proof. We see that the total number of two-column Young tableaux of size n with walls is equal to
n
X
vn,k = Catn 2n+1 − 1 .

k=0

Then, the previous results show that

n+1 1
P (Xn = k) = ,
k 2n+1 − 1
which is a slight variation of a binomial distribution with parameters n+1 and probability 1/2. By the well-known
convergence of the rescaled binomial distribution to a normal distribution the claim holds (see e.g. [FS09]).

62
3 Horizontal walls and the hook-length formula
The hook-length formula is a well-known formula to enumerate standard Young tableaux of a given shape (see
e.g. [Mac15, Sta11]). What happens if we add walls in these tableaux? Let us first consider the case of a Young
tableau of size n such that its walls cut the corresponding tableau into m disconnected parts without walls of
size k1 , . . . , km (e.g., some walls form a full horizontal or vertical line). Then, the number of fillings of such a
tableau is trivially:
m
n! Y
HookLengthFormula(subtableau of size ki ).
k1 ! . . . km ! i=1
So in the rest of article, we focus on walls which are not trivially splitting the problem into subproblems: They
are the only cases for which the enumeration (or the random generation) is indeed challenging.
We continue our study with families of Young tableaux of shape m × n having some local decreases at places
indicated by horizontal walls in the left column. We will need the following lemma counting special fillings of
Young tableaux.
Lemma 3.1. The number of n × 2 “Young tableaux” with 2λ cells filled with the numbers 1, 2, . . . , 2n for n ≥ λ
such that (the number 2n is used and) all consecutive numbers between the minimum of the second column and
2n are used is equal to

2n 2n
− . (1)
λ λ−1

Proof. The constraint on the maximum implies that all not used numbers are smaller than the number in the
bottom right cell. Therefore it is legitimate to add these numbers to the tableaux. In particular, we create a
standard Young tableau of shape (λ, 2n − λ) (i.e., the first column has λ cells and the second one 2n − λ) which
is in bijection with the previous tableau.
Next we build a bijection between standard Young tableaux of shape (λ, 2n − λ) and Dyck paths with up
steps (1, 1) and down steps (1, −1) starting at (0, 2(n − λ)), always staying above the x-axis and ending on the
x-axis after 2n steps. In particular, if the number i appears in the left column, the i-th step is an up step, and
if it appears in the right column, the i-th step is a down step.
Finally, note that these paths can be counted using the reflection principle [And87]. In particular, there are
2n 2n

λ possible paths from (0, 2(n − λ)) to (2n, 0). Yet, λ−1 “bad” paths cross the x-axis at some point. This can
be seen, by cutting such a path at the first time it reaches altitude −1. The remaining path is reflecting along
the horizontal line y = −1 giving a path ending at (2n, −2). It is easy to see that this is a bijection between bad
paths from (0, 2(n − λ)) to (2n, 0) and all paths from (0, 2(n − λ)) to (2n, −2). The latter is obviously counted
2n
by λ−1 , as λ − 1 of the 2n steps have to be up steps.
Theorem 3.2. The number of n × 2 Young tableaux of size 2n with k walls in the first column at heights
0 < hi < n, i = 1, . . . , k with hi < hi+1 is equal to
k+1
Y 2hi + 1
1
,
2n + 1 i=1 hi − hi−1

with h0 := 0 and hk+1 := n.
Remark 3.3. Denoting consecutive relative distances of the walls by λi := hi − hi−1 for i = 1, . . . , k + 1 the
previous result can also be stated as
k+1
Y 2(λ1 + . . . + λi ) + 1
1
.
2n + 1 i=1 λi

Proof. We will show this result by induction on the number of walls k. For k = 0 the result is clear as we
are counting two-column standard Young tableaux which are counted by Catalan numbers (for a proof see also
Lemma 3.1 with λ = n).
Next, assume the formula has been shown for k − 1 walls and arbitrary n. Choose a proper filling with k walls
and cut the tableau at the last wall at height hk into two parts. The top part is a Young tableau with 2(n − hk )

63
elements and no walls, yet labels between 1 and 2n. Furthermore, it has the constraint that all numbers larger
than the element in the bottom right cell have to be present. This is due to the fact that all elements in lower
cells must be smaller. In other words, these are the objects of Lemma 3.1 and counted by (1).
The bottom part is a Young tableau with k − 1 walls and 2hk elements (after proper relabelling). By our
induction hypothesis this number is equal to
k
1 Y 2hi + 1
.
2hk + 1 i=1 hi − hi−1

As a final step, we rewrite Formula (1) into

2(n − λ) + 1 2n + 1
,
2n + 1 λ

and set λ := n − hk . Multiplying the last two expressions then shows the claim.

Remark 3.4. Note that so far we have not found a direct combinatorial interpretation of this formula. However,
note that in general 2n+1
λ does not have to be divisible by 2n + 1.

Let us now also give the general formula for n × m Young tableaux with walls of lengths m − 1 from columns
1 to m − 1, i.e., a hole in column m and nowhere else in a row with walls. Before we state the result, let us
define for integers n, k the falling factorial (n)k := n(n − 1) · · · (n − k + 1) and
for integers n,n!m1 , . . . , mk such
that n ≥ m1 + · · · + mk the (shortened) multinomial coefficient2 m1 ,m2n,...,mk := m1 !m2 !···mk !(n−m 1 −...−mk )!
.

Theorem 3.5. The number of n × m Young tableaux of size mn with k walls from column 1 to m − 1 at heights
0 < hi < n, i = 1, . . . , k with hi < hi+1 is equal to
  !
k+1 m−2 −1 k+1
Y m(λ1 + . . . λi ) + m − 1
(m − 1)! Y Y λi + j
  ,
(mn + m − 1)m−1 i=1 j=1 j i=1
λi , . . . , λ i

where λi := hi − hi−1 and the λi ’s in the multinomial coefficients appear m − 1 times.

Proof (Sketch). First derive an extension of Lemma 3.1 proved by the hook-length formula and then compute
the product. Note that this gives a telescoping factor, giving the first factor.

Just as one more example, here is a more explicit example of what it gives.

Corollary 3.6. The number of n × 4 Young tableaux with k walls from column 1 to 3 at heights 0 < hi < n,
i = 1, . . . , k with hi < hi+1 is equal to

k+1
! k+1 !
6 Y 2 Y 4(λ1 + . . . λi ) + 3
2 (λ + 2)
,
(4n + 3)(4n + 2)(4n + 1) i=1
(λ i + 1) i i=1
λi , λi , λi

with λi := hi − hi−1 .

Let us consider some other special cases. For example, consider tableaux with walls between every row and a
(mn)!
hole in the last column. For this case we set λi = 1 for all i. This gives the general formula n!(m!)n , for n × m

tableaux, see OEIS A001147 for m = 2 and OEIS A025035 to OEIS A025042 for the special cases m = 3, . . . , 10.
Now that we gave several examples of closed-form formulas enumerating some families of Young tableaux with
local decreases, we go to harder families which do not necessarily lead to a closed-form result. However, we shall
see that we have a generic method to get useful alternative formulas (based on recurrences), also leading to an
efficient uniform random generation algorithm.
2 In the literature, one more often finds the notation n n!
m1 ,m2 ,...,mk ,n−m1 −...−mk
:= m !m !···m !(n−m . But we opted
1 2 k 1 −...−mk )!
in this article for a more suitable notation to the eyes of our readers!

64
4 The density method, D-finiteness, random generation
In this section, we present a generic approach which allows us to enumerate and generate any shape involving
some walls located at periodic positions. To keep it readable, we illustrate it with a specific example (without
loss of generality).
So, we now illustrate the method on the case of a 2n × 3 tableau where we put walls on the right and on the
left column at height 2k (for 1 ≤ k ≤ n − 1), see the leftmost tableau in Figure 3. In order to have an easier
description of the algorithm (and more compact formulas), we generate/enumerate first similar tableaux with an
additional cell at the bottom of the middle column, see the middle tableau in Figure 3: It is a polyomino Polyon
with 6n + 1 cells. There are trivially (6n + 1)! fillings of this polyomino with the numbers 1 to 6n + 1. Some of
these fillings are additionally satisfying the classical constraints of Young tableaux (i.e., the labels are increasing
in each row and each column), with some local decreases allowed between cells separated by a wall (as shown
with bold red edges in Figure 3). Let fn be the number of such constrained fillings.
To compute fn we use a generic method which we call the density method, which we introduced and used
in [Mar18, Mar16, BMW18]. It relies on a geometric point of view of the problem: Consider the hypercube
[0, 1]6n+1 and associate to each coordinate a cell of Polyon . To almost every element α of [0, 1]6n+1 (more
precisely, every element with all coordinates distinct) we can associate a filling of Polyon : Put 1 into the cell
of Polyon corresponding to the smallest coordinate of α, 2 into the cell of Polyon corresponding to the second
smallest coordinate of α and so on. The reverse operation associates to every filling of Polyon a region of [0, 1]6n+1
(which is actually a polytope). We call P the set of all polytopes corresponding to correct fillings of Polyon (i.e.,
respecting the order constraints). This P is also known as the “order polytope” in poset theory.
Let us explain how the density method works. It requires two more ingredients. The first one is illustrated
in Figure 3: It is a generic building block with 7 cells with names X,Y,Z,R,S,V,W. We put into each of these
cells a number from [0, 1], which we call x, y, z, r, s, v, w, respectively. The second ingredient is the sequence of
polynomials pn (x), defined by the following recurrence (which in fact encodes the full structure of the problem,
building block after building block):
Z zZ zZ yZ zZ 1Z w
pn+1 (z) = pn (v) dv dw ds dr dy dx, with p0 = 1. (2)
0 x 0 r z y

The fact that this sequence of nested integrals encodes the full structure of the problem (i.e. all the inequalities)
is better stressed with the following writing:
Z Z Z Z Z Z
pn+1 (z) = pn (v) dv dw ds dr dy dx, with p0 = 1. (3)
0