Sample . In Combinatorics, a sample M is the extraction of a quantity of elements from a given set A , more particularly, the quantity of elements to be taken each time is usually predefined and then it is called rsample because it contains r elements. This r value is called the sample volume . Samples are considered permutations if they are ordered and combinations if the order is not relevant to distinguish one sample from another.
Samples, permutations and combinations are the three pillars of Combinatorics, one of the branches of mathematics , dedicated to the study of the possibilities of formation of different types of samples and has great utility for Probabilistics , Discrete Mathematics , Statistics , the Complexity Analysis of Algorithms and others.
Summary
[ hide ]
 1
 2 Types of samples.
 1 Permutations.
 1.1 Permutations with repetition.
 1.2 Permutations without repetition.
 2 Combinations.
 2.1 Combinations without repetition.
 2.2 Combinations with repetition.
 3
 1 Permutations.
Definitions.
Is a set A finite n elements is called rsample any tuple r elements (a _{1} , a _{1} , …, a _{r} ) of A .
If at least a pair of elements a _{i} , a _{j} fulfills that a _{i} = a _{j} ; then the rsample is said to be an rsample with repetition ; otherwise it is an rsample without repetition .
Depending on the importance of the order in which the elements were taken, that is, the order of a _{i} in the rsample makes it different from each other, it is said to be an rpermutation . If it is a repeat rsample then it will be a repeat rpermutation . If it is an rsample without repetition then it will be an rpermutation without repetition .
If there is no order, that is, if any rpermutation of (a _{1} , a _{1} , …, a _{r} ) is considered equal to each other, then the rsample is called rcombination . If there is repetition of elements, then it will be an rcombination with repetition ; but it is rcombination without repetition .
Sample types.
Variants of rpermutations and rcombinations make up all possible types of rsamples on A with  A  = n :

 Permutations with repetition.
 Permutations without repetition.

 Combinations without repetition.
 Combinations with repetition.
Although in some sources the so – called rvariations (simply variations) or rarrangements also appear .
The common objective in the presence of samples, permutations and combinations is either the search for all the samples or the a priori calculation of the number of possibilities of forming each type of sample, for which there are welldefined methods throughout the development of The humanity.
Each one has its own particularities, origins of common use and forms of application. Let’s look at all the cases.
Permutations.
As we have already seen, permutations are samples where the order of appearance of the elements differentiates one sample from another, if they are the same elements. For example, they are permutations:
 abc, acb , bac , bca , cab , cba .
 (0,0,0), (0,0,1) , (0,1,0) , (0,1,1) , (1,0,0) , (1,0,1) , (1 , 1.0) , (1,1,1) .
In the first case, these are all 3permutations without repetition of the set {a, b, c} written as words; while the second are 3permutations with repetition of the elements of the set {0,1} . Here the repetitions are remarkable because several triplets are seen where the zero or the one appears several times .
Now, the fundamental questions in each case are how to obtain the rpermutations on a set A with n elements and how the number of possible forms of rpermutations in an nset (set of n elements) could be known beforehand . Depending on whether they are permutations with or without repetition, there are different methods. However, for rpermutations on an nset a general form can be thought:
P (r, n) = k _{1} k _{2} … k _{r} , where k _{i} is the number of elements that can be arranged in the ith position of the rsample.
Permutations with repetition.
In this type of sample, although there is an order or positioning of the elements, they can be repeated in different places in the same sample. One of the most common cases is our numbering system which, being positional, makes each natural number, for example, a permutation with repetition to include the possibility that the same number can mean the number of powers of 10 that its place indicates, this it is done on the set of the ten figures: {0,1,2,3,4,5,6,7,8,9}. One might think that there is an inconsistency when comparing for example 13 and 133 because one could think that the first is a 2permutation and the second, a 3permutation; but if 13 is rewritten as 013 there is no longer any doubt.
The simplest method of obtaining rpermutations on an nset A with repetition could be:
 Assign an order to A, leaving (a _{1} , a _{2} , …, a _{n} )
 P = (p _{1}, p _{2} , …, p _{r} ) = {0} ^{r}
 L = {}
P _{r} = (a _{p }_{1} , a _{p }_{2} , …, a _{p }_{r} )
 L = LU {P _{r}}
 i = r:
 Repeat the following steps until P _{r}= {a _{n} } ^{r} :
 If p _{i}is not n :
 Increase p _{i}
 If p _{i}is not n :
P _{r} = (a _{p }_{1} , a _{p }_{2} , …, a _{p }_{r} )


 L = LU {P _{r}}
 On the contrary:
 p _{i}= 0
 If iis other than 0:
 Decrement i
 In Lremain the rpermutations

