SafekipediaIn combinatorics, the twelvefold way is a smart way to group twelve similar problems about counting things. It helps us understand how to count different arrangements of objects. For example, it can show us how many ways we can pick items from a group or how to organize them.
This idea was created by a mathematician named Gian-Carlo Rota. Another mathematician, Joel Spencer, gave it the name "twelvefold way."
The twelvefold way looks at problems with two groups of items. It helps us answer questions like how many ways we can match items from one group to another, or how many ways we can split items into groups. It includes classic counting problems such as permutations—the different ways to arrange items in order, combinations—the ways to choose items without worrying about the order, and multisets—where items can be chosen more than once.
This way of thinking is important in many areas of mathematics and computer science. It helps us solve complex counting problems in an organized and efficient way. By grouping these twelve problems together, mathematicians can see how they are related and use solutions from one problem to help solve others.
Overview
The twelvefold way is a way to count and organize different types of problems in math. It shows how we can pair up elements from one group with elements from another group, following certain rules.
There are three main rules for how elements can be paired:
- No rules: any element can pair with any other, and elements can pair more than once.
- One-to-one pairing: each element can only pair with one other element.
- At least one pairing: every element in the second group must pair with at least one element from the first group.
We can also look at these pairings in four different ways:
- Exactly as they are.
- Ignoring the order of elements in the first group.
- Ignoring the order of elements in the second group.
- Ignoring the order in both groups.
By combining these rules and ways of looking at pairings, we get 12 different counting problems. Some of these problems are easy, some have simple formulas, and others need more complex math to solve. This helps us understand many classic counting problems, like how many ways we can arrange or group items.
Main article: Twelvefold way
Viewpoints
The twelvefold way looks at problems in different ways. One way is to think about putting balls into boxes. Each ball goes into one box, and boxes can hold many balls. Some rules change how we count these arrangements.
Another way uses sampling, like picking items from a group. We can pick items and put them back (sampling with replacement) or not put them back (sampling without replacement). Sometimes the order we pick items matters, and sometimes it does not. These choices help us count different ways to make selections.
Formulas
Formulas for the different cases of the twelvefold way are shown in a table. Each table entry links to a section below that explains the formula.
The notations used are:
- the falling factorial power
- the rising factorial power
- the factorial
- the Stirling number of the second kind
- the binomial coefficient
- the Iverson bracket encoding a truth value as 0 or 1
- the number pk(n) of partitions of n into k parts
Intuitive meaning of the rows and columns
Imagine you have a set of X numbered items. You choose n of them, making an ordered list.
The columns mean:
Any f
After you choose an item, you put it back, so you might choose it again.
Injective f
After you choose an item, you set it aside, so you can't choose it again. You'll end up with n distinct items.
Surjective f
After you choose an item, you put it back, so you might choose it again — but in the end, you must have chosen each item at least once.
The rows mean:
Distinct
Leave the lists alone; count them directly.
Sn orbits
Before counting, sort the lists by the item number, so order doesn't matter.
Sx orbits
Before counting, renumber the items seen so the first item seen is number 1, the second is 2, and so on.
Sn × Sx orbits
Two lists count as the same if you can reorder and relabel them to get the same result.
Intuitive meaning of the chart using balls and boxes scenario
The chart below is similar to the chart above, but instead of showing formulas, it helps you understand their meaning using the familiar balls and boxes example.
Details of the different cases
The cases below are ordered to group those with related counting arguments.
Functions from N to X
This case is the same as counting sequences of n elements of X with no restriction.
Injective functions from N to X
This case is the same as counting sequences of n distinct elements of X, also called n-permutations of X, or sequences without repetitions.
Injective functions from N to X, up to a permutation of N
This case is the same as counting subsets with n elements of X, also called n-combinations of X.
Functions from N to X, up to a permutation of N
This case is the same as counting multisets with n elements from X (also called n-multicombinations).
Surjective functions from N to X, up to a permutation of N
This case is the same as counting multisets with n elements from X, where each element of X occurs at least once.
Injective functions from N to X, up to a permutation of X
In this case we look at sequences of n distinct elements from X, but we consider those the same if you can get one from the other by applying a permutation of X.
Injective functions from N to X, up to permutations of N and X
Surjective functions from N to X, up to a permutation of X
This case is the same as counting partitions of N into x (non-empty) subsets, or counting equivalence relations on N with exactly x classes.
Surjective functions from N to X
This case is the same as counting sequences of n elements from X, where each element of X occurs at least once.
Functions from N to X, up to a permutation of X
This case is like the corresponding one for surjective functions, but some elements of x might not correspond to any equivalence class.
Surjective functions from N to X, up to permutations of N and X
This case is the same as counting partitions of the number n into x non-zero parts.
Functions from N to X, up to permutations of N and X
This case is the same as counting partitions of the number n into ≤ x parts.
Extremal cases
The formulas above work for all finite sets N and X. In some cases there are other formulas that are almost the same, but they do not give the correct result in some extreme cases, such as when N or X are empty.
| f {\displaystyle f} -class | Any f {\displaystyle f} | Injective f {\displaystyle f} | Surjective f {\displaystyle f} |
|---|---|---|---|
| Distinct f | n-sequence in X x n {\displaystyle x^{n}} | n-permutation of X x n _ {\displaystyle x^{\underline {n}}} | composition of N with X subsets x ! { n x } {\displaystyle x!\left\{{n \atop x}\right\}} |
| Sn orbits f ∘ Sn | n-multisubset of X ( x + n − 1 n ) {\displaystyle {\binom {x+n-1}{n}}} | n-subset of X ( x n ) {\displaystyle {\binom {x}{n}}} | composition of n with x terms ( n − 1 n − x ) {\displaystyle {\binom {n-1}{n-x}}} |
| Sx orbits Sx ∘ f | partition of N into ≤ x subsets ∑ k = 0 x { n k } {\displaystyle \sum _{k=0}^{x}\left\{{n \atop k}\right\}} | partition of N into ≤ x elements [ n ≤ x ] {\displaystyle [n\leq x]} | partition of N into x subsets { n x } {\displaystyle \left\{{n \atop x}\right\}} |
| Sn×Sx orbits Sx ∘ f ∘ Sn | partition of n into ≤ x parts p x ( n + x ) {\displaystyle p_{x}(n+x)} | partition of n into ≤ x parts 1 [ n ≤ x ] {\displaystyle [n\leq x]} | partition of n into x parts p x ( n ) {\displaystyle p_{x}(n)} |
| Any f (no rules on placement) | Injective f (no multi-packs allowed) | Surjective f (no empty boxes allowed) | |
|---|---|---|---|
| f (Balls and boxes marked) | n-sequence in X How many ways can you place n marked balls into x marked boxes, with no other rules on placement? | n-permutation in X How many ways can you place n marked balls into x marked boxes, with no multi-packs allowed? | composition of N with x subsets How many ways can you place n marked balls into x marked boxes, with no empty boxes allowed? |
| f ∘ Sn (Balls plain, boxes marked) | n-multisubset of X How many ways can you place n plain balls into x marked boxes, with no other rules on placement? | n-subset of X How many ways can you place n plain balls into x marked boxes, with no multi-packs allowed? | composition of n with x terms How many ways can you place n plain balls into x marked boxes, with no empty boxes allowed? |
| Sx ∘ f (Balls marked, boxes plain) | partition of N into ≤ x subsets How many ways can you place n marked balls into x plain boxes, with no other rules on placement? | partition of N into ≤ x elements How many ways can you place n marked balls into x plain boxes, with no multi-packs allowed? | partition of N into x subsets How many ways can you place n marked balls into x plain boxes, with no empty boxes allowed? |
| Sx ∘ f ∘ Sn (Balls and boxes plain) | partition of n into ≤ x parts How many ways can you place n plain balls into x plain boxes, with no other rules on placement? | partition of n into ≤ x parts 1 How many ways can you place n plain balls into x plain boxes, with no multi-packs allowed? | partition of n into x parts How many ways can you place n plain balls into x plain boxes, with no empty boxes allowed? |
Generalizations
We can expand the ideas of the twelvefold way by thinking about different kinds of arrangements. By using special groups of permutations, we can study new ways to organize things. This leads to ideas like cyclic and dihedral permutations.
There is also something called the twentyfold way, created by Kenneth P. Bogart. It looks at how objects can go into boxes when both the objects and boxes might be the same or different. He found 20 different cases to consider.
| No. | Objects | Condition of distribution | Recipients | |
|---|---|---|---|---|
| Distinct | Identical | |||
| 1 | Distinct | No restriction | n-sequence in X x n {\displaystyle x^{n}} | partition of N into ≤ x subsets ∑ i = 0 x { n i } {\displaystyle \sum _{i=0}^{x}\left\{{n \atop i}\right\}} |
| 2 | At most one each | n-permutation of X x n _ {\displaystyle x^{\underline {n}}} | { 1 if n ≤ x 0 otherwise {\displaystyle {\begin{cases}1&{\text{if }}n\leq x\\0&{\text{otherwise}}\end{cases}}} | |
| 3 | At least one each | composition of N with x subsets x ! { n x } {\displaystyle x!\left\{{n \atop x}\right\}} | partition of N into x subsets { n x } {\displaystyle \left\{{n \atop x}\right\}} | |
| 4 | Exactly one each | n ! = x ! {\displaystyle n!=x!} permutations | { 1 if n = x 0 otherwise {\displaystyle {\begin{cases}1&{\text{if }}n=x\\0&{\text{otherwise}}\end{cases}}} | |
| 5 | Distinct, ordered | No restriction | ( n + x − 1 ) n _ {\displaystyle (n+x-1)^{\underline {n}}} ordered functions | ∑ i = 1 x L ( n , i ) {\displaystyle \sum _{i=1}^{x}L(n,i)} broken permutations ( ≤ x {\displaystyle \leq x} parts) Where L ( n , i ) {\displaystyle L(n,i)} is the Lah number |
| 6 | At least one each | ( n ) x _ ( n − 1 ) n − x _ {\displaystyle (n)^{\underline {x}}(n-1)^{\underline {n-x}}} ordered onto functions | L ( n , x ) = ( n x ) ( n − 1 ) n − x _ {\displaystyle L(n,x)=\left({n \atop x}\right)(n-1)^{\underline {n-x}}} broken permutations (x parts) Where L ( n , x ) {\displaystyle L(n,x)} is the Lah number | |
| 7 | Identical | No restriction | n-multisubset of X ( x + n − 1 n ) {\displaystyle \left({x+n-1 \atop n}\right)} | ∑ i = 1 x p i ( n ) {\displaystyle \sum _{i=1}^{x}p_{i}(n)} number partitions ( ≤ x {\displaystyle \leq x} parts) |
| 8 | At most one each | n-subset of X ( x n ) {\displaystyle \left({x \atop n}\right)} | { 1 if n ≤ x 0 otherwise {\displaystyle {\begin{cases}1&{\text{if }}n\leq x\\0&{\text{otherwise}}\end{cases}}} | |
| 9 | At least one each | ( n − 1 x − 1 ) {\displaystyle \left({n-1 \atop x-1}\right)} compositions (x parts) | partition of n into x parts p x ( n ) {\displaystyle p_{x}(n)} | |
| 10 | Exactly one each | { 1 if n = x 0 otherwise {\displaystyle {\begin{cases}1&{\text{if }}n=x\\0&{\text{otherwise}}\end{cases}}} | { 1 if n = x 0 otherwise {\displaystyle {\begin{cases}1&{\text{if }}n=x\\0&{\text{otherwise}}\end{cases}}} | |
This article is a child-friendly adaptation of the Wikipedia article on Twelvefold way, available under CC BY-SA 4.0.