The binomial coefficient – the Newton symbol C#

The binomial coefficient – the Newton symbol C#

What is called in two ways the binomial coefficient – the Newton symbol?

Sometimes a situation occurs in which we need to determine the number of combinations of elements of a given set. This is a situation that, contrary to appearances, happens very often, but it is not always necessary to make calculations, and decisions are made intuitively.

For example, you can consider several situations in which a selection is made taking into account the number of combinations:

A series of 4 collector’s cards from well-known athletes has appeared, and we can afford only 2 of them. From this set we can choose cards with numbers {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}, so we can make as many as 6 different choices.

Favorite number game draws 5 unique numbers from 60 available. The number of combinations is much larger than in the previous example and it would take a lot of space in this article to list them all.

The company employs 100 employees and half of them will receive a bonus this month. How many combinations of employee selection can occur here? Many employers do not think about it and do it at their own discretion.

Definition of the Newton symbol

What if, however, we would like to see how much we really have choices and what are they? Then you can use the formula defined by Newton, called the Newton Symbol or the binomial ratio. This is a function of two arguments that are nonnegative integers. The solution to the Newton’s Symbol is information on how many possible combinations of choices can be obtained by selecting k elements from the n-element set. The formula definition is as follows:

The result of Newton’s symbol in the code

The presented code represents the solution of the above formula without using recursion for engines. It uses a dependency that arises when you shorten the value that is part of the counter with the greater of the numbers in the denominator. Explanation on a specific example should dispel doubts. The counter in the Newton’s Symbol will always be greater than or equal to the denominator. Choosing n = 8 and k = 5 we get a fraction:

The variable that we want to place in the condition must be declared before the occurrence of the loop in the code. Variable initialization may only appear in the loop because it will still be before the condition is checked.

By shortening the counter (8!) With the greater factor from the denominator (5!) We get:

– in the numerator 6 * 7 * 8 (because 1 * 2 * 3 * 4 * 5 will be shortened),

– in the nominative 1 * 3! (and therefore 1 * 2 * 3).

In the code below, the number 1 is multiplied by successive values of the counter (6 * 7 * 8) and divided by subsequent elements of the denominator (1 * 2 * 3). This dependency simplifies the writing and operation of the code to one condition and one loop.

long WyliczIloscGrup(long n, long k)//returns the number of combinations
{
   if (k > n - k)
      k = n - k;
   long liczGrupy = 1;
   for (int i = 0; i < k; i++)
   {
      liczGrupy = liczGrupy * (n - i);
      liczGrupy = liczGrupy / (i + 1);
   }
   return liczGrupy;
}

Combination groups in the code

Sometimes information about the number of possible combinations of choices is insufficient and we would like to know what elements they consist of. The code is relatively simple in the case when we know the number of elements to be found and how many are available. The situation becomes more complicated when the function is to be universal and useful for any values.

The following is the code of the function that retrieves the parameters n and k described earlier, and returns an array of arrays. The returned array in each row stores a one-item array with values belonging to a given group. Therefore, rows can be interpreted as subsequent groups, and their columns as elements drawn in them.

The algorithm needs explanation, but the frog is better understood by using the example n = 6, k = 4.

Defining the drawn values takes place in the while loop. Its first call saves the originally defined group (1,2,3, .., k – in our example 1,2,3,4). Subsequent loop calls increase the last element in the original array until it has a maximum value equal to n (i.e. -> 1,2,3,5 -> 1,2,3,6). After such a value occurs, the variable p is decreased by 1, which causes reference to the element with the lower index (at this stage it is the value from 3 positions equal to 3, which is changed to 4). Elements with larger indexes from it are increased by 1, in relation to the new variable (1,2 remain unchanged, 4 changed a moment ago and subsequent elements 4 + 1 = 5, which gives another group 1,2,4,5), and variable p again gets the value equal to k, so as to refer to the last element.

The reference to elements with smaller and smaller indexes is realized when the last element takes the maximum value more than once, for consecutive elements (eg the first time for the group 1,2,4,6, where p is reduced to 3, the second time 1 , 2,5,6 where p is reduced to 2). The last groups reduce the variable p to 0 and thanks to this and the counter we know that this is the last possible combination.

//Determination of k-element groups from the n-element set
int[][] WyznaczGrupy(int n, int k)
{
    int i = 0, p = 0, licznik = 0;
    //number of possible groups of numbers - number of rows in the table
    long iloscGrup = WyliczIloscGrup(n, k);
    //declaration of a k-element array for individual groups
    int[] pojedynczaGrupa = new int[k];
    //declaration of the array of tables for all groups
    int[][] wszystkieGrupy = new int[iloscGrup][];
    //for each row an empty one-dimensional array, k-element, is assigned
    for (i = 0; i < iloscGrup; i++)
        wszystkieGrupy[i] = new int[k];
    //complementing the k-element array with values from 1 to k
    for (i = 1; i <= k; i++)
        pojedynczaGrupa[i - 1] = i;

    //we draw fewer numbers than we have available (n)
    if (k < n)
        p = k;
    //all n-numbers are drawn randomly
    else
        p = 1;

    //Counter - the number of the currently completed group
    while (licznik < iloscGrup)
    {
        //when the last element of the group is equal to the last available value -> the last case
        if (pojedynczaGrupa[k - 1] == n)
            // p is the position in the originally defined k-element array to which we jump
            // to increase its value by one and according to it set further elements.
            p--;
        else
            p = k;

        //if (p> 0) exceeds the range of defined groups and (counter! = 0) this is not the first group
        if ((p > 0) && (licznik != 0))
        {
            for (i = k; i >= p; i--)
                pojedynczaGrupa[i - 1] = pojedynczaGrupa[p - 1] + i - p + 1;
        }

        //assigning the created single group to the appropriate row in the set of all groups
        for (int j = 0; j < k; j++) //completing the next row
            wszystkieGrupy[licznik][j] = pojedynczaGrupa[j];

            licznik++;
    }
    return wszystkieGrupy;
}

Displaying all combinations

Below, a code is presented, gathering in the variable string data on the composition of groups and their numbering in a manner pleasing to the human eye:

1 – 1 2 3 4 5
2 – 1 2 3 4 6
3 – 1 2 3 4 7
4 – 1 2 3 4 8
….

//Display
int line = 0;
licznik = 0;
while (licznik < iloscGrup)
{
   line++;
   wyswietlwszystkieGrupy += "\n";
   wyswietlwszystkieGrupy += line.ToString();
   wyswietlwszystkieGrupy += "  -  ";

   for (int j = 0; j < k; j++) //uzupełnianie kolejnego wiersza
      wyswietlwszystkieGrupy += wszystkieGrupy[licznik][j].ToString() + " ";
   licznik++;
}