Counting tableaux with row and column bounds

C. Krattenthaler† S. G. Mohanty‡

Abstract. It is well-known that the generating function for tableaux of a given skew shape with r rows where the parts in the i’th row are bounded by some nondecreasing upper and lower bounds which depend on i can be written in form of a determinant of size r. We show that the generating function for tableaux of a given skew shape with r rows and c columns where the parts in the i’th row are bounded by nondecreasing upper and lower bounds which depend on i and the parts in the j’th column are bounded by nondecreasing upper and lower bounds which depend on j can also be given in determinantal form. The size of the determinant now is r + 2c. We also show that determinants can be obtained when the nondecreasingness is dropped. Subsequently, analogous results are derived for (α, β)-plane partitions.

1. Introduction and Definitions. Let λ λ λ = (λ_{1}, …, λ_{r}) and μ μ μ = (μ_{1}, …, μ_{r}) be r-tupels of integers satisfying λ_{1} ≥ ⋯ ≥ λ_{r}, μ_{1} ≥ ⋯ ≥ μ_{r}, and λ λ λ ≥ μ μ μ, meaning λ_{i} ≥ μ_{i} for all i. A tableau of shape λ λ λ/μ μ μ is an array π

(1.1)  \begin{aligned}& π_{1,μ_{1}+1} & . . . . . . . . . . . . . . . . & π_{1,λ_{1}} \\ π_{2,μ_{2}+1} … & π_{2,μ_{1}+1} & . . . . . . . . . & π_{2,λ_{2}} \\ ... & ⋮ & ... \\ π_{r,μ_{r}+1} & . . . . . . . . . . . . . . . . . . . . . . . . . . & π_{r,λ_{r}} \end{aligned}

of integers π_{ij}, 1 ≤ i ≤ r, μ_{i} + 1 ≤ j ≤ λ_{i}, such that the rows are weakly and the columns are strictly increasing. The number of entries in the tableau in (1.1) is (λ_{1} − μ_{1}) + ⋯ + (λ_{r} − μ_{r}), for which we write |λ λ λ − μ μ μ|. The entries will be called parts of the tableau. The sum of all parts of a tableau π is called the norm, in symbols n(π), of the tableau.

In order to make λ λ λ and μ μ μ unique, we always assume that μ_{r} = 0. Sometimes we will call λ_{1} the width, and r the depth of a shape λ λ λ/μ μ μ. If μ μ μ = 0 we shortly write λ λ λ for the shape λ λ λ/μ μ μ.

The weight w(π) of a tableau π under consideration will be ∏ x_{π_{ij}} where the product is over all parts π_{ij} of π.

†Institut für Mathematik der Universität Wien, Strudlhofgasse 4, A-1090 Wien, Austria.

E-mail: KRATT@AWIRAP.BITNET ‡McMaster University, Hamilton, Ontario, Canada L8S 4K1.

E-mail: MOHANTY@MCMAIL.CIS.MCMASTER.CA

It is well-known (cf. [2,4,5,9]) that the generating function ∑ w(π) summed over all tableaux π of shape λ λ λ/μ μ μ where the parts in row i are at most a_{i} and at least b_{i} for some r-tupels a a a = (a_{1}, …, a_{r}) and bbb = (b_{1}, …, b_{r}) satisfying a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{r}, b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{r}, and a a a ≥ bbb, can be written in form of an r × r-determinant,

det_{1≤s,t≤r}(h_{λ_{s}−s−μ_{t}+t}(x x x; a_{s}, b_{t})) ,

where h_{n}(x x x; A, B) is the complete homogenous symmetric functions of order n in the variables x_{B}, x_{B+1}, …, x_{A},

h_{n}(x x x; A, B) := ∑_{B≤i_{1}≤i_{2}≤···≤i_{n}≤A} x_{i_{1}}x_{i_{2}} ⋯ x_{i_{n}} .

