Combinatorics
  Combinatorics Defined
Here we just look at the different ways to generate combinations or variations of "things" (= elements) that belong to a certain set.
The "things" or elements in a set (always denoted by { }) could be some numbers, for example: {0, 1, 2, ..., 9}. They could be some letters of the alphabet, e.g.: {a, b, c, ..., f}, the atoms of a crystal; the people on this earth, in Europe, or in your hometown - you get the drift. We generally assume that the complete set {N} has N such elements.
We then define subsets {k} that contain only k elements from some given set - for example eight letters from the set {a, b, c, ..., f}, a certain number n of atoms from a set of {N} atoms - and then ask what kind of combinations, variations, or relations are possible between {N} and {k}.
Note that we do not ask what you can do with the k elements after you made your choice of this subset.
I need to make that very clear: If we have, for example, a set {N9} = {0, 1, 2, ..., 9} with 9 elements, and form a subset with three members picked from {N9}, we may ask:
  • How many possibilities are there to pick three members from {N9 }? Or, in other words: how many different subsets can I make given the set {N9 }?
  • We do not ask: How many different numbers can I form with the picked subset {2,4,5}?
That forbidden question seems to be perfectly fine, so why don't we allow it?
Because the set {k} = {2,4,5} has no relation anymore with its parent {N9} = {0, 1, 2, ..., 9}. It is a subset of {N9}, allright, but after it was defined it became a set of its own. How many numbers you can form with the integers 2,4,5 is completely independent of {N9}. In the disallowed question you are actually asking about subsets of {N3}. You do not have to know some {N} to answer that question. So it is not an eligible question if you want to look at relations between {N9} and some {k}.
This is a bit abstract, so let's look at examples for allowed questions:
Starting with the set {N} = {0, 1, 2, ..., 9} we may ask:
  1. How many subsets {N3} containing three numbers can we form with the elements of the set {0,1,2,....,9}, allowing everything. It is then allowed that the number encoded by the elements of the subset starts with "0" , e.g. {0,3,4}, encoding 043, is allowed. Having identical elements, e.g. {k} = {3,3,3} is also allowed. Moreover, variations of the sequence of elements is allowed; for example {0,3,4} is then a set different from {3,0,4} and so on.
  2. How many sets {N5} with five digits can we form, but allowing only distinguishable elements? That means that, e.g., neither {3,3,3,3,3} is allowed, nor {1,2,3,4,3}?
  3. How many subsets {Nk} with k elements can we form, allowing only distinguishable elements and counting all different arrangements of the same elements as identical (i.e. {123}; {231}; {312}, ...are not counted as different sets?
  4. .... (Insert your own question).
It is obvious and aggravating: Even for the most simple examples, there is no end of questions you can ask concerning the formation of subsets. Some of those questions may even bear some relation to reality. For example, one of those questions for the subset {N4} may contain the answer of how man different numbers one can make with four digits. But to get a proper answer you must first ask the proper question and then find the solution!
Some answers to possible questions are rather obvious, some certainly are not. For some, you might feel that you would find the answer given enough time; others you might feel are hopeless; at least for you, or possibly for everybody?
Moreover, for some answers you have a feeling or some rough idea of what the result could be. It's just clear that all problems involving three digits have less than 1.000 possibilities, and that with more restrictions the number of possibilities will decrease. For other problems, however, you may not have the faintest idea of what the result might be. That is a big problem for all of us who work with combinatorics only occasionally. You might be completely wrong—but you may not notice it, in contrast to many other problems.
If you are a halfway normal human being, you have by now developed a strong dislike to combinatorics. That is a sound instinct. I know nobody who actually likes it, and I do know a few rather warped scientists. Well, you don't need to be able to do combinatorics yourself, so you can stop reading right here. But if you read on you might learn an interesting thing or two that you then can forget again.
While it is easy to ask combinatorial questions, combinatorics as a math discipline is rather abstract. So how to get a grasp of it? That is an easy question: Study combinatorics as mathematical discipline for quite some time, and you will get there.
In particular you will find out that there is a small number of standard cases that include many of the typical questions we posed above, and that there are standard formulas for the answers. Let's summarize these standard cases in what follows.
     
  Standard Cases of Combinatorics
Quite generally, we look at a situation where we have N elements in a set and ask for the number of possibilities to generate subsets with k of those elements.
Some Examples:
  • The elements are the natural numbers {0, 1, 2, ..., 9}; i.e. N = 10. With k = 3 we now ask how many subsets we can form with 3 of those elements. It is the same as asking how many numbers one can form with three integers (allowing 0 as first digit)
  • The elements are (infinitely many) of two different things (e.g. § and ©; yes and no; place occupied, place free; ...) How many different subsets or strings consisting of k = 6 elements can you form (e.g. §©§ §§©; ©©©§©§, and so on)?
  • The elements are N coins all lined up and with face up. How many different strings can you form if you flip k coins over?
The questions we ask, however, are not yet specific enough to allow a definite answer. We have to construct 2 × 2 = 4 general cases or groups of questions.
First we have to distinguish between two basic possibilities of selecting elements for the combinatorial task:
  1. We only allow different elements. We pick, e.g. 2 or 9 of the 10 given elements 0, 1, 2, ...9; or generally k different elements. Obviously k £ 10 applies. For k = 3, we may thus pick {1,2,3}, or {0, 5,7}, but not {1,1,2} or {3,3,5}.
    However, this just means that you can pick a given element only once but not necessarily that you have it only once in your subset! If we look, for example at the set {N} = {1,1,1,2,3,4} and have k = 4, we may select the sets {1,1,1,3}, or {1,1,2,4}, because {N} contains three "1's". Only, e.g., {1,1,1,1} would be forbidden. Of course, it is a bit confusing that this case includes subsets where the elements look identical, even so they are not, according to the definition we used.
  2. We allow identical elements. Again we pick k elements, but we may pick any element as often as we like, at most, of course, k times. If we work with {N} = {1,2,3, ... ,9} and pick three elements, we now might use {1,1,1}, {1,1,2}, {1,2,2}, {1,2,3}, while only {1,2,3} would have been allowed in the case of different elements from above
Second , we have to distinguish between two basic possibilities of arranging the elements. An arrangement in this sense, simply speaking, can be anything that allows to visualize the combinations we make with the elements selected - e.g. a string as shown above. We then have two basic possibilities:
  1. Different arrangements of the same elements count as different combinations/variations. (1,3,2) thus is a string different from (3,1,2) if we work with different elements from the {0,1,2,3,...,9} set. Likewise, (1,1,3) is a string different from (1,3,1) if identical elements are allowed.
  2. Different arrangements of the same elements do not count as different combinations/variations. (1,2,3), (3,1,2), (2,1,3), (2,3,1), and so on, then would all count as one case or string. Note that it does not matter, if the arrangements are really indistinguishable or not, but only if what they encode is indistinguishable. For example, the string 1,2,3, interpreted in a straight-forward as the number hundred-twenty-three (123), is certainly distinguishable from the number 312. Both strings, however, would be indistinguishable arrangements if they are, for example, interpreted as the the sequence of arranging electrons in a conduction band (132 = take an electron from the first atom, then one from the third and finally one from the second, and put them into the conduction band).
For the following I use the natural numbers as elements of the set {N} to give examples.
We now can produce the following table for the four basic cases:
 

Case Distinction
We must select different elements We may select identical elements.
Different arrangements of the same elements count.
("Distinguishable arrangements")		 Different arrangements of the same elements do not count
("Indistinguishable arrangements")		 Different arrangements of the same elements count. Different arrangements of the same elements do not count.
We ask for the number of possible Variations
VD(k, N)		 We ask for the number of possible Combinations
CD(k, N)		 We ask for the number of possible Variations
VI(k, N)		 We ask for the number of possible Combinations
CI(k, N)
CD(k, N)  =  N!
(N – k)!
     
   =  æ
è 		N
k		 ö
ø 		 · k!
CI(k, N)  =  N!
(N – k)! · k!
           
   =   æ
è 		N
k		 ö
ø 		 
VD(k, N)  =  N k
VI(k, N)  =  (N + k – 1)!
(N – 1)! · k!
         
   =   æ
è 		 N + k – 1
k		 ö
ø
Examples
N = {1,3,4,5}
k = 3
All 3-digit numbers with different elements


CD(k, N) = 4!/1! = 24:

134, 143, 135, 153, 145, ...
 N = {1,3,4,5}
k = 3
3-digit numbers with different elements and only one combination

CD(k, N) = 24/k! = 24/6 = 4:

134, 135, 145, 345		 N = {0,3, ... ,9)
k = 3
All 3-digit numbers



VD(k, N) = 10 3 = 1000:

000, 001, ... , 455, ... , 999		 N = {1,3,4,}
k = 2
All 2-digit numbers with only one combination


CD(k, N) =4!/2! · 2! = 6:

11, 12, 22, 13, 23, 33

 
Since the fraction marked in red comes up all the time in combinatorics, it has been given its own symbol and name.
We define the binomial coefficient of N and k as
   
æ
è 		N
k		 ö
ø 		 =  Binomial
coefficient		  =  N!
(N – k)! · k!
   
Yes - it is a bit mind boggling. But it is not quite as bad as it appears.
The third column gives an obvious result. How many three digit numbers can you produce if you have 0 - 9 and every possible combination is allowed (i.e,. 001 = 1 etc.) and counted. Yes - all numbers from 000, 001, 002, ..., 998, 999 - makes exactly 1000 combinations, or CD(k, N) = 103 as the formula asserts.
Always ask yourself: Am I considering a variation ( all possible arrangement counts) or a combination ("indistinguishable" 1)  arrangements don't count separately)?
Look at it from the practical point of view, not from the formal one, and you will get into the right direction without too much trouble.
The rest you have to take on faith—or you really must apply yourself to combinatorics.
All the more complicated questions not yet contained in the cases above - e.g. we do not allow the element "0" as the first digit, we allow one element to be picked k 1 times, a second one k2 times and so on, may be constructed by various combinations of the 4 cases (and note that I don't say " easily constructed").
 

Arrangement of Vacancies

OK. For the example given, the cases may be halfway transparent. But how about the arrangement of vacancies in a crystal? What are the elements of this combinatorial problem, and what is k?
The elements obviously are the N atoms of the crystal. The subset k equally obviously selects k = nV = number of vacancies of these elements.
This is exactly the "confusing" case mentioned above: All elements in {N} look the same; nevertheless it makes a difference if I allow identical or different elements for {k}. We can make the situation a bit more transparent if we number the atoms in our thoughts.
Now what exactly is the question to ask? There are often many ways in stating the same problem, but one way might be better than others in order to see the structure of the problem.
We could ask for example:
  • How many ways do we have to arrange nV vacancies in a crystal with N atoms? That's the question, of course, but it just does not go directly with the math demonstrated above.
  • How many digital numbers can we produce with N – nV "1's" and nV zeros? Here we simply count the vacancies as zero's. Good question, but still not too clear with respect to the cases above.
  • We have N numbered atoms. How many possibilities do we have to select nV  different elements? Moreover, we don't care about the arrangement of the atoms taken out, all "numbers" we could produce with the numbered atoms we have taken out counts as one arrangement.
It is clear now that we have to take the "different elements" and "different arrangements of the same elements do not count" case - which indeed gives us the correct formula.
 
1) There is a certain paradox here: In order to explain in words that certain arrangements are indistinguishable, we have to list them separately, i.e. we distinguish them. But that is not a real problem, just a problem with words.

With frame With frame as PDF

go to 4.3.1 Nirvana for Crystals

go to The Second Law and Computer Science

go to Entropy

go to Making Vacancies

© H. Föll (Iron, Steel and Swords script)