Combinatorics

Here we just look at the different ways to generate combinations or variations of "things" (= elements) belonging to a certain set of things.
The set of "things" could be the numbers {0, 1, 2, ..., 9}; the letters {a, b, c, ..., f} of the alphabet; 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 has N such elements.
We then define subsets {k} that contain k elements from the set {0...9}; eight letters, a certain number n of atoms, and ask what kind of combinations or variations are possible between N and k.
Note that we do not ask what you can do with k elements after you made a choice.
To make that clear: If we have, for example, N = {0, 1, 2, ..., 9}, and k = 3, we may ask: How many possibilites are there to pick three members of N? We do not ask: How many different numbers can I form with the subset {2,4,5}?
That seems to be a good question, so why don't we allow it? Because the set {k} = {2,4,5} has no relation anymore with {N}. How many numbers you can form with the integers 2,4,5 is completely independent of {N}; so it is not an eligible question if want to look at relations between {N} and {k}.
This is a bit abstract, so let's look at examples:
For the first example we may ask:
  • How many three digit numbers (or subsets) can we form with the elements of the set {0,1,2,....,9} allowing everything (e.g. that the number starts with "0", e.g. 043, and that we may have identical elements, e.g. {k} = {3,3,3} is allowed)
  • How many numbers with five digits can we form, but allowing only distinguishable elements? That means that, e.g., neither k = {3,3,3,3,3} is allowed, nor the number 12343.
  • How many "numbers" with k digits can we form, allowing only distinguishable elements and counting all different arrangements of the same elements as identical (i.e. 123; 231; 312, ...are seen as one "number" or arrangement.
It is obvious: Even for the most simple examples, there is no end of questions you can ask concerning possible arrangements of your elements.
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; some you might feel are hopeless - just 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 and makes combinatorics often very abstract.
How to be systematic about this? That is an easy question: Study combinatorics - a mathematical discipline - for quite some time and you will find out.
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.
Quite generally, we look at a situation where we have N elements and ask for the number of arrangements we can produce 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 numbers we can form with 3 of those elements.
  • The elements are two different things (e.g. § and ©, yes and no, place occupied, place free, ...) How many different strings (or other arrangements) 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 elicite 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, it just means that you can pick a given element only once. If we look 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", but not, e.g., {1,1,1,1}. 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 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 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 than 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 123, interpreted as the number hundred-twenty-three, is certainly distinguishable form 312, but both strings would be indistinguishable arrangements if. e.g., interpreted as the the sequence of arranging electrons (132 = take an electron from the first atom, then one from the third and finally one from the second and put them "in a box").
Sticking to natural numbers as elements of the set {N} for 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

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

134, 135, 145, 345
CD(k, N) = 24/k! = 24/6 = 4		 N = {0,3, ... ,9)
k = 3
All 3-digit numbers

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

11, 12, 22, 13, 23, 33
CD(k, N) =4!/2! · 2! = 6
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 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 k1 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 vancanies 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 that we derived from scratch in exercise 2.1-4
 

1) There is a certain paradoxon here: In order to explain in words that certain arrangements are indistinguisghable, 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 2.1.1 Simple Vacancies and Interstitials

go to Basic Exercise 2-1-4: Derive the Formula for the Vacancy Equilibrium Concentration

go to Exercise 2.1-7 Quick Questions

© H. Föll (Defects - Script)