A natural generalization of this problem is to ask for the generating function ∑ w(π) for tableaux with row bounds and column bounds, to be precise, for the generating function for tableaux of shape λ λ λ/μ μ μ where the parts in row i are at most a_{i} and at least b_{i}, and the parts in column j are at most c_{j} and at least d_{j}, for some tupels a a a = (a_{1}, …, a_{r}), bbb = (b_{1}, …, b_{r}), ccc = (c_{1}, …, c_{λ_{1}}), and d d d = (d_{1}, …, d_{λ_{1}}) satisfying a_{1} ≤ a_{2} ≤ ⋯ ≤ a_{r}, b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{r}, c_{1} ≤ c_{2} ≤ ⋯ ≤ c_{λ_{1}}, d_{1} ≤ d_{2} ≤ ⋯ ≤ d_{λ_{1}}, a a a ≥ bbb, and ccc ≥ d d d. In Theorem 1 we show that this generating function can also be written in form of a determinant whose entries are complete homogenous symmetric functions. The size of the determinant is r + 2λ_{1}, i.e. it is the depth plus twice the width of the shape. Also in section 2, from this theorem we deduce determinant formulas for the norm generating function of (α, β)-reverse plane partitions (which are generalizations of tableaux, cf. section 2 for the definition) with row and column bounds, thus obtaining Corollary 2. Finally, in section 3 we show how to get determinants if the monotonicity of the row and column bounds is dropped. Now in adverse choices of the shape and the row and column bounds, the size of the determinant might explode.

2. Monotone row and column bounds. Recall (Gessel and Viennot [3,4]) that a tableau π of shape λ λ λ/μ μ μ with the parts in row i being at most a_{i} and at least b_{i} can be bijectively mapped onto a family (P_{1}, …, P_{r}) of nonintersecting lattice paths. “Nonintersecting” in this context means that each two paths of this family have no point in common. This correspondence maps the i-th row of π to the i-th path P_{i} in the family such that P_{i} starts at (μ_{i} +r+1−i, b_{i}) and terminates at (λ_{i} +r+1−i, a_{i}), and such that the parts of the i-th row can be read off the heights of the horizontal steps in P_{i}. Figure 1 gives a simple example for r = 3, λ λ λ = (5, 4, 4), μ μ μ = (2, 1, 0), a a a = (8, 9, 12), and bbb = (1, 3, 6).

\begin{aligned}1 ≤ & & & 4 & 6 & 6 & ≤ 8 \\ 3 ≤ & & 5 & 7 & 9 & & ≤ 9 \\ 6 ≤ & 6 & 8 & 9 & 11 & & ≤ 12 \end{aligned} ⟷  _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • • •  • • • 4 6 6 5 7 9 6 8 9 11 P_{1} P_{2} P_{3}

Figure 1

The condition that π has strictly increasing columns corresponds to the condition that the paths are nonintersecting. In addition, this bijection is weight-preserving if we define the weight of a family P = (P_{1}, …, P_{r}) of paths to be

w(P) = ∏ x_{h} ,

where the product is over the heights h of all the horizontal steps of the paths.

We want to compute the generating function ∑ w(π) for tableaux π of shape λ λ λ/μ μ μ where the parts in row i are at most a_{i} and at least b_{i}, i = 1, 2, …, r, and the parts in column j are at most c_{j} and at least d_{j}, j = 1, 2, …, λ_{1}. Note that we always assume μ_{r} = 0 so that there are lower and upper bounds for each column. To abbreviate the notation, for these tableaux we shall often use the terminology tableaux which obey the row bounds a a a, bbb and the column bounds ccc, d d d, or even shorter tableaux obeying a a a, bbb, ccc, d d d, always assuming that a a a and bbb are the upper and lower row bounds while ccc and d d d are the upper and lower column bounds, respectively.

A simple trick enables us to use nonintersecting paths for this generalized problem also. This is accomplished by adding 2λ_{1} “dummy paths” of length 0. In fact, tableaux π of shape λ λ λ/μ μ μ obeying a a a, bbb, ccc, d d d bijectively correspond to families (P_{1}, …, P_{r}, P_{r+1}, …, P_{r+2λ_{1}}) of nonintersecting lattice paths where for i = 1, …, r by using the Gessel/Viennot bijection the path P_{i} is obtained from the i’th row of π respecting the row bounds a a a and bbb, P_{i} : (μ_{i} + r + 1 − i, b_{i}) → (λ_{i} + r + 1 − i, a_{i}), while the paths P_{l}, l = r + 1, …, r + 2λ_{1}, are dummy paths of length 0, the starting and final points of which are given below.

