Rule of division (combinatorics)

Short description: Counting principle

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.

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."

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."

Examples

Visual representation for the round table example

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

• Combinatorial principles

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