Two Approaches to Normal Order Coefficients

Richell O. Celeste

Institute of Mathematics and Natural Sciences Research Institute

University of the Philippines — Diliman Quezon City, Philippines 1101

                 ching@math.upd.edu.ph

Roberto B. Corcino Mathematics Department Cebu Normal University Cebu City, Philippines 6000

                  rcorcino@yahoo.com

Ken Joffaniel M. Gonzales Department of Physical Sciences and Mathematics University of the Philippines — Manila Manila, Philippines 1004

                 kmgonzales@upd.edu.ph

Abstract

We consider the normal ordering coefficients of strings consisting of the symbols V, U which satisfy the commutation rule UV − qV U = hV^{s}. These coefficients are studied using two approaches. First, we continue the study by Varvak, where the coefficients were interpreted as q-rook numbers under the row creation rook model introduced by Goldman and Haglund. Second, we express the coefficients in terms of a kind of generalization of some symmetric functions. We derive identities involving the coefficients including some explicit formulas.

1 Introduction

Let V, U be operators (or variables) that satisfy the commutation rule UV − qV U = hV^{s}, where s ∈ ℕ and h, q ∈ ℝ. For example, if s = 0, h = 1, q = 1, then V, U, respectively, can be represented by the creation operator and annihilation operator in quantum physics [1], or by the operators X, ∂_{x} whose action on a monomial x^{n} are given by Xx^{n} = x^{n+1} and ∂_{x}x^{n} = nx^{n−1}. Given a string w consisting of V ’s and U’s, the normally ordered form of w is an equivalent operator expressed as a sum ∑ c_{i,j}V^{i}U^{j}. The normally ordered form can be computed using the commutation rule alone, i.e., by replacing all occurrences of UV with qV U + hV^{s}, but this task can be cumbersome especially for long strings. It turns out that the coefficients c_{i,j}, called normal ordering coefficients, can be computed more efficiently using combinatorial techniques. In the classical case s = 0, h = 1, q = 1, Navon [7] showed that the normal ordering coefficients of an arbitrary string are given by rook numbers on a Ferrers board. Varvak [8] generalized Navon’s result for arbitrary q and derived explicit formulas for these coefficients using rook factorization. Blasiak [1], El-Desouky et al. [2], and Mansour et al. [4, 5] also computed explicit formulas using other methods.

In this paper, we study normal ordering coefficients using two approaches. In Section 2, we study the coefficients as q-rook numbers under the row creation rule introduced by Goldman and Haglund [3]. In Section 3, we study the coefficients by expressing them in terms of some generalization of elementary and complete homogeneous symmetric functions. Lastly, some special cases are given in Section 4.

2 First approach: rook numbers

Let v = (v_{1}, v_{2}, …, v_{n}), u = (u_{1}, u_{2}, …, u_{n}), and H_{v,u} = V^{v_{n}}U^{u_{n}} ⋯ V^{v_{2}}U^{u_{2}}V^{v_{1}}U^{u_{1}}. In this section, we obtain explicit formulas for the normal ordering coefficients of H_{v,u} which uses the known rook theoretic interpretation directly. We also give a representation of V, U in terms of linear operators and use it to find another explicit formula which generalizes Varvak’s [8, Corollary 4.2].

Following Blasiak [1], we write the string H_{v,u} in the form

H_{v,u} = ∑_{k=u_{1}}^{|u|} S_{s,h;q}^{v,u}[k] V^{|v|−(|u|−k)(1−s)}U^{k} ,  (1)

where |u| = u_{1} + u_{2} + ⋯ + u_{n} and |v| = v_{1} + v_{2} + ⋯ + v_{n}.

Varvak [8] showed that for h = 1, q = 1, the coefficients S_{s,h;q}^{v,u}[k] also occur as rook numbers under the rook model introduced by Goldman and Haglund [3] which we now describe. An s-rook placement on a Ferrers board B is obtained as follows. First, choose the columns where rooks will be placed. The rooks are then placed one by one from the right such that every time a rook is placed in a cell the entire row to its left is divided into s rows. When s = 0, “division” into s rows can be interpreted as cancellation of the entire row lying to the left of a rook. Denote by R_{s}(B, k) the set of all placements of k rooks on B. An example of a rook placement where s = 2 is shown in Figure 1. The k-th s-rook number of a board B is then defined as R_{s}(B(w), k) = |R_{s}(B, k)|.

Figure 1: A placement of 3 rooks.

Varvak [8, Theorem 7.1] showed, in our notation (and after correcting for the typo pointed out by Mansour et al. [4]), that

H_{v,u} = ∑_{k=0}^{|u|−u_{1}} R_{s,1;1}[B(H_{v,u}), k] V^{|v|−k(1−s)}U^{|u|−k}.  (2)

Comparing (2) with (1) gives S_{s,1;1}^{v,u}[k] = R_{s,1;1}[B(H_{v,u}), |u| − k].