P_{l} : (l′ + M(l′), d_{l′} − 1) → (l′ + M(l′), d_{l′} − 1) l = r + 1, …, r + λ_{1},

with l′ = l − r, and

P_{l} : (l′′ + Λ(l′′), c_{l′′} + 1) → (l′′ + Λ(l′′), c_{l′′} + 1) l = r + λ_{1} + 1, …, r + 2λ_{1},

with l′′ = l − r − λ_{1}. The auxiliary functions M and Λ are defined by

M(I) = ∑_{j=1}^{r} χ(I > μ_{j}) and Λ(I) = ∑_{j=1}^{r} χ(I > λ_{j}) ,

where χ(A) is the usual truth function (χ(A) = 1 if A is true, and χ(A)=0 otherwise). Figure 2 gives an example for this correspondence with r = 4, λ = (8, 6, 4, 3), μ = (3, 2, 0, 0), a a a = (10, 12, 13, 13), bbb = (1, 1, 2, 3), ccc = (6, 6, 9, 10, 11, 11, 12, 12), d d d = (2, 2, 3, 3, 3, 4, 6, 7).

2 ≤ 2 ≤ 3 ≤ 3 ≤ 3 ≤ 4 ≤ 6 ≤ 7 ≤
1 ≤  3  4  6  7  7 ≤ 10
1 ≤  5  5  8  9  ≤ 12
2 ≤ 2 3 6  6  ≤ 13
3 ≤ 4 5 8  ≤ 13
≤ 6 ≤ 6 ≤ 9 ≤ 10 ≤ 11 ≤ 11 ≤ 12 ≤ 12

↕

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • • • • • • • • • • • • • • • • • • • • • • • •^{3} ^{4} ^{6} ^{7} ^{7}^{5} ^{5} ^{8} ^{9}^{2} ^{3} ^{6} ^{6}^{4} ^{5} ^{8}  ^{P_{1}}^{P_{2}}^{P_{3}}^{P_{4}}_{P_{5}}_{P_{6}} ^{P_{7}} ^{P_{8}} ^{P_{9}} ^{P_{10}}^{P_{11}}^{P_{12}}^{P_{13}}^{P_{14}}^{P_{15}}  ^{P_{16}} ^{P_{17}}^{P_{18}} ^{P_{19}}^{P_{20}}

Figure 2

One easily gets convinced that P_{r+1}, …, P_{r+λ_{1}} force P_{1}, …, P_{r} to stay above them, and, analogously, that P_{r+λ_{1}+1}, …, P_{r+2λ_{1}} force P_{1}, …, P_{r} to stay below them; otherwise (P_{1}, …, P_{r}, P_{r+1}, …, P_{r+2λ_{1}}) would not be nonintersecting. But that means that the corresponding tableau obeys the column bounds d d d and ccc.

Now, since we have reduced our tableaux counting problem to the problem of counting families of nonintersecting paths, we may apply the main theorem of Gessel and Viennot.

Proposition 1. (Gessel, Viennot [4, sec. 2]) The generating function ∑ w(P) for families P = (P_{1}, …, P_{n}) of nonintersecting paths, where P_{i} runs from (C_{i}, D_{i}) to (A_{i}, B_{i}) is given by

(1.2)  det_{1≤s,t≤n}(h_{A_{s}−C_{t}}(x x x; B_{s}, D_{t})) ,

whenever the location of the points (A_{i}, B_{i}), (C_{i}, D_{i}), i = 1, …, n, guarantees the following property: Let the path Q_{i}, i = 1, …, n, start at (C_{i}, D_{i}) and terminate at any of the points (A_{j}, B_{j}), j = 1, …, n. If (Q_{1}, …, Q_{n}) is a family of nonintersecting lattice paths, then for all i = 1, …, n the path Q_{i} terminates at (A_{i}, B_{i}). □

This yields the following theorem:

Theorem 1. Let a a a, bbb, ccc, d d d as above. The generating function ∑ w(π) for tableaux π of shape λ λ λ/μ μ μ where the parts in row i are at most a_{i} and at least b_{i}, and the parts in column j are at most c_{j} and at least d_{j} is given by

(1.3)  det_{1≤s,t≤r+2λ_{1}}(h_{A_{s}−C_{t}}(x x x; B_{s}, D_{t})) ,

where A_{i}, B_{i}, C_{i}, D_{i} are displayed in the table below.

