Partial permutation

A variation (from the Latin variatio "change" ) or ordered sample is in combinatorics a selection of objects in a particular order. Can objects are selected multiple times, then one speaks of a variation with repetition, each object can only appear once on a variation without repetition. The determination of the number of possible variations is a standard task of enumerative combinatorics.

  • 3.1 Number
  • 3.2 set representation
  • 3.3 Examples

Distinction between

A variation or ordered sample is a selection of objects from a set of objects, where the order of selection matters. If all available objects selected, so true, we speak instead of a variation of a permutation, plays in the selection of objects, the order does not matter from a combination.

In a variation with repetition objects can be selected more than once, while a variation of each object can only appear once without repetition. In an urn model corresponds to a variation with repetition of a drawing of the balls with replacement and a variation without repeating a selection without replacement.

Deviating sometimes variations and combinations are summarized in the literature, and a variation is then called " combined with consideration of the order ." In particular, in English usage, variations and permutations are summarized and then variations called "k - permutations " (k- permutations ).

Variation without repetition

Number

In a variation without repetition of objects should be placed ( with ) on available spaces, each object at most only allowed to take a seat. There are for the first place possible objects for second place objects, etc. to the -th place, for which there is still potential objects. Overall, there are therefore

Possible arrangements. For these figures, the notations and which are called falling factorial exist. With the Faculty of is called.

Set representation

The amount

, the " set of all variations without repetition of objects to the class ", and has the above mentioned number of elements.

Examples

  • When is drawn from an urn with five different balls three times without replacement, different selections are possible: in the first draw five more ways then just four for the third draw finally only three possibilities.
  • If all five balls are chosen, it follows, accordingly, a total number of possibilities, ie the number of permutations of all five balls.

Variation with repetition

Number

In a variation with repetition objects are selected in accordance with the order of objects, where objects can also be selected more than once. After each of the objects can appear on any of the courses in the selection, there is therefore

Possible arrangements.

Set representation

The amount

Is the " set of all variations with repetition of objects to class ". It is the -fold Cartesian product of the amount with itself and has the above specified number of elements.

Examples

  • When is drawn from an urn with five different balls three times with replacement, then different selections are possible.
  • In a four-digit PIN or a combination lock with four rings and ten digits There are different variations ( 0000-9999 ).
  • In the binary digital technique used consists only of two digits and. With an array of such figures can therefore different variations arise. A four-digit binary coded, for example, different states.
Urn problem Martin Aigner
799023
de