The connection between rook numbers and normal ordering lies on the fact that a string w determines a unique Ferrers board (where a column or row is allowed to have length zero) and that the placement or non-placement of a rook corresponds to the choice of replacement for each occurrence of UV. Specifically, a string w outlines a Ferrers board B(w) whose underside border is the lattice path obtained from w by replacing V with a unit step up and U with a unit step to the right. For example, the Ferrers board in Figure 1 is outlined by V UV UUV V UV V U. Placing a rook on the northeast inner corner of B(w) corresponds to replacing the rightmost UV with hV^{s} while leaving a cell empty corresponds to replacing UV with qV U. Under this correspondence, it is now clear how Varvak’s result can be extended to arbitrary q. Given a rook placement ϕ, assign the weight w(ϕ) = h^{t′}q^{t} where t′ is the number of rooks, and t is the number of cells not containing a rook and not lying above a rook if s ≠ 0 and t is the number of cells not containing a rook and not lying above or to the left of a rook if s = 0. For example, the rook placement in Figure 1 has weight h^{3}q^{11}. We define the generalized rook numbers by

R_{s,h;q}[B, k] = ∑_{ϕ∈R_{s}(B,k)} w(ϕ).

When all three parameters s, h, q are arbitrary, the normally ordered form of the string H_{v,u} is then given by

H_{v,u} = ∑_{k=0}^{|u|−u_{1}} R_{s,h;q}[B(H_{v,u}), k] V^{|v|−k(1−s)}U^{|u|−k}.  (3)

Again, comparing (3) with (1) gives S_{s,h;q}^{v,u}[k] = R_{s,h;q}[B(H_{v,u}), |u| − k].

Our first result gives the normally ordered form of strings of the form U^{m}V^{l}. The following notation will be used. For n ∈ ℕ, let [n]_{q} = 1 + q + q^{2} + ⋯ + q^{n−1} if n > 0 and [0]_{q} = 0. Let [n]_{q}! = [n]_{q}[n − 1]_{q} ⋯ [2]_{q}[1]_{q} for n > 0 and [0]_{q}! = 1. The q-binomial coefficient is defined by \left[{n \atop k}\right]_{q} = \frac{[n]_{q}!}{[k]_{q}![n−k]_{q}!}. They satisfy the property (see [6, Table 1 and Identity 2.2])

\left[{n \atop k}\right]_{q} = ∑_{0≤i_{1}≤i_{2}≤...≤i_{n−k}≤k} q^{i_{1}+i_{2}+···+i_{n−k}} .  (4)

Theorem 1. For s ∈ ℕ, the normally ordered form of U^{m}V^{l} is given by

U^{m}V^{l} = ∑_{j=0}^{m} (h^{j}q^{l(m−j)}\left[{m \atop j}\right]_{q^{s−1}} ∏_{i=0}^{j−1}[l + i(s − 1)]_{q}) V^{l+j(s−1)}U^{m−j}.  (5)

Proof. The string U^{m}V^{l} outlines a rectangular Ferrers board with m columns and l rows. The total weight of all placements of j rooks on this board equals the coefficient of V^{l+j(s−1)}U^{m−j} in the normally ordered form of U^{m}V^{l}. We now compute the total weight of such rook placements as follows. Choose j columns where rooks will be placed. If the first rook is placed on the cell in the ith row, 1 ≤ i ≤ l, then the cells below the rook will contribute a weight of q^{i−1}. As i varies, a total weight of h(1 + q + ⋯ + q^{l−1}) = h[l]_{q} will be contributed by all possible placements of the first rook. Since the placement of the first rook adds s − 1 subcells to every cell to its left, the total weight contributed by all possible placement of the second rook is [l + (s − 1)]_{q}. Continuing this process with the other columns, we see that the weight contributed by all possible placements of j rooks in the chosen columns is h^{j} ∏_{i=0}^{j−1}[l + i(s − 1)]_{q}, and that this weight is the same for any choice of j columns.

We now consider the weight contributed by the other columns in which no rooks are placed. For such a column, the weight is completely determined by the number of columns to its right that contains a rook, i.e., if there are t columns to its right containing a rook, then the column will assume a weight of q^{l+t(s−1)}. Note that t varies from 0 to j and that for a given placement of j rooks, the weight contributed by all the columns containing no rooks is q^{lt_{0}}q^{(l+(s−1))t_{1}}q^{(l+2(s−1))t_{2}} ⋯ q^{(l+j(s−1))t_{j}} for some t_{0} + t_{1} + ⋯ + t_{j} = m − j. Summing this up over all such possible collections {t_{0}, t_{1}, …, t_{i}}, we have

∑_{t_{0}+t_{1}+···+t_{j}=m−j}q^{(l+0(s−1))t_{0}}q^{(l+1(s−1))t_{1}}q^{(l+2(s−1))t_{2}} ⋯ q^{(l+j(s−1))t_{j}}

