Rule of division (combinatorics)
In combinatorics, the rule of division is a counting principle. It states that there are n/d ways to do a task if it can be done using a procedure that can be carried out in n ways, and for each way w, exactly d of the n ways correspond to the way w.
In a nutshell, the division rule is a common way to ignore "unimportant" differences when counting things.[1]
Applied to Sets
In the terms of a set: "If the finite set A is the union of n pairwise disjoint subsets each with d elements, then n = |A|/d."[1]
As a function
The rule of division formulated in terms of functions: "If f is a function from A to B where A and B are finite sets, and that for every value y ∈ B there are exactly d values x ∈ A such that f (x) = y (in which case, we say that f is d-to-one), then |B| = |A|/d."[1]
Examples
Example 1
- How many different ways are there to seat four people around a circular table, where two seatings are considered the same when each person has the same left neighbor and the same right neighbor?
- To solve this exercise we must first pick a random seat, and assign it to person 1, the rest of seats will be labeled in numerical order, in clockwise rotation around the table. There are 4 seats to choose from when we pick the first seat, 3 for the second, 2 for the third and just 1 option left for the last one. Thus there are 4! = 24 possible ways to seat them. However, since we only consider a different arrangement when they don't have the same neighbours left and right, only 1 out of every 4 seat choices matter.
- Because there are 4 ways to choose for seat 1, by the division rule (n/d) there are 24/4 = 6 different seating arrangements for 4 people around the table.
Example 2
- We have 6 coloured bricks in total, 4 of them are red and 2 are white, in how many ways can we arrange them?
- If all bricks had different colours, the total of ways to arrange them would be 6! = 720, but since they don't have different colours, we would calculate it as following:
- 4 red bricks have 4! = 24 arrangements
- 2 white bricks have 2! = 2 arrangements
- Total arrangements of 4 red and 2 white bricks = 6!/4!2! = 15.
See also
Notes
- ↑ 1.0 1.1 1.2 Rosen 2012, pp.385-386
References
- Rosen, Kenneth H (2012). Discrete Mathematics and Its Applications. McGraw-Hill Education. ISBN 978-0077418939.
Further reading
- Leman, Eric; Leighton, F Thompson; Meyer, Albert R; Mathematics for Computer Science, 2018. https://courses.csail.mit.edu/6.042/spring18/mcs.pdf
 |  |
