Rule Of Division (combinatorics) on:
[Wikipedia]
[Google]
[Amazon]
In
''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 = .
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
, 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
*Combinatorial principles
In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used.
The rule of sum, rule of product, and inclusion–exclusion principle are often used for Enumerative combinatorics ...
Notes
References
* {{cite book , last=Rosen , first=Kenneth H , title=Discrete Mathematics and Its Applications , publisher=McGraw-Hill Education , year=2012 , isbn=978-0077418939Further reading
* Leman, Eric; Leighton, F Thompson; Meyer, Albert R; Mathematics for Computer Science, 2018. https://courses.csail.mit.edu/6.042/spring18/mcs.pdf Combinatorics