q-Vandermonde identity

In mathematics, in the field of combinatorics, the q-Vandermonde identity is a q-analogue of the Chu–Vandermonde identity. Using standard notation for q-binomial coefficients, the identity states that

\binom{m + n}{k}_{\!\!q} =\sum_{j} \binom{m}{k - j}_{\!\!q} \binom{n}{j}_{\!\!q} q^{j(m-k+j)}.

The nonzero contributions to this sum come from values of j such that the q-binomial coefficients on the right side are nonzero, that is, $max(0, k - m) \leq j \leq min(n, k).$

Other conventions

As is typical for q-analogues, the q-Vandermonde identity can be rewritten in a number of ways. In the conventions common in applications to quantum groups, a different q-binomial coefficient is used. This q-binomial coefficient, which we denote here by $B_q(n,k)$ , is defined by

B_q(n, k) = q^{-k(n-k)} \binom{n}{k}_{\!\!q^2}.

In particular, it is the unique shift of the "usual" q-binomial coefficient by a power of q such that the result is symmetric in q and $q^{-1}$ . Using this q-binomial coefficient, the q-Vandermonde identity can be written in the form

B_q(m + n,k)=q^{n k}\sum_{j}q^{-(m+n)j} B_q(m,k - j) B_q(n,j).

Proof

As with the (non-q) Chu–Vandermonde identity, there are several possible proofs of the q-Vandermonde identity. The following proof uses the q-binomial theorem.

One standard proof of the Chu–Vandermonde identity is to expand the product $(1 + x)^m (1 + x)^n$ in two different ways. Following Stanley,^[1] we can tweak this proof to prove the q-Vandermonde identity, as well. First, observe that the product

(1 + x)(1 + qx) \cdots \left (1 + q^{m + n - 1}x \right )

can be expanded by the q-binomial theorem as

(1 + x)(1 + qx) \cdots \left (1 + q^{m + n - 1}x \right ) = \sum_k q^{\frac{k(k-1)}{2}} \binom{m + n}{k}_{\!\!q} x^k.

Less obviously, we can write

(1 + x)(1 + qx) \cdots \left (1 + q^{m + n - 1}x \right ) = \left((1 + x)\cdots (1 + q^{m - 1}x)\right) \left( \left(1 + (q^m x) \right) \left (1 + q(q^m x) \right ) \cdots \left (1 + q^{n - 1}(q^m x) \right )\right)

and we may expand both subproducts separately using the q-binomial theorem. This yields

(1 + x)(1 + qx) \cdots \left (1 + q^{m + n - 1}x \right ) = \left(\sum_i q^{\frac{i(i - 1)}{2}} \binom{m}{i}_{\!\!q} x^i \right) \cdot \left(\sum_i q^{mi + \frac{i(i - 1)}{2}} \binom{n}{i}_{\!\!q} x^i \right).

Multiplying this latter product out and combining like terms gives

\sum_k \sum_j \left(q^{j(m - k + j) + \frac{k(k - 1)}{2}} \binom{m}{k - j}_{\!\!q} \binom{n}{j}_{\!\!q}\right)x^k.

Finally, equating powers of $x$ between the two expressions yields the desired result.

This argument may also be phrased in terms of expanding the product $(A + B)^m(A + B)^n$ in two different ways, where A and B are operators (for example, a pair of matrices) that "q-commute," that is, that satisfy BA = qAB.

Notes

↑ Stanley (2011), Solution to exercise 1.100, p. 188.

References

Richard P. Stanley (2011). Enumerative Combinatorics, Volume 1 (PDF) (2 ed.). Retrieved August 2, 2011.

Exton, H. (1983), q-Hypergeometric Functions and Applications, New York: Halstead Press, Chichester: Ellis Horwood, 1983, ISBN 0853124914, ISBN 0470274530, ISBN 978-0470274538
Gaurav Bhatnagar (2011). "In Praise of an Elementary Identity of Euler". Electronic J. Combinatorics, P13, 44pp. 18 (2). arXiv:1102.0659.
Victor J. W. Guo (2008). "Bijective Proofs of Gould's and Rothe's Identities". Discrete Mathematics. 308 (9): 1756. arXiv:1005.4256. doi:10.1016/j.disc.2007.04.020.
Sylvie Corteel; Carla Savage (2003). "Lecture Hall Theorems, q-series and Truncated Objects". arXiv:math/0309108 [math.CO].

This article is issued from Wikipedia - version of the 3/23/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.