Das ist ein Modul aus dem "Defects" Hyperscript, der aber hier auch sehr gut paßt. | ||

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 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 such elements. The
elements can be different or identical - the set N{1,2,3,4,5 } has 5 different elements, the set {1,1,1,1,1}
has 5 identical elements, for example. | ||

We then define subsets
{ that contain k} elements from the set k{0...9}; eight letters, a certain number
of atoms, and ask what kind of combinations or variations are possible between n and N.k |
||

Note that we do not primariliy ask what you
can do with elements after you made a choice.k | ||

To make that clear: If we have, for example, ,
and N = {0, 1, 2, ..., 9}, we may ask: How many possibilites are there to pick three members of k = 3? That's a
"legal" question. However, we do Nnot first 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 { has no relation anymore with k}
= {2,4,5}{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 {.
This does k}not mean that we can not answer the question of how many numbers..., too -
if we phrase it correctly, that is! | ||

This is a bit abstract, so let's look at examples: | ||

For the first example we may ask:- How many possibilities do we have to pick three elements from set
**{0,1,2,....,9}**allowing everything. This*also*would answer the question of how many general three-digit numbers including "numbers" that start with "**0**", e.g.**043**we could make. - How many possibilities do we have to pick three elements from set
**{0,1,2,....,9}**if we always pick different elements. - How many possibilities do we have to pick three elements from set
**{0,1,2,....,9}**while counting all different arrangements of the same elements as identical (i.e.**123**;**231**;**312**, ...are not counted as different subsets.
| ||

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 given enough time you would eventually find the answer; 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 elements
and ask for the number of arrangements we can produce with N of those elements.k | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Some Examples:- The elements are the natural numbers
**{0, 1, 2, ..., 9}**; i.e.. With*N*= 10we now ask how many different strings = different*k*= 3*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
elements can you form (e.g. §©§§§©; ©©©§©§, and so on)?*k*= 6 - The elements are
coins all lined up and with face up. How many*N**different strings*can you form if you flipcoins over?**k**
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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:- 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. Obviouslyapplies. For*k*£ 10, we may thus pick*k*= 3**{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}**. - We allow
*identical*elements. Again we pickelements, but we may pick any element as often as we like, at most, of course,*k*times. If we work with**k****{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:*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 differemt 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.*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 the 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: | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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 and N ask | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

Yes - it is a bit mind boggling. But it is not quite as bad as it appears. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

The first 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 C as the formula asserts.^{D}(k, N)
= 10^{3} | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

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
times, a second one k_{1} times and so on, may be constructed by various combinations of the k_{2}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 atoms of the crystal. The subset
N equally obviously selects k of these elements.k = n_{V} = number of vancanies |
||

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
vacancies in a crystal with*n*_{V}atoms? That's the question, of course, but it just does not go directly with the math demonstrated above.**N** - How many digital numbers can we produce with
"*N*–*n*_{V}**1's**" andzeros? Here we simply count the vacancies as zero's. Good question, but still not too clear with respect to the cases above**n** - We have
**N***numbered*atoms. How many possibilities do we have to select*n*_{V}*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 "identical 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

5.3.3 Gleichgewichtskonzentration von atomaren Fehlstellen in Kristallen

5.3.2 Definition der Entropie und erste Anwendung

Ableitung der Gauss Verteilung

Übung 5.3-2 Gleichgewichtskonzentration an Leerstellen

Übung 5-1 Anordnungsmöglichkeiten

© H. Föll (MaWi 1 Skript)