1 ≤ i ≤ r r + 1 ≤ i ≤ r + λ_{1} r + λ_{1} + 1 ≤ i ≤ r + 2λ_{1}
i′ = i − r  i′′ = i − r − λ_{1}
A_{i} λ_{i} + r + 1 − i  i′ + M(i′)  i′′ + Λ(i′′)
B_{i}  a_{i}  d_{i′} − 1  c_{i′′} + 1
C_{i} μ_{i} + r + 1 − i  i′ + M(i′)  i′′ + Λ(i′′)
D_{i}  b_{i}  d_{i′} − 1  c_{i′′} + 1

Table 1

□

Setting x_{i} = q^{i} for all i, we obtain as a corollary the norm generating function for tableaux with row and column bounds.

Corollary 1. Let a a a, bbb, ccc, d d d as in Theorem 1. The generating function ∑ q^{n(π)} for tableaux π of shape λ λ λ/μ μ μ where the parts in row i are at most a_{i} and at least b_{i}, and the parts in column j are at most c_{j} and at least d_{j} is given by

(1.4)  det_{1≤s,t≤r+2λ_{1}} (q^{D_{t}(A_{s}−C_{t})} [ \begin{matrix}A_{s} + B_{s} − C_{t} − D_{t} \\ B_{s} − D_{t} \end{matrix} ]) ,

where A_{i}, B_{i}, C_{i}, D_{i} are displayed in Table 1. The q-binomial coefficient is defined by

[ \begin{matrix}n \\ k \end{matrix} ] = \frac{(1 − q^{n})(1 − q^{n−1}) ⋯ (1 − q^{n−k+1})}{(1 − q^{k})(1 − q^{k−1}) ⋯ (1 − q)} ,

if n ≥ k ≥ 0, and 0 otherwise. □

Applying this result to tableaux of shape (8, 6, 4, 3)/(3, 2, 0, 0) obeying a a a = (10, 12, 13, 13), bbb = (1, 1, 2, 3), ccc = (6, 6, 9, 10, 11, 11, 12, 12), and d d d = (2, 2, 3, 3, 3, 4, 6, 7), a typical example of which is displayed in Figure 2, we obtain that the norm generating function for the 196.650.160 tableaux of this type is given by

q63+7 q64+31 q65+108 q66+318 q67+830 q68+1967 q69+4309 q70+8825 q71+17054 q72+31300 q73+54857 q74+92202 q75

+149150 q76+232896 q77+351926 q78+515736 q79+734334 q80+1017550 q81+1374118 q82+1810680 q83+2330671 q84 +2933374 q85+3613028 q86+4358418 q87+5152677 q88+5973797 q89+6795371 q90+7588103 q91+8321344 q92 +8965234 q93+9492509 q94+9880603 q95+10112996 q96+10180583 q97+10081990 q98+9823778 q99+9419561 q100 +8889120 q101+8256606 q102+7549054 q103+6794310 q104+6019584 q105+5249728 q106+4506378 q107+3806938 q108 +3164499 q109+2587580 q110+2080681 q111+1644535 q112+1277020 q113+973600 q114+728280 q115+534013 q116 +383492 q117+269382 q118+184885 q119+123772 q120+80708 q121+51140 q122+31435 q123+18679 q124+10708 q125 +5890 q126+3102 q127+1549 q128+733 q129+322 q130+132 q131+48 q132+16 q133+4 q134+q135.

Corollary 1 can be generalized in the following way. Call an array \overline{π} of the form (1.1) an (α, β)-reverse plane partition of shape λ λ λ/μ μ μ if

\overline{π}_{ij} + α ≤ \overline{π}_{i,j+1} 1 ≤ i ≤ r, μ_{i} + 1 ≤ j < λ_{i}

and (1.5)

\overline{π}_{ij} + β ≤ \overline{π}_{i+1,j} 1 ≤ i < r, μ_{i} + 1 ≤ j ≤ λ_{i+1} .

This definition comprises several classes of reverse plane partitions. In particular, tableaux are (0, 1)-reverse plane partitions.

Given a tableau π of shape λ λ λ/μ μ μ, the transformation

π_{ij} → π_{ij} + i(β − 1) + jα ,

