Combinatorics

[d0ntc4r3 104]

Combinatorics

By Gallo

13th of Snow’s Maiden, 54 SA

 

 

 

 

 

Permutations

 

 

Commander Uell is a proud Mali'aheral, and was recently promoted in elSillumir. He wishes to organize his 10 sillumiran into a line, but he cannot decide which order to put them in. He thinks to himself for a moment and asks how many possible ways these 10 sillumiran could be ordered? Uell has just delved into combinatorics, more specifically permutation theory.

 

Let us call each possible ordering of a set a permutation. We want to find the total number of possible permutations involving 10 sillumiran. In other words, we have 10 slots we want to fill with 10 people.

 

Well, in the first slot we have 10 choices from which to choose. Regardless of whom we choose to fill that slot, the second slot will only have 9 choices. The third will have 8, and so forth. The final tenth spot will have 1 choice, since all prior slots will have been filled.

 

So we then have 10 * 9 * 8 * … * 2 * 1 = 3,628,800 possible permutations of our 10 sillumiran. Commander Uell has many to choose! Instead of writing these ten numbers out, let us simplify this to say we have 10 “factorial” (from here on denoted as “!”) possible permutations. In general, we say n! = n * (n-1) * (n-2) * … * 3 * 2 * 1 where n >= 1.

 

 

 

 

 

Choice Theory

 

 

Suppose now Commander Uell has a special mission that only a handful of his 10 sillumiran need to conduct. Let us say he only needs 4 sillumiran for this mission. How many possible ways can he choose 4 from his 10? In general, how can we choose k things from a set of n items where k is less than or equal to n?

 

Let us denote n choose k as choose(n, k). First we select a k-element string in which the digits are the elements of the set of [n] (the integers 1 through n). We can do this in n! / (n-k)! ways. And yet in these strings the order of the elements does matter. In fact, each k-element subset occurs k! Times among these strings as its elements can be permuted into k! Ways. Therefore, the number of k-element subsets is 1 / k! Times the number of k-element strings. So then choose(n, k) = (1 / k!) * [n! / (n-k)!] = n! / [k! * (n-k)!].

 

So back to Uell’s problem, we have choose(10, 4) = 10! / (4! * 6!) = 210 possible ways to select 4 sillumiran from our 10 total.

 

 

 

 

 

Northeastern Graph Paths

 

 

Commander Uell must now chart the course to his squad’s destination. He realizes that their goal lies 10 miles north and 10 miles east of elCihi (an astute mathematician might notice that the destination is about 14 miles due northeast, but that is a story for another time). To maximize both efficiency and undetectability, Uell instructs his squad to only move either 1 mile north or 1 mile east at a time. How many possible paths can his squad take?

 

Let us define a graph to be a two-dimensional plane formed by the perpendicular intersection of two lines. Both lines contain some number of points evenly spaced apart extending in either direction. All of these linear points are numbered, starting at 0 and extending until some number.

 

In our case, Uell correctly points out that if we were to look at a map and consider elCihi to be at (0, 0), or at the intersection of our two axes, then his squad’s destination would be at (10, 10). We want to find the number of possible routes to get from (0, 0) to (10, 10) by only moving either north or east 1 mile at a time.

 

Let n be the number of points heading either east or north. So for every n, we then have n points east and n points north. So n + n = 2n. If we were to exclusively head east and arrive at (n, 0), we must then by default head north as heading further east would entreat us to head west at some point in violation of our rule. This holds true no matter what path we take to get to (n, n): that we take n steps to get there. So we have choose(2n, n).

 

Back to Uell’s problem, as our n = 10 then we have choose(20, 10) = 20! / (10! * 10!) = 2,217,072. Uell has quite a number of routes from which to choose!

Edited December 9, 2021 by d0ntc4r3

[High_On_Math 399]

Ooc: High_On_Math squeals in joy as she reads a fantasy role play explanation of permutations.

Irp: Luthriel reads intently, "This Gallo is the epitome of what an elf should strive to be.  From their use of Haelunorian examples, I wonder if they live there. If so, I must endeavor to take their mind off that illogical city and ask them to join me in my plans.  . . Regardless, I want to meet them." The elfess grabs two walking sticks and slowly begins to make her way around the small settlement she lived in, looking for someone to write a note for her. 

Edited December 10, 2021 by High_On_Math