Twelvefold way

From Wikipedia for FEVERv2
Jump to navigation Jump to search

In combinatorics, the twelvefold way is a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number. Twelvefold way_sentence_0

The idea of the classification is credited to Gian-Carlo Rota, and the name was suggested by Joel Spencer. Twelvefold way_sentence_1

Overview Twelvefold way_section_0

The functions are subject to one of the three following restrictions: Twelvefold way_sentence_2

There are four different equivalence relations which may be defined on the set of functions f from N to X: Twelvefold way_sentence_3

Twelvefold way_ordered_list_0

  1. equality;Twelvefold way_item_0_0
  2. equality up to a permutation of N;Twelvefold way_item_0_1
  3. equality up to a permutation of X;Twelvefold way_item_0_2
  4. equality up to permutations of N and X.Twelvefold way_item_0_3

The three conditions on the functions and the four equivalence relations can be paired in 3 × 4 = 12 ways. Twelvefold way_sentence_4

The twelve problems of counting equivalence classes of functions do not involve the same difficulties, and there is not one systematic method for solving them. Twelvefold way_sentence_5

Two of the problems are trivial (the number of equivalence classes is 0 or 1), five problems have an answer in terms of a multiplicative formula of n and x, and the remaining five problems have an answer in terms of combinatorial functions (Stirling numbers and the partition function for a given number of parts). Twelvefold way_sentence_6

The incorporation of classical enumeration problems into this setting is as follows. Twelvefold way_sentence_7

Twelvefold way_unordered_list_1

Viewpoints Twelvefold way_section_1

The various problems in the twelvefold way may be considered from different points of view. Twelvefold way_sentence_8

Balls and boxes Twelvefold way_section_2

Traditionally many of the problems in the twelvefold way have been formulated in terms of placing balls in boxes (or some similar visualization) instead of defining functions. Twelvefold way_sentence_9

The set N can be identified with a set of balls, and X with a set of boxes; the function ƒ : N → X then describes a way to distribute the balls into the boxes, namely by putting each ball a into box ƒ(a). Twelvefold way_sentence_10

Thus the property that a function ascribes a unique image to each value in its domain is reflected by the property that any ball can go into only one box (together with the requirement that no ball should remain outside of the boxes), whereas any box can accommodate (in principle) an arbitrary number of balls. Twelvefold way_sentence_11

Requiring in addition ƒ to be injective means forbidding to put more than one ball in any one box, while requiring ƒ to be surjective means insisting that every box contain at least one ball. Twelvefold way_sentence_12

Counting modulo permutations of N or X (or both) is reflected by calling the balls or the boxes, respectively, "indistinguishable". Twelvefold way_sentence_13

This is an imprecise formulation (in practice individual balls and boxes can always be distinguished by their location, and one could not assign different balls to different boxes without distinguishing them), intended to indicate that different configurations are not to be counted separately if one can be transformed into the other by some interchange of balls or of boxes. Twelvefold way_sentence_14

This possibility of transformation is formalized by the action by permutations. Twelvefold way_sentence_15

Sampling Twelvefold way_section_3

Another way to think of some of the cases is in terms of sampling, in statistics. Twelvefold way_sentence_16

Imagine a population of X items (or people), of which we choose N. Two different schemes are normally described, known as "sampling with replacement" and "sampling without replacement". Twelvefold way_sentence_17

In the former case (sampling with replacement), once we've chosen an item, we put it back in the population, so that we might choose it again. Twelvefold way_sentence_18

The result is that each choice is independent of all the other choices, and the set of samples is technically referred to as independent identically distributed. Twelvefold way_sentence_19

In the latter case, however, once we've chosen an item, we put it aside so that we can't choose it again. Twelvefold way_sentence_20