= q^{l(m−j)} ∑_{t_{0}+t_{1}+···+t_{j}=m−j} q^{0(s−1)t_{0}}q^{1(s−1)t_{1}}q^{2(s−1)t_{2}} ⋯ q^{j(s−1)t_{j}}

= q^{l(m−j)} ∑_{0≤i_{1}≤i_{2}≤...≤i_{m−j}≤j} q^{(s−1)(i_{1}+i_{2}+···+i_{m−j})}

= q^{l(m−j)}\left[{m \atop j}\right]_{q^{s−1}} ,

where the last equality follows from (4). This proves the theorem.

Corollary 2. Let s ∈ ℕ. The string H_{v,u} may be written as

H_{v,u} = ∑_{j_{1}=0}^{u_{2}} ∑_{j_{2}=0}^{u_{3}} ⋯ ∑_{j_{n−1}=0}^{u_{n}} ∏_{i=1}^{n−1} h^{j_{1}+···+j_{n−1}}Γ_{q,s}[j_{i}, v_{1} + ⋯ + v_{i} + (j_{1} + ⋯ + j_{i−1})(s − 1), u_{i+1}]_{q}

V^{v_{1}+···+v_{n}+(j_{1}+···+j_{n−1})(s−1)}U^{u_{1}+···+u_{n}−(j_{1}+···+j_{n−1})}. (6)

where

Γ_{q,s}[j, l, m] = q^{l(m−j)}\left[{m \atop j}\right]_{q^{s−1}} ∏_{i=0}^{j−1}[l + i(s − 1)]_{q}.

Hence, the numbers S_{s,h;q}^{v,u}[k] are given by

S_{s,h;q}^{v,u}[k] = h^{|u|−k} ∑_{j_{1}+···+j_{n−1}=u_{1}+···+u_{n}−k} ∏_{i=1}^{n−1} Γ_{q,s}[j_{i}, v_{1}+⋯+v_{i}+(j_{1}+⋯+j_{i−1})(s−1), u_{i+1}]. (7)

Proof. Identity (6) is proved by repeated application of (5) beginning from U^{u_{2}}V^{v_{1}}. Identity (7) follows by comparing the coefficient of U^{k} in (6) and (1).

We note that the case s = 0, h = 1, q = 1 of Corollary 2 was derived by El Desouky et al. [2] using the Leibniz formula.

Corollary 3. Let s ∈ ℕ and set v = u = (\underbrace{1, 1, …, 1}_{n}). Then the following explicit formula

for S_{s,h;q}^{v,u}[k] holds

S_{s,h;q}^{v,u}[k] = h^{n−k} ∑_{j_{1}+···+j_{n−1}=n−k} ∏_{i=1}^{n−1} q^{(i+(j_{1}+···+j_{i−1})(s−1))(1−j_{i})}\left[{i + (j_{1} + ⋯ + j_{i−1})(s − 1) \atop j_{i}}\right]_{q}.

Varvak’s [8] use of rook factorization to obtain an explicit formula adapts readily in the case of S_{s,h;q}^{v,u}[k] after some modification. We will need the following analogues of the falling

factorial and factorial: for r ∈ ℝ, j ∈ ℕ, define [r]_{q,1−s}^{(\underline{j})} = [r(1 − s)]_{q}[(r − 1)(1 − s)]_{q} ⋯ [(r − j + 1)(1 − s)]_{q} and for n ∈ ℕ, define [n]_{q,1−s}! = [n]_{q,1−s}^{(\underline{n})}.

Theorem 4. Let s ≠ 1. The coefficients S_{s,h;q}^{v,u}[k] satisfy the explicit formula

S_{s,h;q}^{v,u}[k] = \frac{h^{|u|−k}}{[k]_{q,1−s}!} ∑_{j=0}^{k}(−1)^{k−j}q^{\binom{k−j}{2}(1−s)}\left[{k \atop j}\right]_{q^{1−s}}Ω_{s;q}^{v,u}[j],

where

Ω_{s;q}^{v,u}[j] = ∏_{t=1}^{n}[j − (u_{1} + u_{2} + ⋯ + u_{t−1}) + (v_{1} + v_{2} + ⋯ + v_{t−1})/(1 − s)]_{q,1−s}^{(\underline{u_{t}})}.

Proof. We use a representation of V, U as linear operators whose action on the monomial t^{j} is given by V t^{j} = t^{j+1} and Ut^{j} = h[j]_{q}t^{j+s−1}. One can verify that these operators satisfy V U − qV U = hV^{s} and that U^{k}t^{n(1−s)} = h^{k}[n]_{q,1−s}^{(\underline{k})}t^{(n−k)(1−s)}. We then apply both sides of (1) to t^{x(1−s)}. After letting t = 1 to the resulting equation and using the property [x]_{q,1−s}^{(\underline{k})} = [1 − s]_{q}^{k}[x]_{q^{1−s}}[x − 1]_{q^{1−s}} ⋯ [x − k + 1]_{q^{1−s}}, we obtain

