Sample (Combinatorial)

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 r-sample 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

Definitions.

Is a set A finite n elements is called r-sample any tuple r elements (a 1 , a 1 , …, a r ) of A .

If at least a pair of elements i , j fulfills that i = a j ; then the r-sample is said to be an r-sample with repetition ; otherwise it is an r-sample without repetition .

Depending on the importance of the order in which the elements were taken, that is, the order of i in the r-sample makes it different from each other, it is said to be an r-permutation . If it is a repeat r-sample then it will be a repeat r-permutation . If it is an r-sample without repetition then it will be an r-permutation without repetition .

If there is no order, that is, if any r-permutation of (a 1 , a 1 , …, a r ) is considered equal to each other, then the r-sample is called r-combination . If there is repetition of elements, then it will be an r-combination with repetition ; but it is r-combination without repetition .

Sample types.

Variants of r-permutations and r-combinations make up all possible types of r-samples on A with | A | = n :

    • Permutations with repetition.
    • Permutations without repetition.
    • Combinations without repetition.
    • Combinations with repetition.

Although in some sources the so  called r-variations (simply variations) or r-arrangements 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 well-defined 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:

  • abcacb , 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 3-permutations without repetition of the set {a, b, c} written as words; while the second are 3-permutations 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 r-permutations on a set A with n elements and how the number of possible forms of r-permutations in an n-set (set of n elements) could be known beforehand . Depending on whether they are permutations with or without repetition, there are different methods. However, for r-permutations on an n-set a general form can be thought:

P (r, n) = k 1 k 2 … k r , where i is the number of elements that can be arranged in the i-th position of the r-sample.

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 2-permutation and the second, a 3-permutation; but if 13 is rewritten as 013 there is no longer any doubt.

The simplest method of obtaining r-permutations on an n-set A with repetition could be:

  1. Assign an order to A, leaving (a 1 , a 2 , …, a n )
  2. P = (p 1, p 2 , …, p r ) = {0} r
  3. L = {}

r = (a 1 , a 2 , …, a r )

  1. L = LU {P r}
  2. i = r:
  3. Repeat the following steps until r= {a n } r :
    1. If iis not n :
      1. Increase i

r = (a 1 , a 2 , …, a r )

      1. L = LU {P r}
    1. On the contrary:
      1. i= 0
      2. If iis other than 0:
        1. Decrement i
      3. In Lremain the r-permutations

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 = r-1    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! = r-1:                i = r-1        else:            p [i] = 0            if i:                i – = 1    return L

Thus the r-permutations with repetition can be obtained.

But there is also a calculation method that determines the number of repeating r-permutations that can be obtained from an n-set:

  • 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 r-partition, any of the n values can also be put in the 2nd place and thus up to the r-th place. In the end it turns out that you have to multiply r times the n or r .

Examples:

How many 6-permutations can be formed with the letters ABCDE ? They are 5 letters, therefore: Pr 6,5 = 5 6 = 15625 .

  1. With 3 three dice rolls, up to 6 3= 216 numbers can be formed .

How many 4-digit 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 r-calculating permutations with repetition of an n-set 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 n-uplas 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 r-permutation there are n possibilities to choose; for the second, since an element has already been taken, there are n-1 ; for the third place, n-2 and so on to the place r where there are n-r + 1 variants to choose from. In summary, r, n r-permutations can be formed without repetition on an n-set, where:

  • r, n= n (n-1) (n-2) … (n-r + 1) .

In the case that r = n , the formula remains:

  • 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 r-sample 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 n-1 branches are derived for the remaining elements , then from each of these n-2 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 r-uplas.

Examples

  • abac , bc are the 2-combinations without repetition of {a, b, c} .
  • aaab , ac , bb , bc , cc are the 2-combinations with repetition of {a, b, c} .

Also in the case of r-combinations, 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 r-combinations without repetition on an n-set is given by the fact of removing from the number of r-permutations or r, n the permutations that can be made to each r-sample that would be r, r . Dividing remains: 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 r-combinations of an n-set are its subsets of length r . Therefore, the construction method is focused on obtaining all r-subsets of A .

Combinations with repetition.

When element repetition is supported in combinations, the count (and construction) of the total r-combinations with repetition over an n-set takes the form:

  1. It is associated with Athe

subset n of the first natural n using the isomorphism R = {<1, a 1 >, <2, a 2 >, …, <n, a n >} .

  1. L = {}

For all r-sample M = (k 1 , k 2 , …, k r ) where i is an element of n and 1 <= k 2 <= … <= k r :

    1. It inverting the isomorphism R, it is obtained from M r-sample S .
    2. L = LU {S}
  1. In Lare the r-combinations with repetition of A

Before accounting for the combinations obtained by the previous method, a second one-to-one association can be made between M and a r-set O formed by O = {k 1 + 0, k 2 +1, …, k r + r- 1} , where O will be the form of all r-subsets of {1,2, …, n, n + 1, …, n + r-1} , which is the same as the r-combinations of a (n + r-1) -set, which is defined as:

 

Leave a Comment