## 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 , ,..., 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,