h^{|u|}Ω_{s;q}^{v,u}[x] = ∑_{k=u_{1}}^{|u|} h^{k}S_{s,h;q}^{v,u}[k][1 − s]_{q}^{k}[x]_{q^{1−s}}[x − 1]_{q^{1−s}} ⋯ [x − k + 1]_{q^{1−s}}.

Let E denote the shift operator EP (x) = P (x+1) and Δ_{Q}^{k} the k-th Q-difference operator defined by Δ_{Q}^{k} = (E − 1)(E − Q) ⋯ (E − Q^{k−1}). If P (x) = ∑_{k} p_{k}[x]_{Q}[x − 1]_{Q} ⋯ [x − k + 1]_{Q},

then p_{k} = \frac{1}{[k]_{Q}!}Δ_{Q}^{k}P (x)|_{x=0}. By the q-binomial theorem, Δ_{Q}^{k} = ∑_{j=0}^{k}(−1)^{j}Q^{\binom{j}{2}}\left[{k \atop j}\right]_{Q}E^{k−j}.

The result then follows by letting Q = q^{1−s}, p_{k} = h^{k}S_{s,h;q}^{v,u}[k][1 − s]_{q}^{k} and P (x) = h^{|u|}Ω_{s;q}^{v,u}[x].

Corollary 5. Let s ∈ ℕ\\{0, 1\}. If v = u = (\underbrace{1, 1, …, 1}_{n}), then the numbers S_{s,h;q}^{v,u}[k] have the

following explicit formula

S_{s,h;q}^{v,u}[k] = \frac{h^{n−k}[s]_{q}^{n}}{[k]_{q^{1−s}}![1 − s]_{q}^{k}} ∑_{j=0}^{k}(−1)^{k−j}q^{\binom{k−j}{2}(1−s)}\left[{k \atop j}\right]_{q^{1−s}} ∏_{t=1}^{n}[(j/s) + t − j − 1]_{q^{s}}.

When s = 0,

S_{0,h;q}^{v,u}[k] = \frac{h^{n−k}}{[k]_{q}!} ∑_{j=0}^{k}(−1)^{k−j}q^{\binom{k−j}{2}}\left[{k \atop j}\right]_{q}[j]_{q}^{n}.

Theorem 4 can be used to derive a Dobinsky formula for the Bell numbers corresponding to S_{s,h;q}^{v,u}[k]. Define the generalized q-Bell polynomials B_{s,h;q}^{v,u}[x] and generalized q-Bell numbers B_{s,h;q}^{v,u} by

B_{s,h;q}^{v,u}[x] = ∑_{k=u_{1}}^{|u|} S_{s,h;q}^{v,u}[k]x^{k}, B_{s,h;q}^{v,u} = B_{s,h;q}^{v,u}[1].

When s = 0, h = 1, q = 1 and the associated string H_{v,u} outlines a staircase board, i.e., when v = u = (\underbrace{1, 1, …, 1}_{n}), the numbers B_{s,h;q}^{v,u}[x] and B_{s,h;q}^{v,u} reduce to the usual Bell polynomial

B(n; x) and Bell number B(n), respectively. The classical Dobinsky formula is given by

B(n; x) = \frac{1}{e^{x}} ∑_{j=0}^{∞} j^{n} \frac{x^{j}}{j!} .

The Dobinsky formula corresponding to B_{s,h;q}^{v,u}[x] is as follows.

Corollary 6. Let s ∈ ℕ\{1} and Ω_{s;q}^{v,u}[j] be as in Theorem 4. Then,

B_{s,h;q}^{v,u}[x] = (∑_{j=0}^{∞} h^{|u|−j}(−1)^{j}q^{\binom{j}{2}(1−s)} \frac{x^{j}}{[j]_{q,1−s}!}) (∑_{j=0}^{∞} Ω_{s;q}^{v,u}[j]\frac{x^{j}}{h^{j}[j]_{q,1−s}!}) .

Proof. Using Theorem 4, the property S_{s,h;q}^{v,u}[k] = 0 when |u| < k < u_{1} and the property \left[{k \atop j}\right]_{q^{1−s}} = \frac{[k]_{q,1−s}!}{[j]_{q,1−s}![k−j]_{q,1−s}!}, respectively, we have

B_{s,h;q}^{v,u}[hx] = ∑_{k=u_{1}}^{|u|} S_{s,h;q}^{v,u}[k]h^{k}x^{k}

= ∑_{k=0}^{∞} ∑_{j=0}^{k} \frac{h^{|u|}}{[k]_{q,1−s}!}(−1)^{k−j}q^{\binom{k−j}{2}(1−s)}\left[{k \atop j}\right]_{q^{1−s}}Ω_{s;q}^{v,u}[j]x^{k}

