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 , ,..., are finite sets and then
The truth of this statement follows from the definition of multiplication for positive integers and induction.
Number of elements in cartesian products where the set depends on the first components
In many situations we are interested in a set whose elements are strings (or vectors) of length such that the set where the component takes values depends on the values of the previous components of the string. Then one can write as follows:
where an element of is denoted with
If
is independent of then
Example 1
Several basic counting formulas follow from this principle. For example, the number of permutations of length from a finite set is
where
Example 2
In the previous example is a decreasing sequence. Here is an example where is increasing (Feller, Probability Theory, Vol I, Third Edition). Suppose there are flag poles and each pole can contain arbitrary number of flags. What are the number of possible ways to put distinct flags on these poles if the order of the flags on the poles is important? In this example is the possible places where the flag can be put. , i.e., for the first flag we simply pick a pole. Let denote the pole where the first flag is put. Then
where refers to the position before the first flag on the poll where this flag is and refers to the position after. It follows that
Let denote the position of the second flag. Then the set of all possible positions for the third flag are:
and it follows that
In general for the flag the set of all possible positions are
and
It is clear that the problem is in the range of our method and we have
Example 3
Here is an example where the idea does not apply. Let . Let be the set of ordered strings from the alphabet of length . has the same structure as the one given in the display above with
Clearly, here is a function of and we cannot obtain 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.)