applied to every part π_{ij} of π, maps π to an (α, β)-reverse plane partition. Clearly, this mapping is a bijection between tableaux and (α, β)-reverse plane partitions. This bijection does not preserve w(π) nor the norm n(π). But for the norm we have the simple assertion that the norm of the (α, β)-reverse plane partition which was obtained from a certain tableau under this transformation differs from the norm of this tableau by ∑ (i(β − 1) + jα), where the sum is over all i, j with 1 ≤ i ≤ r and μ_{i} + 1 ≤ j ≤ λ_{i}. This quantity only depends on the shape λ λ λ/μ μ μ and not on the tableau involved. Therefore, using this bijection it is an easy task to transfer Corollary 1 to the more general case of (α, β)-reverse plane partitions. One only has to find out how the row and column bounds change under this transformation.

Corollary 2. Let a a a, bbb be r-tupels and ccc, d d d be λ_{1}-tupels of integers satisfying

a_{i} + α(λ_{i+1} − λ_{i}) + (β − 1) ≤ a_{i+1}, b_{i} + α(μ_{i+1} − μ_{i}) + (β − 1) ≤ b_{i+1} (1.6)

c_{i} + (β − 1)(λ′_{i+1} − λ′_{i}) + α ≤ c_{i+1}, d_{i} + (β − 1)(μ′_{i+1} − μ′_{i}) + α ≤ d_{i+1} .

The generating function ∑ q^{n(\overline{π})} for (α, β)-reverse plane partitions \overline{π} of shape λ λ λ/μ μ μ where the last part in row i is at most a_{i} and the first part in row i is at least b_{i}, and where the down-most part in column j is at most c_{j} and the upper-most part in column j is at least d_{j}, is given by

(1.7) q^{(β−1) ∑_{i=1}^{r} i(λ_{i}−μ_{i})+α ∑_{i=1}^{r}[\binom{λ_{i}+1}{2}−\binom{μ_{i}+1}{2}]}

× det_{1≤s,t≤r+2λ_{1}} (q^{D_{t}(A_{s}−C_{t})} [ \begin{matrix}A_{s} + B_{s} − C_{t} − D_{t} \\ B_{s} − D_{t} \end{matrix} ]) ,

where A_{i}, B_{i}, C_{i}, D_{i} are displayed in Table 2.

1 ≤ i ≤ r  r + 1 ≤ i ≤ r + λ_{1}  r + λ_{1} + 1 ≤ i ≤ r + 2λ_{1}
i′ = i − r  i′′ = i − r − λ_{1}
A_{i}  λ_{i} + r + 1 − i  i′ + M(i′)  i′′ + Λ(i′′)
B_{i}  a_{i} − (β − 1)i − αλ_{i}  d_{i′} − (β − 1)(μ′_{i′′} + 1) − αi′′ − 1 c_{i′′} − (β − 1)λ′_{i′′} − αi′′ + 1
C_{i}  μ_{i} + r + 1 − i  i′ + M(i′)  i′′ + Λ(i′′)
D_{i} b_{i} − (β − 1)i − α(μ_{i} + 1) d_{i′} − (β − 1)(μ′_{i′′} + 1) − αi′′ − 1 c_{i′′} − (β − 1)λ′_{i′′} − αi′′ + 1

Table 2

λ λ λ′/μ μ μ′ is the conjugate shape of λ λ λ/μ μ μ. □

Remarks. 1) Theorem 1 and Corollary 2 immediately can be used for columnstrict plane partitions and (α, β)-plane partitions (cf. [5]), respectively, since rotation by 180^{∘} turns them into tableaux and (α, β)-reverse plane partitions, respectively.

2) Very often the size of the determinant can be reduced by ignoring superflous paths. (In Figure 2 P_{5}, P_{6}, P_{17}, P_{19}, P_{20} are superflous.) Also, the entries in the determinant can be reduced by replacing a_{i} by min{a_{i}, c_{λ_{i}}}, and b_{i} by max{b_{i}, d_{μ_{i}+1}}. For a rectangular shape (c^{r}) it is easily seen that after these manipulations P_{r+1} and P_{r+2c} are always superflous so that in this case the size of the determinant in fact is at most r + 2c − 2.