= ∑_{k=0}^{∞} ∑_{j=0}^{k} (\frac{h^{|u|}(−1)^{k−j}q^{\binom{k−j}{2}(1−s)}}{[k − j]_{q,1−s}!} ) (\frac{Ω_{s;q}^{v,u}[j]}{[j]_{q,1−s}!}) x^{k}.

The desired result is then obtained after replacing x with x/h and by using the Cauchy product rule.

3 Second approach: generalized symmetric functions

In this section, we derive formulas for S_{s,h;q}^{v,u}[k] by showing that it can be expressed in terms of a certain generalization of some symmetric functions. Our derivation will involve the following shift in notation. Let w = H_{v,u}. Label the columns of B(w) from the right by 0, 1, 2, …, |u| − 1 and let w_{i} be the length of the column labeled i. Let B_{0}(w) = ∅ and for n = 1, 2, …, |u| − 1, let B_{n}(w) be the Ferrers board whose column lengths are w_{0}, w_{1}, w_{2} …, w_{n−1}. Finally, define S_{s,h;q}^{w}[n, k] = R_{s,h;q}[B_{n}(w), n − k].

Theorem 7. Let n = 0, 1, 2, …, |u| − 1, k ≤ n. The rook numbers R_{s,h;q}[B_{n}(w), k] satisfy the recurrence relation

R_{s,h;q}[B_{n}(w), k] = q^{w_{n−1}+k(s−1)}R_{s,h;q}[B_{n−1}(w), k] + h[w_{n−1} + (k − 1)(s − 1)]_{q} R_{s,h;q}[B_{n−1}(w), k − 1] (8)

with boundary conditions R_{s,h;q}[B_{n}(w), n] = ∏_{i=0}^{n−1}[w_{i} + (i − 1)(s − 1)]_{q} and R_{s,h;q}[B_{0}(w), 0] = R_{s,h;q}[B_{n}(w), 0] = 1.

Proof. The identity can be proved by induction but a combinatorial proof appears to be more straightforward. Divide the set R(B(w), k) into two, with the first set consisting of rook placements without a rook in the m-th column and the other set consisting of rook placements with a rook in m-th column. The sum of the weights of all rook placements in the first set is q^{w_{n−1}+k(s−1)}R_{s,h;q}[B_{n−1}(w), k] while that of the second set is h[w_{n−1} + (k − 1)(s − 1)]_{q}R_{s,h;q}[B_{n−1}(w), k − 1].

From Equation (8), we have

S_{s,h;q}^{w}[n, k] = q^{w_{n−1}+(n−k)(s−1)}S_{s,h;q}^{w}[n − 1, k − 1] + h[w_{n−1} + (n − k − 1)(s − 1)]_{q}S_{s,h;q}^{w}[n − 1, k]. (9)

Now, multiply both sides of (9) by q^{(s−1)\binom{k+1}{2}−(s−1)\binom{n+1}{2}−∑_{i=0}^{n−1} w_{i}} and let

s_{n,k} = q^{(s−1)\binom{k+1}{2}−(s−1)\binom{n+1}{2}−∑_{i=0}^{n−1} w_{i}}S_{s,h;q}^{w}[n, k].

Equation (9) then becomes

s_{n,k} = s_{n−1,k−1} + hq^{s} ([w_{n−1} + (n − 1)(s − 1)]_{1/q} − [k(s − 1)]_{1/q}) s_{n−1,k}.

This shows that the numbers s_{n,k}, and hence S_{s,h;q}^{w}[n, k], can be studied under a more general setting. (A similar observation was made by Mansour et al. [5] in the case of the normal ordering coefficients of (V U)^{n}.) Specifically, let α = (α_{0}, α_{1}, …) and w = (β_{0}, β_{1}, …) be sequences (or equivalently, weight functions) and define the numbers A_{n,k}^{α,β} by the recurrence relation

A_{n,k}^{α,β} = A_{n−1,k−1}^{α,β} + (α_{n−1} + β_{k})A_{n−1,k}^{α,β},  (10)

with initial conditions A_{0,n}^{α,β} = δ_{0,n} and A_{n,0}^{α,β} = (α_{n−1}+β_{0})(α_{n−2}+β_{0}) ⋯ (α_{0}+β_{0}). When only the value of a weight function at i = 0, 1, 2, … is specified (for instance, α_{i}), it is understood that the corresponding weight function is the same letter in boldface without the subscript.

In the theorem that follows, we denote the matrix whose (n, k) entry is M_{n,k} by [M_{n,k}]. The zero weight function is denoted 0 = (0, 0, …). The matrices are all assumed to be square.

Theorem 8. There holds the matrix factorization [A_{n,k}^{α,β}] = [A_{n,k}^{α,0}] [A_{n,k}^{0,β}]. Equivalently,

