Combination

A combination (from the Latin combinatio "Summary" ) or unordered sample is in combinatorics a selection of objects in which the order is disregarded. Can objects are selected multiple times, then one speaks of a combination with repetition, each object can only appear once on a combination without repetition. The determination of the number of possible combinations is a standard task of enumerative combinatorics.

• 3.1 Number
• 3.2 set representation
• 3.3 Examples 3.3.1 gummy bear oracle
• 3.3.2 urn
• 3.3.3 cube

Distinction between

A combination or unordered sample is a selection of objects from a set of objects in which the order of selection does not matter. If the order still play a role, we speak instead of a combination of a variation. Deviating sometimes combinations and variations are summarized in the literature, and a variation is then called " combined with consideration of the order ."

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

Combination without repetition

Number

Selection problems without repetition can be examined in two ways. In the classical case, a procedure is a variation without repetition for which there are opportunities to be selected at of elements. But the selected items may in turn be arranged in various ways. When these various arrangements all play a role, so again should be considered as the same selection of items, we have the result obtained again by share, and receive so that only

Possibilities, which is also referred to as binomial coefficient.

A second, especially in the evaluation of Bernoulli experiments, application -find approach reflects a combination without repetition, as a placement problem. The number of possible selections can then be determined by the fact that it determines the number of distinguishable arrangements of selected and non-selected objects, which are no longer to be distinguished from each other themselves, thus " selected " the total output quantity only in the two object classes ( " not selected " for example, black ball with white numbers) and (eg white ball with black number) is divided. If one looks at how many different arrangements of these black and white balls there, with only their color is to play a role, is obtained according to the formula for the number of permutations of elements, each class-wise indistinguishable, the above formula. Whether the number of selected objects and the number of non-selected objects, or vice versa, is irrelevant to the result; which of the two subsets of the output quantity which is of interest, has no influence on the number of possible splits.

Set representation

The amount

Is the " set of all combinations without repetition of objects to class" and has the above specified number of elements. An alternative representation of this quantity is

Examples

Lotto

Now, if you want to select without repetition and without regard to the order of objects, as is the case for example in the lottery draw, there is this

Possible choices. In Lotto, the order does not matter whether the first instance and then the first or the and then drawn, does not matter for the winning numbers and the determination of the lottery winner. The number of possible solutions is calculated from the number of first and then balls that can be drawn, ie. However, because the order does not matter, it must be considered that the product comprises equivalent solutions. Three drawn numbers is the number of ways, but because the drawing order of the balls does not matter, the product should be divided by the number of possible drawing orders.

Number of ways

The mural in the Wismar Holy Spirit Church is in the middle of the letter "D " on the bottom left and an "S". If you go just steps to the left and down, always results in the text " Deogracias ". Overall, it is nine steps, though you have five times a step to the right and go four times a down. There are

Opportunities. But you can also five times to the right and go up four times, or left and bottom or left and above. Overall, the results in this example from options. This task is usually referred to as the Manhattan problem, named after the New York City borough with the regular road.

Combination with repetition

Number

Shall be selected elements from a set of elements, their order should continue to be of no importance, but they now also have to repeat yourself, how is this possible eg when sampling with replacement, the following formula is obtained for the number of possibilities ( see multiset ):

This is apparent when one is a result of each of the selected elements of possible elements of a sequence of symbols, said symbols ( "N"), the elements of the selected set, and symbols ( "K" ) representing the selected items. The sequence always starts with an N- symbol; K the number of symbols of the second N- symbol corresponds to the frequency with which the first of the elements has been drawn, the number of symbols K between the second and third N- symbol to the second of the elements, etc. Since the up to first "N", all symbols can be freely combined, the number of combinations and hence the number of possible moves to the formula given.

For example, corresponds to the choice of 3 of 5 elements ("1 ", "2 ", " 3", " 4", " 5") with replacement the result is " 1, 3, 3 ' of the symbol sequence " NKNNKKNN ", the result " 5, 5, 5 'of the sequence" NNNNNKKK ". This results in possible combinations.

Set representation

The amount

Is the " set of all combinations with repetition of things to the class " and has the above specified number of elements. Herein, the number of occurrences of the - th element of the sample. An alternative representation of this quantity is

Examples

Gummy bear oracle

One application of this is the so-called gummy bear oracle, in which one selects bear from a bag of gummy bears in different colors. Accordingly, there is

Different combinations. There are five key combinations in which all bear the same color, combinations of two different colors, three colors, four colors and one with all five colors. Would it arrive when pulling on the order, you would have to do with a "Variation with repetition ," that is with options. The same number to get at the question of the number of options, four pins from a stock of pencils with six different colors to choose ( Mastermind order is not important ). On the other hand there is the "right" Mastermind ( the order is important ) ways.

Urn

From an urn containing five numbered balls will be drawn three times a ball and each put back. So you can select all three draws always from five balls. If one does not take into account the order of the numbers drawn, there are

Different combinations. These combinations with repetition of five things to class three, so three-element multisets with elements from the initial amount, correspond, as the adjacent chart shows exactly the combinations without repetition of seven things to class three, ie the number Three-element subsets of a total siebenelementigen output quantity. ( The existence of a bijection can be used to prove the formula for the number of combinations with replacement. )

Cube

The same replacement is the use of several identical objects, such as cubes with one to six eyes. How many litters are possible with three dice? Basically different litters are possible if you throw a cube at a time and observe the order. If all three dice are thrown simultaneously, however, it can be useful to say no more order. Since the simultaneous throw all three dice, for example, the union of or is no longer distinguishable, there is only

Different ( distinguishable ) throws. Not to be confused with it is the sum of the eyes, which can only assume different values ​​(from to).