Combinatorics- How they are important to computer science
Combinatorics
In simple terms, it is mostly about determining the amount of possibilities certain situations have to play out. This includes probability, factorials, combinations and permutations.
Why is this important?
Well from a programmer’s perspective, combinatorics come in handy. Especially when we start talking algorithms.
In mathematics and computer science, an algorithm (Listeni/ˈælɡərɪðəm/ AL-gə-ri-dhəm) is a self-contained sequence of actions to be performed. Algorithms can perform calculation, data processing and automated reasoning tasks.An algorithm is an effective method that can be expressed within a finite amount of space and time[1] and in a well-defined formal language[2] for calculating a function.Credits)
Graph theory is also a part of combinatorics that relate to the study of objects and the interaction/connection between them
To determine the amount of resources used by computational procedures, we use the complexity theory, which is part of combinatorics.
Complexity theory is an interdisciplinary theory that grew out of systems theory in the 1960s.[1]:350 It draws from research in the natural sciences that examines uncertainty and non-linearity.[1] Complexity theory emphasizes interactions and the accompanying feedback loops that constantly change systems. While it proposes that systems are unpredictable, they are also constrained by order-generating rules.[2]:74
(Credits)
This branch of mathematics have a lot of other applications relating to computer science thus it can be seen as really important in the computer science field.
Examples in everyday life!
Let us say you have 9 guests attending a dinner you are hosting. You have a round table and you want to determine in how many ways can the 9 guests be seated. This is where combinatorics come in.
This one is easy; just place one guest at a fixed location, because the table is round. Then calculate 8! (Read eight factorial) which means calculate 8x7x6x5x4x3x2x1 = 40 320.
However, it can get complicated. Let us say that guest number three and five do not want to sit next to each other. Then you have to place them at a random place in the circle where they do not sit next to each other.
This means we calculate 2!*7! Which means (2x1)(7x6x5x4x3x2x1) =10 080 and then your possibilities decrease by a lot as you can see.
Another example we can use is determining the amount of passwords that can be formed.
Let us look at this example A certain email server uses case sensitive alphanumeric passwords. (Examples: “A7pQ5”, “RvS1990”.)
(a) How many passwords of eight characters can be formed?
Seeing as it uses uppercase and lowercase as well as digits means that the total number is 62 digits and letters that we can use all together.
Because there are no restrictions we can say that there are 62^8 ( 62 to the power of 8) possible passwords of length eight.
(b) How many passwords of eight characters contain no repeated characters?
Because this one has a restriction we have to take it into considerations. This is where we start using factorials because once you used one letter or digit you cannot use it again. In other words the answer would be
62P8 which reads as 62 Permutation 8.
This written out would be 62!/(62-8)!
We use factorial because the characters cannot be repeated but remember the password can only be 8 characters long. Thus we cannot just take 62!.
Another way of writing 62P8 would be 62x61x60x59x58x57x56x55.
Sorry for not posting lately, I have been busy with exams and life and sorry for the text justification