A_{n,k}^{α,β} = ∑_{j=k}^{n} A_{n,j}^{α,0}A_{j,k}^{0,β}.

Proof. By (10),

A_{n,j}^{α,0}A_{j,k}^{0,β} = (A_{n−1,j−1}^{α,0} + α_{n−1}A_{n−1,j}^{α,0})(A_{j−1,k−1}^{0,β} + β_{k}A_{j−1,k}^{0,β})
= A_{n−1,j−1}^{α,0}A_{j−1,k−1}^{0,β} + α_{n−1}A_{n−1,j}^{α,0}A_{j,k}^{0,β} + β_{k}A_{n−1,j−1}^{α,0}A_{j−1,k}^{0,β}

Hence, the numbers A_{n,k}^{α,β} viewed as the (n, k) entry of the matrix product [A_{n,k}^{α,0}] [A_{n,k}^{0,β}] satisfy the same recursion as the numbers defined by Equation (10).

The theorem that follows gives different formulations for the numbers A_{n,k}^{α,β} in terms of expressions that are analogous to elementary and complete symmetric functions.

Theorem 9. The following identities hold:

A_{n,k}^{α,β} = ∑_{0≤i_{1}<i_{2}<...<i_{n−k}≤n−1} ∏_{j=1}^{n−k}(α_{i_{j}} + β_{i_{j}−j+1})  (11)

A_{n,k}^{α,β} = ∑_{0≤i_{1}≤i_{2}≤...≤i_{n−k}≤k} ∏_{j=1}^{n−k}(α_{i_{j}+j−1} + β_{i_{j}})  (12)

A_{n,k}^{α,β} = ∑_{i_{0}+i_{1}+i_{2}+···+i_{k}=n−k} ∏_{j=0}^{k} ∏_{l=0}^{i_{j}−1}(α_{j+l+i_{0}+i_{1}+i_{2}+···+i_{j−1}} + β_{j}).  (13)

Proof. It can be shown by partitioning the set of indices that the RHS of (11) and (12) satisfy the recursion (10). Identity (13) is a restatement of (12).

Let H be a set. The m-th elementary symmetric function e and m-th complete symmetric function h are defined as follows: e_{m}(H) (resp. h_{m}(H)) is the sum of all products of m elements from H taken without (resp. with) replacement. Observe that by (11), A_{n,k}^{α,0} = e_{n−k}({α_{0}, α_{1}, …, α_{n−1}}) and by (12) or (13), A_{n,k}^{0,α} = h_{n−k}({α_{0}, α_{1}, …, α_{k}}). This shows that the numbers A_{n,k}^{α,0} and A_{n,k}^{0,α} are exactly the U-Stirling numbers studied by Medicis and Leroux [6] which they defined in terms of A-tableaux.

We now give an interpretation for A_{n,k}^{α,β} in terms of certain lattice paths which reduces to the A-tableau interpretation for A_{n,k}^{α,0} and A_{n,k}^{0,β}. Let m, m′ ∈ ℕ and denote by L(m, m′) the set of pairs of lattice paths (λ, λ′) on an m by m′ grid consisting of unit left (L) and unit up (U) steps beginning from the origin (the lower left corner of the grid) such that λ contains no two consecutive L’s and such that λ′ is the lattice path obtained from λ by replacing every occurrence of UL by L. Figure 2 shows an example of a pair of lattice path in L(6, 5) where λ is the lattice path in bold lines and λ′ is the lattice path in dotted lines.

Figure 2: A pair of lattice paths in L(6, 5)

Given a weight function γ, we assign to a lattice path λ^{∗} with m^{∗} L’s the weight γ(λ^{∗}) = ∏_{i=1}^{m^{∗}} γ_{λ_{i}^{∗}} where the λ_{i}^{∗}’s are the second coordinates of the L’s of λ^{∗}. For instance, the lattice path in bold lines in Figure 2 has weight γ_{0}γ_{1}γ_{2}γ_{4}γ_{6}. The next theorem gives the interpretation of A_{n,k}^{α,β} in terms of lattice paths and follows directly from Equation (11) of Theorem 9.

Theorem 10. The following interpretation for A_{n,k}^{α,β} holds

A_{n,k}^{α,β} = ∑_{(λ,λ′)∈L(n−1,n−k)} (α(λ) + β(λ′)) .

Going back to S_{s,h;q}^{w}[n, k], the discussion in the beginning of this section shows that if α_{i} = hq^{s}[w_{i} + i(s − 1)]_{1/q}, β_{i} = −hq^{s}[i(s − 1)]_{1/q}, then

q^{(s−1)\binom{k+1}{2}−(s−1)\binom{n+1}{2}−∑_{i=0}^{n−1} w_{i}}S_{s,h;q}^{w}[n, k] = A_{n,k}^{α,β}.  (14)

