Given a set Sn of n different elements, it is possible to use these elements to form other sets Gi.
The number of these possible groupings Gi is virtually infinite and can be virtually infinite also the number of their elements. But in many operational situations there are more or less explicit formation rules that limit their number so that these groupings can be counted.
For example, given the set of the letters of the Latin alphabet, you can build sequences representing the words of the English language. The number of possible words is not limited a priori, nor is their length. Theoretically you can create more or less fanciful neologisms, but, in general, if you want them to be understandable, their composition and their length can not be arbitrary not only by the need that every word is has a meaning, but also by the phonetic and orthographic compatibility. For example, it will be difficult that a sequence as hgtkx (unless it is a particular acronym) is included in a vocabulary.
We can exactly calculate the number E of the Gi only if we explicitly define the method we use to make them.
The formal development of this subject made in the second half of last century, mainly by Giancarlo Rota, is known as Twelvefold way. Here we are limited to the most basic and intuitive arguments.
The most restrictive rule is to establish that the sets Gi must be subsets of S such that they constitute a partition of S, that is
This case is treated the page Partitions of this site.
If we admit that the elements of S are all distinguishable and that the sets Gi may have elements in common, their number can be limited by setting the number k of their elements.
The result of the the counting varies according to the way in which the sets are formed and evaluated. In particular:
Moreover, if we form the groups Gn,k taking only once the elements of Sn, we count the simple permutations or combinations; otherwise we count the permutations or combinations with repetition.
In order to obtain the number of the groups we can form in these different ways, it is useful to calculate the factorial of a natural number n.
Given the natural number n>0, its factorial, written as n!, is the natural number given by the product of all the natural numbers i ≤ n.
Obviously
If n>1, we have
If we want to extend the validity of this equality to the number n=1, we must admit that
If k<n,
L. Euler was able to generalize the calculation of the factorial also for real and complex number by defining the function Γ (Gamma).
Given a set Sn of n different elements, a simple permutation is a sequence we can form taking once k elements of S (k ≤ n). The number of these sequences is written as Pn,k.
In particular, if we write as Pn,n the number of the different ways of arranging all the n elements of S, we have
By induction:
if we add another element to the set Sn, from each sequence Pn,n we can obtain n+1 new different sequences, each of them with n+1 elements. So the permutations Pn+1,n+1 are
If the elements of Sn are not all different from each other, but, for example, Sn contains m times the same element, we will have m! permutations indistinguishable from each other, that is they are the same permutation that we count only once, so we must divide Pn,n by m!:
If the elements of Sn are all different from each other and k<n, given the number Pn,k of the sequences with k elements we can obtain from Sn and the number Pn-k,n-k of the sequences we can form with the remaining n-k elements, the number Pn,n is given by
and therefore
Obviously if k=n the equality (1.10) gives
Given a set Sn of n different elements, a simple combination is a subset of Sn formed with k (k≤n) of its elements, each of them taken once. Order does not matter. The number of these subsets is written as Cn,k.
In order to calculate Cn,k, we observe that from each subset with k elements we can have k! different permutations. So
and therefore
The numbers Cn,k coincide with the numbers of the Pascal's triangle, used to expand the n-th power of a binomial, so they are usually referred as binomial coefficients. They are written in the following ways
Given a set Sn of n different elements, a permutation with repetition is a sequence formed taking k elements of Sn, each of them possibly more than once. k can therefore be greater than n.
Such permutations are considered different if they have different elements or, otherwise, if their elements have different order.
We will write the number of such permutations as P'n,k.
To calculate such number, we observe that, given a permutation with k elements, we can obtain n permutations with k+1 elements by appending to it any of the n elements of Sn.
Since
from the equality (4.1) we have
In general
Given a set Sn of n different elements, a combination with repetition is a set formed taking k elements of Sn, each of them possibly more than once. k can therefore be greater than n.
Such combinations are considered different only if they have different elements.
We will write the number of such combinations as C'n,k.
This number is the same we would get if we were to calculate the simple combinations with k elements from a set Sn+k-1 formed by n+k-1 different elements. So from the equality (1.13) we have
For example, given the set Sn = {a,b,c}, a possible combination with k = 5 elements is the set {a,a,a,a,a} where the last four a are treated as if they were different elements.