Words and selections

#matematik-discmath

We notice that a function is uniquely determined by the -tuple

Definition: Word

Let be a nonempty set. A function is called a word of length in the alphabet .

Remark

can also be seen as a mathematical model of an ordered selection with repetition of things from the set .

For example, we may let denote the function where , , .

Theorem

Let be nonempty finite sets where and . The set of all functions from to has size .

Proof:
We know a function is corresponds to an -tuple of elements of , meaning an element from . The Multiplication principle gives .

We notice that if we restrict the functions to only injective ones, we instead model selection without repetition of things from .

Theorem

The number of ordered selections without repetition of things from a set of size is the number of injections from to , which is given by Proof:
We have options for , options for and so on.