Chapter 1
Basic q-Combinatorics and q-Hypergeometric Series

1.1 Introduction

The basic -sequences and -functions of the calculus of -hypergeometric series, which facilitate the study of discrete -distributions, are thoroughly presented in this chapter. More precisely, after introducing the notions of a -power, a -factorial, and a -binomial coefficient of a real number, two -Vandermonde's (-factorial convolution) formulae are derived. Also, two -Cauchy's (-binomial convolution) formulae are presented as a corollary of the two -Vandermonde's formulae. Furthermore, the -binomial and the negative -binomial formulae are obtained. In addition, a general -binomial formula is derived and, as limiting forms of it, -exponential and -logarithmic functions are deduced. The -Stirling numbers of the first and second kind, which are the coefficients of the expansions of -factorials into -powers and of -powers into -factorials, respectively, are presented. Also, the generalized -factorial coefficients are briefly discussed. Moreover, the -factorial and -binomial moments, which, apart from the interest in their own, are used as an intermediate step in the calculation of the usual factorial and binomial moments of a discrete -distribution, are briefly presented. Finally, the probability function of a nonnegative integer-valued random variable is expressed in terms of its -binomial (or -factorial) moments.

1.2 q-Factorials and q-Binomial Coefficients

Let and be real numbers, with , and be an integer. The number

is called -number and in particular is called -integer. Note that

The base (parameter) , in the theory of discrete -distributions, varies in the interval or in the interval . In both these cases,

In particular,

In this book, unless stated otherwise, it is assumed that or .

The th-order factorial of the -number , which is defined by

is called -factorial of of order . In particular,

is called -factorial of .

The -factorial of of negative order may be defined as follows. Clearly, the following fundamental property of the -factorial

is readily deduced from its definition. Requiring the validity of this fundamental property to be preserved, the definition of the factorial may be extended to zero or negative order. Specifically, it is required that the fundamental property is valid for any integer values of and . Then, substituting into it , it follows that

for any integer . This equation, if , whence , implies

while, if , reduces to an identity for any value is required to represent. Furthermore, from the fundamental property, with a positive integer and , it follows that

and, for ,

Notice that the last expression, for , yields

The -binomial coefficient (or Gaussian polynomial ) is defined by

and so

Note that

and since

it follows that

and

Using these expressions, a formula involving -numbers, -factorials, and -binomial coefficients in a base , with , can be converted, with respect to the base, into a similar formula in the base , with .

Two useful versions of a triangular recurrence relation for the -binomial coefficient, which constitutes a -analogue of Pascal's triangle, are derived in the next theorem.

Theorem 1.1

Let and be real numbers, with , and let be a positive integer. Then, the -binomial coefficient satisfies the triangular recurrence relation

with initial condition . Alternatively,

Proof

The -factorial of of order , since and

satisfies the triangular recurrence relation

with initial condition . Thus, dividing both members of it by and using the expression

the triangular recurrence relation (1.1) is readily deduced. Furthermore, replacing the base by and using the relation

(1.1) may be rewritten in the form (1.2).

Note that the triangular recurrence relation (1.2) may also be derived, independently of (1.1), by using the expression

which entails for the -factorial of of order the triangular recurrence relation

Hence, dividing both members of it by , (1.2) is obtained.

Remark 1.1

The lack of uniqueness of -analogues of expressions and formulae. The lack of uniqueness, due to the presence of powers of in pseudo-isomorphisms as

where or , should be remarked from the very beginning of the presentation of the basic -sequences, -functions and -formulae. It should also be noticed that the two formulae may be considered as equivalent in the sense that any of these implies the other by replacing the base by . In this framework, the existence of two versions of the -analogue of Pascal's triangle, which may be considered as equivalent, is attributed to the lack of uniqueness.

The particular cases of the -binomial coefficients and , with and positive integers, admit -combinatorial interpretations, which are deduced in the following theorem, starting from a generating function of a number of partitions of an integer into parts of restricted size. Recall that a partition of a positive integer into parts is a nonordered collection of positive integers, , with , for , whose sum equals . In a partition of into parts, let be the number of parts that are equal to , for . Then,

Theorem 1.2

The -binomial coefficient , for and positive integers, equals the -combinations of the set , , weighted by ,

Also, the -binomial coefficient , for and positive integers, equals the -combinations of the set with repetition, , weighted by ,

Proof

Let denotes the number of partitions of into parts, each of which is less than or equal to , and consider its bivariate generating function

for fixed . Clearly, using the definition of a partition of into parts, each of which is less than or equal to , it may be expressed as

where in the inner sum the summation is extended over all integer solutions , for , and , for , of the equations and . Since this inner sum is summed over all and , it follows that

Furthermore, for the sequence of univariate generating functions

on using the relation and since

we deduce the following first-order recurrence relation

Applying it repeatedly, we find the expression

Since the number , of partitions of into parts, each of which is less than or equal to , equals the number of solutions in positive integers of the equation , with , or equivalently (by replacing with , for ), with , the last expression may also be written in the form

which readily implies (1.4).

Furthermore, replacing by in (1.4) and then setting , for , the inequalities are transformed into and . Consequently, expression (1.4) is transformed into

from which (1.3) is deduced.

Remark 1.2

An alternative expression of a -binomial coefficient. Expression (1.4) of the -binomial coefficient , may be written alternatively as follows. Let be the number of the (bound) variables , that are equal to , for . Then, , with , and

Consequently, expression (1.4) may be, alternatively, expressed as

A few interesting combinatorial and probabilistic examples, in which -numbers and -binomial coefficients naturally emerged, are presented next. Specifically, in the following example, a number theoretic random variable is defined in a sequence of independent and identically distributed Bernoulli trials, and its probability function is expressed by a -number.

Example 1.1

Bernoulli trials and number theory. Consider a sequence of independent Bernoulli trials, with constant failure probability , and let be the number of failures until the occurrence of the first success. Clearly, the random variable follows a geometric distribution with probability function

where . Also, consider a fixed positive integer and let

Clearly, each of the possible values of the random variable , , belongs to one of these congruence classes (pairwise disjoint sets), modulo , . Furthermore, consider a sequence of independent Bernoulli trials, with constant failure probability , and let be the index of the congruence class in which the number of failures, until the occurrence of the first success, belongs. Since the random variable assumes the value if and only if belongs to , its probability function,

may be expressed as

Note that the limiting probability function, as ,

is the discrete uniform probability function on the set . For this reason, the distribution of is called discrete -uniform distribution.

It is worth noting that the probability function , of a right truncated geometric distribution, since

for , and

is readily deduced as

An interesting combinatorial interpretation of the -binomial coefficient for a positive integer and a power of a prime number, is given in the next example.

Example 1.2

Number of subspaces of a vector space. Let be a vector space of dimension over a finite field of elements, where is a prime number and is a positive integer. The vector space contains vectors. A subspace of , of dimension...