|
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 SetsIn 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 functionThe 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?
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?
See alsoNotes
References
Further reading
|
Portal di Ensiklopedia Dunia
