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.

Comments

Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)

snapshot
Notifications