Rule of division (combinatorics)

In combinatorics, the rule of division is a counting principle. It states that there are {{math|n/d}} ways to do a task if it can be done using a procedure that can be carried out in {{mvar|n}} ways, and for each way {{mvar|w}}, exactly {{mvar|d}} of the {{mvar|n}} ways correspond to the way {{mvar|w}}.

In a nutshell, the division rule is a common way to ignore "unimportant" differences when counting things.{{harvnb|Rosen|2012|loc=pp.385-386}}

Applied to Sets

In the terms of a set: "If the finite set {{mvar|A}} is the union of n pairwise disjoint subsets each with {{mvar|d}} elements, then {{math|1=n = {{!}}A{{!}}/d}}."

== As a function ==

The rule of division formulated in terms of functions: "If {{mvar|f}} is a function from {{mvar|A}} to {{mvar|B}} where {{mvar|A}} and {{mvar|B}} are finite sets, and that for every value {{math|y ∈ B}} there are exactly {{mvar|d}} values {{math|x ∈ A}} such that {{math|1=f (x) = y}} (in which case, we say that {{mvar|f}} is {{mvar|d}}-to-one), then {{math|1={{!}}B{{!}} = {{!}}A{{!}}/d}}."

Examples

File:Round table rule of division.gif

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 ({{math|n/d}}) there are {{math|1=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 {{math|1=6! = 720}}, but since they don't have different colours, we would calculate it as following:

:4 red bricks have {{math|1=4! = 24}} arrangements

:2 white bricks have {{math|1=2! = 2}} arrangements

:Total arrangements of 4 red and 2 white bricks = {{math|1={{sfrac|6!|4!2!}} = 15}}.

Notes

== References ==

{{cite book |last=Rosen |first=Kenneth H |title=Discrete Mathematics and Its Applications |publisher=McGraw-Hill Education |year=2012 |isbn=978-0077418939}}

Rule of division (combinatorics)

Applied to Sets

Examples

See also

Notes

Further reading