Tricki
a repository of mathematical know-how

Number of elements in cartesian products

Quick description

This article describes situations where one can use multiplication to compute the number of elements of a set of vectors or strings.

Prerequisites

Basic mathematical notation.

General discussion

We start with the following elementary fact: if \Omega_1, \Omega_2,..., \Omega_n are finite sets and \Omega = \Omega_1 \times \Omega_2\times\cdots\times\Omega_n then

 |\Omega| = \prod_{i=1}^n|\Omega_i |.

The truth of this statement follows from the definition of multiplication for positive integers and induction.

Number of elements in cartesian products where the i^{th} set depends on the first i-1 components

In many situations we are interested in a set \Omega whose elements are strings (or vectors) of length n such that the set where the i^{th} component takes values depends on the values of the previous i-1 components of the string. Then one can write \Omega as follows:

 \Omega = \Omega_1 \times \Omega_2(\omega_1) \times \Omega_3(\omega_1,\omega_2)\times\cdots\times\Omega_n(\omega_1,\omega_2,...,\omega_{n-1}),

where an element of \Omega is denoted with \omega=(\omega_1,\omega_2,...,\omega_n).

If

 n_i = | \Omega_i(\omega_1,\omega_2,...,\omega_{i-1}) |

is independent of (\omega_1,\omega_2,...,\omega_{i-1}) then

 |\Omega| = \prod_{i=1}^n n_i.

Example 1

Several basic counting formulas follow from this principle. For example, the number of permutations of length r from a finite set \Omega_0 is

 (n-r+1)(n-r+2)\cdots(n-1)n,

where |\Omega_0| = n.

Example 2

In the previous example n_i is a decreasing sequence. Here is an example where n_i is increasing (Feller, Probability Theory, Vol I, Third Edition). Suppose there are r flag poles and each pole can contain arbitrary number of flags. What are the number of possible ways to put n distinct flags on these r poles if the order of the flags on the poles is important? In this example \Omega_i(\omega_1,\omega_2,...,\omega_{i-1}) is the possible places where the i^{th} flag can be put. \Omega_1 =\{1,2,3,...,r\}, i.e., for the first flag we simply pick a pole. Let \omega_1 \in \Omega_1 denote the pole where the first flag is put. Then

 \Omega_2(\omega_1) = \Omega_1  \cup \{ (\omega_{1},0) , (\omega_{1},1) \} - \{\omega_1 \}.

where (\omega_1,0) refers to the position before the first flag on the poll where this flag is and (\omega_{1},1) refers to the position after. It follows that

 |\Omega_2(\omega_1)| = r+1.

Let \omega_2 \in \Omega_2(\omega_1) denote the position of the second flag. Then the set of all possible positions for the third flag are:

 \Omega_3(\omega_1,\omega_2) = \Omega_2 \cup \{\ (\omega_2,0), (\omega_2,1) \}-  \{\omega_2\}

and it follows that

 |\Omega_3(\omega_1,\omega_2)| = r+2.

In general for the i^{th} flag the set of all possible positions are

 \Omega_i(\omega_1,\omega_2,...,\omega_{i-1}) = \Omega_{i-1}  \cup \{ (\omega_{i-1},0), (\omega_{i-1},1)\} - \{ \omega_{i-1}\}

and

 |\Omega_i(\omega_1,\omega_2,...,\omega_{i-1})| = r+i-1.

It is clear that the problem is in the range of our method and we have

 |\Omega| = r (r+1)(r+2)\cdots(r+n-1).

Example 3

Here is an example where the idea does not apply. Let \Omega_0 = \{1,2,3,4,...,N\}. Let \Omega be the set of ordered strings from the alphabet \Omega_0 of length n. \Omega has the same structure as the one given in the display above with

 \omega \ge \max_{j=1}^{i-1} \omega_i \right\}.

Clearly, here |\Omega_i| is a function of (\omega_1,\omega_2,...,\omega_{i-1}) and we cannot obtain |\Omega as simple multiplication. However, this problem can be embedded in a counting problem that yields to multiplication, see Example 2 in the article on counting and partitioning.