Choose jour language!

---

|

14. Combinatorics: Calculation number of combinations. - solution

---

Variations without repetition. Permutations. Combinations without repetition.

The following figure shows how to create and calculate variations of n elements of the kth class, without repetition, on an example, what are permutations, what is the difference between variations and combinations without repetition and how to determine their number.

Figure 1: Combinatorics: Variations and combinations without repetition, of n elements, k-th class on an example.

    Let a set of elements N be given and let them be natural numbers from 1-5 in the observed example. From those numbers, it is shown in Figure 1, how the variations of the 2nd (left) and 3rd (right) class of 5 elements are formed. The number of n=5 elements comes from the set N, which is the number of elements available for making variations. For example. 1-2 is a class 2 variation because two digits are in the variation, while 1-2-3 is a class 3 variation.
In order to get the total number of variations of 5 elements of the 2nd class, let's observe how many different ways it is possible to choose the first digit from one variation, which is actually 5(n) in this example, where n is the number of elements of the set N.
In the next place, it is possible to choose 1 less number of different digits, if the variations are without repetition, because one element of the set is already "reserved" for the first place. So we have 5 groups of variations with the number 1 in the first place, 5 groups with the number 2 in the first place, etc. which means we multiply by the number of possibilities in the 2nd place, which in this example is 4.
So the number of variations of 5 elements of 2 classes is:

V⁵₂=5*4 = 20

It should further be noted that if the class increases by 1, i.e. if k=3, one more digit should be added to the existing class variation of the 2nd class, so that the number of possibilities increases as many times as it is possible to vary the element in the third place in variation, and in the example it is 1 less than in the previous place, so 3(5-2), because we have already placed two elements earlier. Each subsequent increase would add (n-k+1) new possibilities, so the formula for the number of non-repeating variations of n elements of class k is:

Vⁿ_k=n*(n-1)*(n-2)*...*(n-k+1)

A special case of variations when the class is equal to the number of elements, so when n=k are called permutations of n elements and are calculated:​
​

P=n*(n-1)*(n-2)*...*1= n!

---

Number of combinations without repetition

If we look at the example for class 2 and 3, the following can be observed:
Variations 1-2 and 2-1 are two different variations, but it is the same combination, because the order of the elements in the variation in the combination is not important, only the digits, as a "group". The number of combinations in that case is 2 times smaller.
In the case of the 3rd class it would be, for example: 1-2-3,1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1 represents 6 different combinations, but it is about one combination. So in the case of class 3, the number of combinations is 2*3=6 times less than the number of variations.
In the general case for n elements of class k, the number of variations is mani k!(k factorial) times, which is actually the number of permutations of k elements.
The number of combinations of n elements of the kth class is thus calculated:

Cⁿ_k=Vⁿ_k/K!
Cⁿ_k=n*(n-1)*(n-2)*...*(n-k+1)/K!

Below is the solution to the task in the "c" programming language:

Solution of the task - code:

#include <stdio.h>
#include <math.h>

/*function that determines the value of the factorial of an integer*/
int factoriel(int x)
{
    int F;
    F=1;
    while(x>1)
    {
        F=F*x;
        x--;
    }
    return F;

}
int combinations(int n1,int k1)//5,3
{

    int K,T;
    K=1;
    T=n1;
    while(T > n1-k1){  //5>2,4>2,3>2
        K=K*T; //K=1*5=5; K=5*4=20; K=20*3=60
        T--;
    }
    int numComb=K/factoriel(k1); //numComb=60/6=10
    return numComb; //return 10

}
int main()
{
    int n,k,p,S=0;
    printf("n=?,k=?,p=?\n");
    scanf("%d%d%d",&n,&k,&p);
    for(int pi=0; pi<=p; pi++)
    {
        int coef=(int)pow(-1,pi);
        int comb=combinations(n,k+pi); //Calls a function that counts the number of combinations of n elements of class k+pi
        printf("%d + %d * %d\n",S,coef,comb);
        S=S+coef * comb;
    }
    printf("%d\n",S);
    return 0;
}

---

Prethodno
​|< Functions in C/C++ - examples

Sledeće
Algorithms examples >|

---