In combinatorics, the rule of division is a counting principle. It states that there are ways to do a task if it can be done using a procedure that can be carried out in ways, and for each way , exactly of the ways correspond to the way . In a nutshell, the division rule is a common way to ignore "unimportant" differences when counting things.
Applied to Sets
In the terms of a set: "If the finite set is the union of n pairwise disjoint subsets each with elements, then ."
As a function
The rule of division formulated in terms of functions: "If is a function from to where and are finite sets, and that for every value there are exactly values such that (in which case, we say that is -to-one), then ."
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 () there are 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 , but since they don't have different colours, we would calculate it as following:
4 red bricks have arrangements
2 white bricks have arrangements
Total arrangements of 4 red and 2 white bricks = .
See also
Notes
References
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