This means that the act of choosing an item has an effect on all the following choices (the particular item can't be seen again), so our choices are dependent on one another. Twelvefold way_sentence_21

In the terminology below, the case of sampling with replacement is termed "Any f", while the case of sampling without replacement is termed "Injective f". Twelvefold way_sentence_22

Each box indicates how many different sets of choices there are, in a particular sampling scheme. Twelvefold way_sentence_23

The row labeled "Distinct" means that the ordering matters. Twelvefold way_sentence_24

For example, if we have ten items, of which we choose two, then the choice (4,7) is different from (7,4). Twelvefold way_sentence_25

On the other hand, the row labeled "Sn orders" means that ordering doesn't matter: Choice (4,7) and (7,4) are equivalent. Twelvefold way_sentence_26

(Another way to think of this is to sort each choice by the item number, and throw out any duplicates that result.) Twelvefold way_sentence_27

In terms of probability distributions, sampling with replacement where ordering matters is comparable to describing the joint distribution of N separate random variables, each with an X-fold categorical distribution. Twelvefold way_sentence_28

The case where ordering doesn't matter, however, is comparable to describing a single multinomial distribution of N draws from an X-fold category, where only the number seen of each category matters. Twelvefold way_sentence_29

The case where ordering doesn't matter and sampling is without replacement is comparable to a single multivariate hypergeometric distribution, and the fourth possibility does not seem to have a correspondence. Twelvefold way_sentence_30

Note that in all the "injective" cases (i.e. sampling without replacement), the number of sets of choices is zero unless N ≤ X. Twelvefold way_sentence_31

("Comparable" in the above cases means that each element of the sample space of the corresponding distribution corresponds to a separate set of choices, and hence the number in the appropriate box indicates the size of the sample space for the given distribution.) Twelvefold way_sentence_32

From this perspective, the case labeled "Surjective f" is somewhat strange: Essentially, we keep sampling with replacement until we've chosen each item at least once. Twelvefold way_sentence_33

Then, we count how many choices we've made, and if it's not equal to N, throw out the entire set and repeat. Twelvefold way_sentence_34

This is vaguely comparable to the coupon collector's problem, where the process involves "collecting" (by sampling with replacement) a set of X coupons until each coupon has been seen at least once. Twelvefold way_sentence_35

Note that in all "surjective" cases, the number of sets of choices is zero unless N ≥ X. Twelvefold way_sentence_36

Labelling, selection, grouping Twelvefold way_section_4

A function ƒ : N → X can be considered from the perspective of X or of N. This leads to different views: Twelvefold way_sentence_37

Twelvefold way_unordered_list_2

  • the function ƒ labels each element of N by an element of X.Twelvefold way_item_2_10
  • the function ƒ selects (chooses) an element of the set X for each element of N, a total of n choices.Twelvefold way_item_2_11
  • the function ƒ groups the elements of N together that are mapped to the same element of X.Twelvefold way_item_2_12

These points of view are not equally suited to all cases. Twelvefold way_sentence_38

The labelling and selection points of view are not well compatible with permutation of the elements of X, since this changes the labels or the selection; on the other hand the grouping point of view does not give complete information about the configuration unless the elements of X may be freely permuted. Twelvefold way_sentence_39

The labelling and selection points of view are more or less equivalent when N is not permuted, but when it is, the selection point of view is more suited. Twelvefold way_sentence_40

The selection can then be viewed as an unordered selection: a single choice of a (multi-)set of n elements from X is made. Twelvefold way_sentence_41

Labelling and selection with or without repetition Twelvefold way_section_5

When viewing ƒ as a labelling of the elements of N, the latter may be thought of as arranged in a sequence, and the labels as being successively assigned to them. Twelvefold way_sentence_42

A requirement that ƒ be injective means that no label can be used a second time; the result is a sequence of labels without repetition. Twelvefold way_sentence_43

In the absence of such a requirement, the terminology "sequences with repetition" is used, meaning that labels may be used more than once (although sequences that happen to be without repetition are also allowed). Twelvefold way_sentence_44

For an unordered selection the same kind of distinction applies. Twelvefold way_sentence_45

If ƒ must be injective, then the selection must involve n distinct elements of X, so it is a subset of X of size n, also called an n-combination. Twelvefold way_sentence_46

Without the requirement, a same element of X may occur multiple times in the selection, and the result is a multiset of size n of elements from X, also called an n-multicombination or n-combination with repetition. Twelvefold way_sentence_47

In these cases the requirement of a surjective ƒ means that every label is to be used at least once, respectively that every element of X be included in the selection at least once. Twelvefold way_sentence_48

Such a requirement is less natural to handle mathematically, and indeed the former case is more easily viewed first as a grouping of elements of N, with in addition a labelling of the groups by the elements of X. Twelvefold way_sentence_49

Partitions of sets and numbers Twelvefold way_section_6

When viewing ƒ as a grouping of the elements of N (which assumes one identifies under permutations of X), requiring ƒ to be surjective means the number of groups must be exactly x. Twelvefold way_sentence_50

Without this requirement the number of groups can be at most x. Twelvefold way_sentence_51

The requirement of injective ƒ means each element of N must be a group in itself, which leaves at most one valid grouping and therefore gives a rather uninteresting counting problem. Twelvefold way_sentence_52

When in addition one identifies under permutations of N, this amounts to forgetting the groups themselves but retaining only their sizes. Twelvefold way_sentence_53

These sizes moreover do not come in any definite order, while the same size may occur more than once; one may choose to arrange them into a weakly decreasing list of numbers, whose sum is the number n. This gives the combinatorial notion of a partition of the number n, into exactly x (for surjective ƒ) or at most x (for arbitrary ƒ) parts. Twelvefold way_sentence_54

Formulas Twelvefold way_section_7

Formulas for the different cases of the twelvefold way are summarized in the following table; each table entry links to a subsection below explaining the formula. Twelvefold way_sentence_55

The particular notations used are: Twelvefold way_sentence_56

Intuitive meaning of the rows and columns Twelvefold way_section_8

This is a quick summary of what the different cases mean. Twelvefold way_sentence_57

The cases are described in detail below. Twelvefold way_sentence_58

Then the columns mean: Twelvefold way_sentence_59

And the rows mean: Twelvefold way_sentence_60

Twelvefold way_unordered_list_3

  • Distinct: Leave the lists alone; count them directly.Twelvefold way_item_3_13
  • Sn orbits: Before counting, sort the lists by the item number of the items chosen, so that order doesn't matter, e.g. (5,2,10), (10,2,5), (2,10,5), etc. all → (2,5,10).Twelvefold way_item_3_14
  • Sx orbits: Before counting, renumber the items seen so that the first item seen has number 1, the second 2, etc. Numbers may repeat if an item was seen more than once, e.g. (3,5,3), (5,2,5), (4,9,4), etc. → (1,2,1) while (3,3,5), (5,5,3), (2,2,9), etc. → (1,1,2).Twelvefold way_item_3_15
  • Sn×Sx orbits: Before counting, sort the lists and then renumber them, as described above. (Note: Renumbering then sorting will produce different lists in some cases, but the number of possible lists does not change.)Twelvefold way_item_3_16

Details of the different cases Twelvefold way_section_9

The cases below are ordered in such a way as to group those cases for which the arguments used in counting are related, which is not the ordering in the table given. Twelvefold way_sentence_61

Functions from N to X Twelvefold way_section_10

This case is equivalent to counting sequences of n elements of X with no restriction: a function f : N → X is determined by the n images of the elements of N, which can each be independently chosen among the elements of x. Twelvefold way_sentence_62

This gives a total of x possibilities. Twelvefold way_sentence_63

Injective functions from N to X Twelvefold way_section_11

This case is equivalent to counting sequences of n distinct elements of X, also called n-permutations of X, or sequences without repetitions; again this sequence is formed by the n images of the elements of N. This case differs from the one of unrestricted sequences in that there is one choice fewer for the second element, two fewer for the third element, and so on. Twelvefold way_sentence_64

Therefore instead of by an ordinary power of x, the value is given by a falling factorial power of x, in which each successive factor is one fewer than the previous one. Twelvefold way_sentence_65

The formula is Twelvefold way_sentence_66

Note that if n > x then one obtains a factor zero, so in this case there are no injective functions N → X at all; this is just a restatement of the pigeonhole principle. Twelvefold way_sentence_67

Injective functions from N to X, up to a permutation of N Twelvefold way_section_12

Functions from N to X, up to a permutation of N Twelvefold way_section_13

This case is equivalent to counting multisets with n elements from X (also called n-multicombinations). Twelvefold way_sentence_68

The reason is that for each element of X it is determined how many elements of N are mapped to it by f, while two functions that give the same such "multiplicities" to each element of X can always be transformed into another by a permutation of N. The formula counting all functions N → X is not useful here, because the number of them grouped together by permutations of N varies from one function to another. Twelvefold way_sentence_69

Rather, as explained under combinations, the number of n-multicombinations from a set with x elements can be seen to be the same as the number of n-combinations from a set with x + n − 1 elements. Twelvefold way_sentence_70

This reduces the problem to another one in the twelvefold way, and gives as result Twelvefold way_sentence_71

Surjective functions from N to X, up to a permutation of N Twelvefold way_section_14

This case is equivalent to counting multisets with n elements from X, for which each element of X occurs at least once. Twelvefold way_sentence_72

This is also equivalent to counting the compositions of n with x (non-zero) terms, by listing the multiplicities of the elements of x in order. Twelvefold way_sentence_73

The correspondence between functions and multisets is the same as in the previous case, and the surjectivity requirement means that all multiplicities are at least one. Twelvefold way_sentence_74

By decreasing all multiplicities by 1, this reduces to the previous case; since the change decreases the value of n by x, the result is Twelvefold way_sentence_75

Note that when n < x there are no surjective functions N → X at all (a kind of "empty pigeonhole" principle); this is taken into account in the formula, by the convention that binomial coefficients are always 0 if the lower index is negative. Twelvefold way_sentence_76

The same value is also given by the expression Twelvefold way_sentence_77

The form of the result suggests looking for a manner to associate a class of surjective functions N → X directly to a subset of n − x elements chosen from a total of n − 1, which can be done as follows. Twelvefold way_sentence_78

First choose a total ordering of the sets N and X, and note that by applying a suitable permutation of N, every surjective function N → X can be transformed into a unique weakly increasing (and of course still surjective) function. Twelvefold way_sentence_79

If one connects the elements of N in order by n − 1 arcs into a linear graph, then choosing any subset of n − x arcs and removing the rest, one obtains a graph with x connected components, and by sending these to the successive elements of X, one obtains a weakly increasing surjective function N → X; also the sizes of the connected components give a composition of n into x parts. Twelvefold way_sentence_80

This argument is basically the one given at stars and bars, except that there the complementary choice of x − 1 "separations" is made. Twelvefold way_sentence_81

Injective functions from N to X, up to a permutation of X Twelvefold way_section_15

Injective functions from N to X, up to permutations of N and X Twelvefold way_section_16

Surjective functions from N to X, up to a permutation of X Twelvefold way_section_17

Surjective functions from N to X Twelvefold way_section_18

Functions from N to X, up to a permutation of X Twelvefold way_section_19

Surjective functions from N to X, up to permutations of N and X Twelvefold way_section_20

Functions from N to X, up to permutations of N and X Twelvefold way_section_21

Extremal cases Twelvefold way_section_22

The above formulas give the proper values for all finite sets N and X. Twelvefold way_sentence_82

In some cases there are alternative formulas which are almost equivalent, but which do not give the correct result in some extremal cases, such as when N or X are empty. Twelvefold way_sentence_83

The following considerations apply to such cases. Twelvefold way_sentence_84

Twelvefold way_unordered_list_4

  • For every set X there is exactly one function from the empty set to X (there are no values of this function to specify), which is always injective, but never surjective unless X is (also) empty.Twelvefold way_item_4_17
  • For every non-empty set N there are no functions from N to the empty set (there is at least one value of the function that must be specified, but it cannot).Twelvefold way_item_4_18
  • When n > x there are no injective functions N → X, and if n < x there are no surjective functions N → X.Twelvefold way_item_4_19
  • The expressions used in the formulas have as particular valuesTwelvefold way_item_4_20

Generalizations Twelvefold way_section_23

The twentyfold way Twelvefold way_section_24

Another generalization called the twentyfold way was developed by Kenneth P. Bogart in his book "Combinatorics Through Guided Discovery". Twelvefold way_sentence_85

In the problem of distributing objects to boxes both the objects and the boxes may be identical or distinct. Twelvefold way_sentence_86

Bogart identifies 20 cases. Twelvefold way_sentence_87

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: way.