In the Python programming language it could be expressed:
def Permutations_with_Repetition (r, A): a = list (A) n = len (a) 1 L = [] p = [0] * r P = [a [j] for j in p] L.append (P) i = r1 p_final = [n] * r while p! = p_final: if p [i]! = n: p [i] + = 1 P = [a [j] for j in p] L.append (P) if i! = r1: i = r1 else: p [i] = 0 if i: i – = 1 return L
Thus the rpermutations with repetition can be obtained.
But there is also a calculation method that determines the number of repeating rpermutations that can be obtained from an nset:
 Pr _{r, n}= n ^{r}
This formula is based on the arithmetic fact that for every n values of A in the first position of the rpartition, any of the n values can also be put in the 2nd place and thus up to the rth place. In the end it turns out that you have to multiply r times the n or n ^{r} .
Examples:
How many 6permutations can be formed with the letters ABCDE ? They are 5 letters, therefore: Pr _{6,5} = 5 ^{6} = 15625 .
 With 3 three dice rolls, up to 6 ^{3}= 216 numbers can be formed .
How many 4digit numbers can be formed? 9×10 ^{3} = 9000 (the form is like this because 0 cannot be entered in the thousands, in the rest it can).
A particular case of rcalculating permutations with repetition of an nset A is when you want to determine the amount of subsets of A . For this tuple is created whose elements would be the existence (V) or absence (F) of each element of A . Now the question changes how many nuplas can settle for {F, V} which is the same as’ Pr _{n, 2} = 2 ^{n} .
Permutations without repetition.
Permutations without repetition are also often called variations or arrangements and basically consist of taking in order up to r the elements of A as it would be from a bag. For the first position of the rpermutation there are n possibilities to choose; for the second, since an element has already been taken, there are n1 ; for the third place, n2 and so on to the place r where there are nr + 1 variants to choose from. In summary, P _{r, n} rpermutations can be formed without repetition on an nset, where:
 P _{r, n}= n (n1) (n2) … (nr + 1) .
In the case that r = n , the formula remains:
 P _{n, n}= P _{n} = n! .
There is no formula for when r> n because by extracting the n elements from A there are still places to fill in the rsample and there are no more elements.
The construction of the different permutations is usually carried out by going through the [[Forest (Graph)  forest]] whose trees have a root that can be any of the n elements of A , that element is marked and n1 branches are derived for the remaining elements , then from each of these n2 branches are traced with the other remaining elements and so on until the depth r is completed .
Forest bypass trees A elements
Combinations.
Behind the idea of the combination lies the fact of not taking into account the order of the elements, only the presence of them in the sample is enough to identify them. Although in the case of combinations with repetition of elements it could be represented as a set, when repetition is allowed it would not work because the sets do not support it. So it usually usually shows up as ruplas.
Examples
 ab, ac , bc are the 2combinations without repetition of {a, b, c} .
 aa, ab , ac , bb , bc , cc are the 2combinations with repetition of {a, b, c} .
Also in the case of rcombinations, people often want to know how to obtain them all and how many there are or will be.
Combinations without repetition.
The count of the total of rcombinations without repetition on an nset is given by the fact of removing from the number of rpermutations or P _{r, n} the permutations that can be made to each rsample that would be P _{r, r} . Dividing remains: P _{r, n} / P _{r, r} = P _{r, n} / r! . This result is well known and is identified by the following notation:
Whose name is also the binomial coefficient .
It is easy to perceive that the rcombinations of an nset are its subsets of length r . Therefore, the construction method is focused on obtaining all rsubsets of A .
Combinations with repetition.
When element repetition is supported in combinations, the count (and construction) of the total rcombinations with repetition over an nset takes the form:
 It is associated with Athe
subset N _{n} of the first natural n using the isomorphism R = {<1, a _{1} >, <2, a _{2} >, …, <n, a _{n} >} .
 L = {}
For all rsample M = (k _{1} , k _{2} , …, k _{r} ) where k _{i} is an element of N _{n} and k _{1} <= k _{2} <= … <= k _{r} :

 It inverting the isomorphism R, it is obtained from M rsample S .
 L = LU {S}
 In Lare the rcombinations with repetition of A
Before accounting for the combinations obtained by the previous method, a second onetoone association can be made between M and a rset O formed by O = {k _{1} + 0, k _{2} +1, …, k _{r} + r 1} , where O will be the form of all rsubsets of {1,2, …, n, n + 1, …, n + r1} , which is the same as the rcombinations of a (n + r1) set, which is defined as: