Grouping and counting


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.


Factorial

Given the natural number n>0, its factorial, written as n!, is the natural number given by the product of all the natural numbers in.

Eqn000.gif

Obviously

Eqn001.gif

If n>1, we have

Eqn002.gif

If we want to extend the validity of this equality to the number n=1, we must admit that

Eqn003.gif

If k<n,

Eqn004.gif

Eqn005.gif

 

 

L. Euler was able to generalize the calculation of the factorial also for real and complex number by defining the function Γ (Gamma).


Permutations

Given a set Sn of n different elements, a simple permutation is a sequence we can form taking once k elements of S (kn). 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

Eqn100.gif

By induction:

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!:

Eqn102.gif

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

Eqn103.gif

and therefore

Eqn104.gif

Obviously if k=n the equality (1.10) gives

Eqn105.gif


Simple combinations

Given a set Sn of n different elements, a simple combination is a subset of Sn formed with k (kn) 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

Eqn200.gif

and therefore

Eqn201.gif

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

Eqn202.gif


Permutations with repetition

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.

Eqn300.gif

Since

Eqn301.gif

from the equality (4.1) we have

Eqn302.gif

In general

Eqn303.gif


Combinations with repetition

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

Eqn400.gif

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.