3) Reflection in the main diagonal turns an (α, β)-reverse plane partition of shape λ λ λ/μ μ μ into an (β, α)-reverse plane partition of shape λ λ λ′/μ μ μ′. Therefore the norm generating function for (α, β)-reverse plane partitions of a given rectangular shape (c^{r}) and with given row and column bounds can be computed in two different ways using Corollary 2. The first way is to use Corollary 2 directly, thus (by Remark 2) obtaining a determinant of size (r + 2c − 2). Or, secondly, one could use the reflection which exchanges α and β, r and c, a a a and ccc, and bbb and d d d, and then apply Corollary 2 with these new parameters. This time a determinant of size (c + 2r − 2) is obtained. Therefore, in order to minimize the size of the determinant, one should first check whether r ≥ c or not, in the first case use Corollary 2 directly, in the latter Corollary 2 should be used only after first having performed the reflection. With a skew shape, in general Corollary 2 will not be applicable in two ways as described above because after the reflection the new bounds might not satisfy (1.6). But as will be seen later, it is possible to give a determinant for the “reflected” problem, also.

4) Of course, our formula can also be used if there are bounds only on three sides. In fact, in this case the determinants in Theorem 1 or Corollaries 1,2 trivially reduce to determinants of size r + λ_{1}. It should be noted that three bound counting for rectangular shapes has been considered earlier by Chorneyko and Zing [1, 8, Theorems 1.2.1 and 1.2.2]. Using the Narayana/Mohanty [cf. 7] method of successively building up determinants, they derived determinants for the number of rectangular tableaux with bounds a a a, bbb, ccc or a a a, bbb, d d d, respectively. However, Chorneyko and Zing’s determinants slightly differ from our q = 1-results. But they can also be explained by nonintersecting lattice paths. These determinants correspond to a slightly different choice of the dummy paths. For example, to obtain Chorneyko and Zing’s determinant in the (a a a, bbb, d d d)-case for a shape (c^{r}) [8, Theorem 1.2.1], one had to take the dummy paths P_{l} : (l, b_{1} − 1) → (l, max{b_{1}, d_{l−r}} − 1), l = r + 1, …, r + c, instead of P_{l} : (l, d_{l−r} − 1) → (l, d_{l−r} − 1). The corresponding picture of a typical example is given in the figure below.

\begin{aligned}& 2 ≤ & 4 ≤ & 4 ≤ & 5 ≤ \\ 1 ≤ & 3 & 4 & 6 & 7 & ≤ 8 \\ 3 ≤ & 5 & 5 & 7 & 9 & ≤ 9 \\ 6 ≤ & 6 & 8 & 9 & 11 & ≤ 12 \end{aligned} ⟷  _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • • • • • • •  • • • • • • • 3 4 6 7 5 5 7 9 6 8 9 11 P_{4}P_{5}P_{6}P_{7} P_{1} P_{2} P_{3}

Figure 3

Clearly, the dummy paths in Figure 3 have just the same effect as those in Figure 2. We decided to take paths of length 0 because this choice causes the entries in the determinant to become smaller. □

3. Unrestricted row and column bounds. It turns out that even if we drop the condition of the bounds being nondecreasing, the generating functions for tableaux can be given in determinantal form. Let a a a, bbb be arbitrary r-tupels of integers and ccc, d d d be arbitrary λ_{1}-tupels of integers only satisfying a a a ≥ bbb and ccc ≥ d d d. We want to compute the generating function for tableaux of shape λ λ λ/μ μ μ where the parts in row i are at most a_{i} and at least b_{i}, and the parts in column j are at most c_{j} and at least d_{j}. Since now a formula for the entries of the resulting determinant would involve very clumsy expressions, it is more convenient to only give a rough description of the procedure which finally leads to the determinantal formula. Moreover, as will be seen later, it is better not to rigorously stick to a formula because very often in the last step of this procedure the size of the determinant can be significantly reduced, which would not be observed when a general formula is directly used.

Let us give a sketch of this procedure, which is performed in four steps. First, consider the case λ λ λ = (5, 4, 3), μ μ μ = (2, 0, 0), a a a = (14, 10, 13), bbb = (4, 1, 4), ccc = (6, 8, 16, 15, 12), d d d = (2, 7, 1, 7, 5) which is illustrated on the left-hand side of Figure 4.

