Number of elements in cartesian products

a repository of mathematical know-how

Number of elements in cartesian products

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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 
[maths]
|\Omega| = \prod_{i=1}^n|\Omega_i |.
[/maths]
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:
[maths]
\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}),
[/maths]
where an element of $\Omega$ is denoted with $\omega=(\omega_1,\omega_2,...,\omega_n).$

If 
[maths]
n_i = | \Omega_i(\omega_1,\omega_2,...,\omega_{i-1}) | 
[/maths]
is independent of $(\omega_1,\omega_2,...,\omega_{i-1})$  then
[maths]
|\Omega| = \prod_{i=1}^n n_i.
[/maths]

[EXAMPLE]
Several basic counting formulas follow from this principle. 
For example, the number of permutations of length $r$ from a finite set $\Omega_0$ is 
[maths]
(n-r+1)(n-r+2)\cdots(n-1)n,
[/maths]
where $|\Omega_0| = n.$

[EXAMPLE]
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
[maths]
\Omega_2(\omega_1) = \Omega_1  \cup \{ (\omega_{1},0) , (\omega_{1},1) \} - \{\omega_1 \}.
[/maths]
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
[maths]
|\Omega_2(\omega_1)| = r+1.
[/maths]
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:
[maths]
\Omega_3(\omega_1,\omega_2) = \Omega_2 \cup \{\ (\omega_2,0), (\omega_2,1) \}- 
\{\omega_2\} 
[/maths]
and it follows that 
[maths]
|\Omega_3(\omega_1,\omega_2)| = r+2.
[/maths]
In general for the $i^{th}$ flag the set of all possible positions are
[maths]
\Omega_i(\omega_1,\omega_2,...,\omega_{i-1}) = \Omega_{i-1}  \cup \{ (\omega_{i-1},0), (\omega_{i-1},1)\} - \{ \omega_{i-1}\}
[/maths]
and
[maths]
|\Omega_i(\omega_1,\omega_2,...,\omega_{i-1})| = r+i-1.
[/maths]
It is clear that the problem is in the range of our method
and we have
[maths]
|\Omega| = r (r+1)(r+2)\cdots(r+n-1).
[/maths]
  
[EXAMPLE]
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 
[maths]
\Omega_i(\omega_1,\omega_2,...,\omega_{i-1}) = \left\{ \omega \in \Omega_0: \omega \ge \max_{j=1}^{i-1} \omega_i \right\}.
[/maths]
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 [[Counting by partitioning| Example 2 in the article on counting and partitioning.]]

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Number of elements in cartesian products

Recent articles

Active forum topics

Recent comments