If w = H_{v,u} where B(w) has n = |u| columns, then S_{s,h;q}^{w}[n, k] = S_{s,h;q}^{v,u}[k]. This shows that properties of S_{s,h;q}^{v,u}[k] can be easily lifted from the properties of A_{n,k}^{α,β}.

Theorem 11. Let n = |u|. Then the numbers S_{s,h;q}^{v,u}[k] satisfy the formula

S_{s,h;q}^{v,u}[k] = f(n, k)h^{n−k} ∑_{i,j,l}(−1)^{j−l}A_{n,j}^{ρ,0}\binom{j}{i}\binom{i}{l}\left[{l \atop k}\right]_{q^{1−s}},

where f_{q}(n, k) = q^{2(s+1)(n−k)−(s−1)\binom{k+1}{2}+(s−1)\binom{n+1}{2}−∑_{i=0}^{n−1} w_{i}}(1 − q)^{−2(n−k)}, ρ is the weight function given by ρ_{i} = (1/q)^{w_{i}+i(s−1)} and w_{i} is the length of the (i + 1)-st column from the rights of the Ferrers board B(H_{v,w}). Hence,

H_{v,u} = ∑_{k=u_{1}}^{n} (f_{q}(n, k) ∑_{i,j,l} h^{n−k}(−1)^{j−l}A_{n,j}^{ρ,0}\binom{j}{i}\binom{i}{l}\left[{l \atop k}\right]_{q^{1−s}}) V^{|v|−(|u|−k)(1−s)}U^{k}.

Proof. For simplicity, let h = 1. We can easily recover the more general identity using the fact that S_{s,h;q}^{w}[n, k] = h^{n−k}S_{s,1;q}^{w}[n, k]. Define the weight functions α and β by α_{i} = q^{s}[w_{i} + i(s − 1)]_{1/q}, β_{i} = −q^{s}[i(s − 1)]_{1/q}. We first gather all the facts we will use. Also, let Q = 1/q by α_{i}^{∗} = Q^{w_{i}+i(s−1)} and β_{i}^{∗} = Q^{i(s−1)}. Then we can rewrite the weight functions as α_{i} = Q^{−s} \frac{α_{i}^{∗}−1}{Q−1}, β_{i} = −Q^{−s} \frac{α_{i}^{∗}−1}{Q−1}.

For an arbitrary weight function γ and constant c, Equations (11) and (12) imply that A_{n,k}^{cγ,0} = c^{n−k}A_{n,k}^{γ,0} and A_{n,k}^{0,cγ} = c^{n−k}A_{n,k}^{0,γ}, respectively. Furthermore, if γ_{i} = q^{i}, then A_{n,k}^{0,γ} = \left[{n \atop k}\right]_{q} by the recurrence (10) and the fact that \left[{n \atop k}\right]_{q} = \left[{n−1 \atop k−1}\right]_{q} + q^{k}\left[{n−1 \atop k}\right]_{q}. Using these facts and by the repeated use of Theorem 8,

A_{n,k}^{α,β} = (Q^{s}(Q − 1))^{−2(n−k)} ∑_{i} A_{n,i}^{α,0}A_{i,k}^{0,β}

= (Q^{s}(Q − 1))^{−2(n−k)} ∑_{i} A_{n,i}^{α^{∗},−1}A_{i,k}^{−1,β^{∗}}

= (Q^{s}(Q − 1))^{−2(n−k)} ∑_{i,j,l} A_{n,j}^{α^{∗},0}A_{j,i}^{0,−1}A_{i,l}^{−1,0}A_{l,k}^{0,β^{∗}}

= (Q^{s}(Q − 1))^{−2(n−k)} ∑_{i,j,l}(−1)^{j−l}A_{n,j}^{α^{∗},0}\binom{j}{i}\binom{i}{l}\left[{l \atop k}\right]_{Q^{s−1}}.

The theorem now follows from (14) and after letting ρ = α^{∗}.

We can use the previous theorem to obtain explicit formulas for the rook numbers of some special types of Ferrers boards studied by Goldman and Haglund [3]. If the columns lengths of the Ferrers board B(H_{v,u}) has column lengths 0, c, 2c, …, (|u| − 1)c, we call B(H_{v,u}) a c-jump board. If B(H_{v,u}) is an |u| × |u| Ferrers board, then we call B(H_{v,u}) an Abel board.

Corollary 12. Let n = |u| and let f_{q}(n, k) be as in Theorem 11. If w outlines a c-jump board, then

R_{s,h;q}[B(H_{v,u}), k] = f_{q}(n, n − k)h^{k} ∑_{i,j,l}(−1)^{j−l}q^{\binom{n−j}{2}(c+s−1)}\left[{n \atop j}\right]_{q^{1−s−c}} \binom{j}{i}\binom{i}{l}\left[{l \atop n − k}\right]_{q^{1−s}}.