\begin{aligned}& 2 ≤ & 7 ≤ & 1 ≤ & 7 ≤ & 5 ≤ \\ 4 ≤ & & & & & & ≤ 14 \\ 1 ≤ & & & & & & ≤ 10 \\ 4 ≤ & & & & & & ≤ 13 \\ & ≤ 6 & ≤ 8 & ≤ 16 & ≤ 15 & ≤ 12 \end{aligned} ⟶^{first step} \begin{aligned}& 2 ≤ & 7 ≤ & 4 ≤ & 7 ≤ & 7 ≤ \\ 4 ≤ & & & & & & ≤ 12 \\ 2 ≤ & & & & & & ≤ 10 \\ 4 ≤ & & & & & & ≤ 13 \\ & ≤ 6 & ≤ 8 & ≤ 13 & ≤ 10 & ≤ 12 \end{aligned}

Figure 4

Obviously, some entries in a a a, bbb, ccc, or d d d, respectively, could be replaced by greater respectively smaller ones without changing the set of tableaux obeying these bounds. For example, d_{5} = 5 could be replaced by 7, a_{1} = 14 by 12, etc. Formally, we may replace a a a by ā a a, bbb by b̄bb, …, where

ā_{i} = \{ \begin{matrix}min\{a_{i}, a_{i+1}, …, a_{λ′_{λi}} \} & λ_{i+1} = λ_{i} \\ min\{a_{i}, c_{λ_{i}}\} & λ_{i+1} < λ_{i} \end{matrix} , b̄_{i} = \{ \begin{matrix}max\{b_{μ′_{μi} +1}, …, b_{i−1}, b_{i}\} & μ_{i−1} = μ_{i} \\ max\{b_{i}, d_{μ_{i}+1}\} & μ_{i−1} > μ_{i} \end{matrix} ,

c̄_{i} = \{ \begin{matrix}min\{c_{i}, c_{i+1}, …, c_{λ_{λ′i}} \} & λ′_{i+1} = λ′_{i} \\ min\{c_{i}, a_{λ′_{i}}\} & λ′_{i+1} < λ′_{i} \end{matrix} , d̄_{i} = \{ \begin{matrix}max\{d_{μ_{μ′i} +1}, …, d_{i−1}, d_{i}\} & μ′_{i−1} = μ′_{i} \\ max\{d_{i}, b_{μ′_{i}+1}\} & μ′_{i−1} > μ′_{i} \end{matrix} .

In our example, this normalization of the bounds is displayed on the right-hand side of Figure 4.

In the second step, tableaux of shape λ λ λ/μ μ μ obeying ā a a, b̄bb, c̄cc, d̄ d d are interpreted as families of lattice paths as was done before in order to prove Theorem 1.

2 ≤ 7 ≤ 4 ≤ 7 ≤ 7 ≤
4 ≤  4  9  9 ≤ 12
2 ≤ 3 7  7  10  ≤ 10
4 ≤ 4 8  8  ≤ 13
≤ 6 ≤ 8 ≤ 13 ≤ 10 ≤ 12

↓ second step

• _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • • • • • • • • • • • • • • • •^{3} ^{7} ^{7} ^{10}^{4} ^{9} ^{9}^{4} ^{8} ^{8}  ⟶^{third step} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•} _{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•}^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} ^{•} • • • • • • • • • • • • • • • • • • • • • •^{3} ^{7} ^{7} ^{10}^{4} ^{9} ^{9}^{4} ^{8} ^{8}^{(} ^{)}^{(} ^{)}^{(} ^{)}^{(} ^{)} ^{(} ^{)}^{(} ^{)}^{(} ^{)}

Figure 5

But now there are not enough dummy paths to guarantee that every family of nonintersecting paths corresponds to a tableaux of the desired type. Therefore, in the third step we have to insert additional dummy paths to build up “barriers” at some places. Let us consider the starting points S_{i}, S_{i+1} of the paths P_{i}, P_{i+1} which correspond to the i’th and (i + 1)’th row of the tableau, respectively. Depending on which of the relations μ_{i} = μ_{i+1}, b̄_{i} ≤ b̄_{i+1}, d̄_{μ_{i}} ≤ b̄_{i} hold or not, we obtain four cases which schematically are described in Figure 6.

• •^{S_{i+1}}_{S_{i}}_{Case 1: μ_{i}=μ_{i+1}, b̄_{i}≤b̄_{i+1}} •  • • • • • ∘ ∘ ∘ ∘ ∘^{S_{i+1}}  _{S_{i}}_{Case 2: μ_{i}>μ_{i+1}, d̄_{μ_{i}} >b̄_{i}≤b̄_{i+1}}

•  •_{S_{i+1}}  ^{S_{i}} • • • ∘ ∘ ∘ ∘ ∘ ∘ ∘ ∘_{Case 3: d̄_{μ_{i}} ≤b̄_{i}>b̄_{i+1}}  •  •_{S_{i+1}}  ^{S_{i}} • • • • ∘ ∘ ∘ ∘ ∘ ∘ ∘_{Case 4: d̄_{μ_{i}} >b̄_{i}>b̄_{i+1}}

Figure 6

The boldface dots different from S_{i} and S_{i+1} indicate the dummy paths which were inserted during Step 2. The circles indicate the dummy paths which have to be added to build up barriers which prevent P_{i+1} from going below P_{i} or not obeying d d d, respectively. Only in Case 1 nothing has to be done. Considering the end points of P_{i} and P_{i+1}, dummy paths are added in an analogous manner in order to guarantee that the corresponding tableau is of the desired type. The result of this third step applied to our example is the family of paths on the right-hand side of Figure 5.

Finally, in the fourth step we look after paths which are superflous. These subsequently are dropped. In the right-hand side family of lattice paths in Figure 5 the superflous paths are put into parentheses. (It should be observed that paths should only be dropped sequentially because the same path could be superflous with respect to some set of paths which already has been dropped but not superflous with respect to another set. There can be several different sets of paths which can be legitimately dropped. One will choose that one which causes the corresponding determinant to become as “small” as possible.)

Now Proposition 1 can be applied thus again obtaining a determinant for the generating function. In our running example (Figures 4,5) this procedure yields that there are 17.163 tableaux of the desired type, the norm generating function of which is given by

q^{62}+6 q^{63}+21 q^{64}+55 q^{65}+118 q^{66}+221 q^{67}+372 q^{68}+572 q^{69}+812 q^{70}+1072 q^{71}+1322 q^{72}+1530 q^{73}
+1665 q^{74}+1707 q^{75}+1650 q^{76}+1503 q^{77}+1290 q^{78}+1041 q^{79}+789 q^{80}+561 q^{81}+373 q^{82}+231 q^{83}
+132 q^{84}+69 q^{85}+32 q^{86}+13 q^{87}+4 q^{88}+q^{89}.

Of course, with the help of this procedure the norm generating function for (α, β)- plane partitions or (α, β)-reverse plane partitions of shape λ λ λ/μ μ μ which obey arbitrary a a a, bbb, ccc, d d d, can also be computed by transforming the problem to the corresponding tableaux problem.

References

1. I. Z. Chorneyko, L. K. K. Zing, K-sample analogues of two-sample Kolmogorov–Smirnov stastistics, Selecta Statistica Canadiana 6 (1982), 37–62.

2. W. Chu, Dominance method for plane partitions. IV: Enumeration of flagged skew tableaux, Linear and Multilinear Algebra 28 (1990), 185–191.

3. Gessel, I., G. Viennot, Binomial determinants, paths, and hook length formulae, Adv. in Math. 58 (1985), 300–321.

4. I. Gessel, G. Viennot, Determinants, paths, and plane partitions, preprint, 1989.

5. C. Krattenthaler, Generating functions for plane partitions of a given shape, Manuscripta Math. 69 (1990), 173–202.

6. I. G. Macdonald, Symmetric Functions and Hall Polynomials, Oxford University Press, New York/London, 1979.

7. S. G. Mohanty, Lattice path counting and applications, Academic Press, New York, 1979.

8. L. K. K. Zing, K-sample analogues of Kolmogorov–Smirnov statistics and group tests, Ph. D. Thesis, McMaster University, 1978.

9. M. Wachs, Flagged Schur functions, Schubert polynomials, and symmetrizing operators, J. Combin. Theory A 40 (1985), 276–289.

1991 Mathematics subject classifications: Primary 05A15; Secondary 05A17, 05E10, 11P81. Keywords and phrases: tableaux, generating functions, plane partitions, nonintersecting lattice

paths.