# Combinatorics

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!
(Nk)! · k!

=   æ
è
N
k
ö
ø

VD(k, N)  =  N k
VI(k, N)  = æ è ö ø
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 æ è ö ø
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.

2.1.1 Simple Vacancies and Interstitials

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

Exercise 2.1-7 Quick Questions

© H. Föll (Defects - Script)