On the other hand, if w outlines a d × |u| Ferrers board, then

R_{s,h;q}[B(H_{v,u}), k] = f_{q}(n, n − k)h^{k} ∑_{i,j,l}(−1)^{j−l}q^{−d(k)−\binom{n−j}{2}}\left[{n \atop j}\right]_{q^{1−s}} \binom{j}{i}\binom{i}{l}\left[{l \atop n − k}\right]_{q^{1−s}}.

The Abel board is the case where d = n.

4 Some Special Cases

In this section, we enumerate special cases of the normal ordering coefficients considered in Sections 2 and 3 for some strings, with h = 1, q = 1. We have verified that the OEIS sequences cited below are indeed the coefficients of the given strings by comparing their known recurrence relations with Equation (9). We have also included sequences whose recurrence relations are not given in the OEIS entry, but whose table of values match the ones we have generated. These sequences are marked with an asterisk, and it remains an open question if these sequences indeed occur as normal ordering coefficients. The name or short description of the sequences are also given when available.

String s  OEIS entry  Name or short description
(V U)^{n} −3  \underline{A265604} ^{∗}  Inverse Bell transform of quartic factorial numbers
(V U)^{n} −2  \underline{A265605} ^{∗}  Inverse Bell transform of the triple factorial numbers
(V U)^{n} −1  \underline{A122848} ^{∗}  Exponential Riordan array (1, x(1 + x/2))
(V U)^{n} 0  \underline{A008277}  Stirling numbers of the second kind
(V U)^{n} 1  \underline{A132393}  Stirling numbers of the first kind
(V U)^{n} 2  \underline{A001497}  Coefficients of Bessel polynomials
(V U)^{n} 3  \underline{A203412}
(V U)^{n} 4  \underline{A265606}^{∗}  Bell transform of the quartic factorial numbers
(V^{2}U)^{n} 0  \underline{A271703}  unsigned Lah numbers
(V^{3}U)^{n} 0  \underline{A035342}^{∗}  convolution matrix of \underline{A001147}
(V^{4}U)^{n} 0  \underline{A035469}  Bell transform of \underline{A007559} without column 0
(V^{2}U)^{n} 1 unsigned \underline{A039683}
(V^{3}U)^{n} 1 unsigned \underline{A051141}
(V^{4}U)^{n} 1 unsigned \underline{A051142}
(V^{2}U)^{n} 2  \underline{A004747}  Bell transform of \underline{A008544} without column 0.

5 Acknowledgment

The third author was supported in part by the Department of Science and Technology (DOST) through its ASTHRD Program. The research was also supported by the grant MAT-15-1-03 from the Natural Sciences Research Institute (NSRI), University of the Philippines Diliman. The support of these institutions are gratefully acknowledged.

References

[1] P. Blasiak, Combinatorics of boson normal ordering and some applications, Ph. D. thesis, University of Paris VI and Polish Academy of Sciences, 2005,

   http://arxiv.org/abs/quant-ph/0507206.

[2] B. S. El-Desouky, N. Cakić, and T. Mansour, Modified approach to generalized Stirling numbers via differential operators, Appl. Math. Lett. 23 (2010), 115–120.

[3] J. Goldman and J. Haglund, Generalized rook polynomials, J. Combin. Theory Ser. A 91 (2000), 509–530.

[4] T. Mansour, M. Schork, and M. Shattuck, On a new family of generalized Stirling and Bell numbers, Electron. J. Combin. 18 (2011), #P77.

[5] T. Mansour, M. Schork, and M. Shattuck, The generalized Stirling and Bell numbers revisited, J. Integer Sequences 15 (2012), Article 12.8.3.

[6] A. Médicis and P. Leroux, Generalized Stirling numbers, convolution formulae and p, qanalogues, Canad. J. Math. 47 (1995), 474–499.

[7] A. Navon, Combinatorics and fermion algebra, Nuovo Cimento 16 (1973) 324–330.

[8] A. Varvak, Rook numbers and the normal ordering problem, J. Combin. Theory Ser. A 112 (2005), 292–307.

2010 Mathematics Subject Classification: Primary 05A15; Secondary, 11B65, 11B73. Keywords: Stirling number, normal ordering, rook theory, Bell number, symmetric function.

(Concerned with sequences \underline{A001147}, \underline{A001497}, \underline{A004747}, \underline{A007559}, \underline{A008277}, \underline{A008544}, \underline{A035342}, \underline{A035469}, \underline{A039683}, \underline{A051141}, \underline{A051142}, \underline{A122848}, \underline{A132393}, \underline{A203412}, \underline{A265604}, \underline{A265605}, \underline{A265606}, and \underline{A271703}.)

Received August 22 2016; revised versions received October 16 2016; January 3 2017. Published in Journal of Integer Sequences, January 14 2017.

Return to Journal of Integer Sequences home page.