Enumerative combinatorics

The enumerative combinatorics is a part of combinatorics. It deals with determining the number of possible arrangements or selections

• Distinguishable or indistinguishable objects (that is, " without " and " with " repetition of the same objects ) and
• ( "ordered" that is, or " disordered" ) with or without regard to their order.

In the modern Combinatorics these selections or arrangements are also considered as illustrations, so that the task of combinatorics may limit in this context essentially on counting these pictures.

Applications

For the computation with probabilities on the basis of the concept of probability of Laplace combinatorics forms an important basis.

An amazing phenomenon of combinatorics is that often can be combined with few objects in many ways. At the magic cube, for example, the 26 elements can be combined to around 43 trillion ways. This phenomenon is often referred to as combinatorial explosion and is also the cause of the so-called birthday paradox.

Permutations, variations and combinations

Term accruals

Due to the variety of approaches the spellings and terminology in the field of combinatorics are unfortunately often quite uneven. Although all authors consistently refer to the change in the order of a set of distinguishable elements as a permutation. If one chooses, however, of these elements only elements from whose order is subsequently reversed, described by many authors that now. Than variation, ordered sample or combined with consideration of the order, while others ( particularly in English-speaking countries ) than permutation You finally can with such a selection of elements whose order aside, such a selection is now commonly called disordered sample, combination out of sequence or just combination. Combinations must, provided nothing is further said to them, usually disordered, permutations and / or ordered variations, however, the question of whether permutations as special cases of variations (or vice versa ) is considered, where appropriate answers vary from author to author.

All in all, there are so first of all three (or even two) different questions, which in turn are again divided on whether there should be also repeats the same elements among the selected elements or not. In the former case, one speaks of combinations, variations or permutations with repetition, otherwise those without repetition. Finally, If you imagine that the selected elements of the transformation of an urn or the like are taken, is accordingly also spoken by sampling with or without replacement:

Put down

Denotes the number of elements present and the number of elements which can not be distinguished, then, for the number of possible permutations,:

Denotes the number of elements present and the number of elements to be selected, the following applies for the number of possible variations and combinations:

Balls and subjects

A generalization of the urn model is called a popularized by Gian- Carlo Rota model with balls and subjects in English, as suggested by Joel Spencer also twelvefold Way ( "Twelve Multiple way"). Wanted is the number of ways to distribute balls on subjects, where the balls and compartments are each either distinguishable or indistinguishable and either no condition shall or may come at most one ball in each subject or must arrive at least one ball. This gives the following overview:

This is the number of ways to split a - element set into nonempty disjoint subsets ( Stirling number of the second kind ), and the number of ways to display the number as a sum of positive integers without regard to the order (see partition function).

Equivalent representations

If in a discrete probability space, the number of possible events given by one of the above combinatorial formulas, then equivalent representations for them can be derived from the complete disassembly of the event space. The following two models illustrate this. There are randomly distributed to subjects balls. Consider the events that subjects, at least one ball included under the premise:

The first case corresponds to the variant ' indistinguishable balls, distinct compartments '. The complete decomposition of event space into the disjoint events then gives

The second case corresponds to the variant ' distinguishable balls, distinct compartments '. The complete decomposition of event space analogous to the first case yields the equivalent representation

For the event that all the subjects have at least one ball, equal to the event that all subjects have exactly one ball, and contains elements. It follows