The division rule 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 every way w, exactly d of the n ways correspond to way w"
I really can't understand this definition. Is there a easy way to explain this rule, not using math terms?
$\endgroup$3 Answers
$\begingroup$I guess the best way to explain this is with an example.
Let's say we want to arrange $(1,1,2,3,4)$ in a row.
For example,
$$(1,1,2,4,3),(1,1,3,2,4)$$ Are possible arrangements.
We first assume that the two $1$'s are distinct, so we have $5!$ ways to arrange:
$$(1_a,1_b,2,3,4)$$
But for each of the $5!$ ways, we have over-counted some cases:
$$ (1,1,2,3,4) \begin{cases} (1_a,1_b,2,3,4)\\ (1_b,1_a,2,3,4)\\ \end{cases} $$
$$ (2,1,1,3,4) \begin{cases} (2,1_a,1_b,3,4)\\ (2,1_b,1_a,3,4)\\ \end{cases} $$
$$\vdots $$
Every $2!$ of our initial $5!$ ways corresponds to one actual arrangement.
That is why to arrange $(1,1,2,3,4)$ in a row, we have:
$$\frac{5!}{2!} \space \text{ways}$$
$\endgroup$ $\begingroup$Imagine you have a class of 24 students, which you want to divide into groups of 4 for a project. The number of ways you can choose the 4 students is $24\cdot23\cdot22\cdot21$ - this is $n$. The number of ways you can arrange those 4 students within the group is $4!$ - this is $d$.
So, $\frac{n}{d}$ gives the number of distinct ways to arrange the 24 students into groups of 4. In this case, each "way" is a different combination of students, and exactly $d$ ($4!$) of the ways to pick students correspond to each unique combination of students (since order doesn't matter).
I hope this helps!
$\endgroup$ $\begingroup$I've always heard this explained as:
To count the number of cows in your field, first count the number of legs and then divide by four.
(Not sure who to attribute this to.)
The usual example is counting the number of subsets of size $k$ from $n$ elements. As a first attempt, we could count them by picking $k$ elements in order. We choose any of $n$ elements at first, then any of the $n-1$ elements left, and continue, for $$n \cdot (n-1) \cdots (n- k +1)$$ choices. But we have overcounted here, since subsets are unordered. Each subset $S \subseteq \{1,2, \ldots, n\}$ of size $k$ will be counted exactly $k!$ times in the above expression. So the number of subsets of size $k$ is $${ n \choose k} = \frac{ n(n-1)\cdots(n-k+1)}{k!}.$$ Each "cow" ( a subset $S \subseteq \{1,2, \ldots, \}$ of size $k$) has exactly $k!$ "legs" (the orderings of $S$).
I know you said no math terms, so you can ignore this part if you want. Let's say you want to count the size of a set $Y$, but it's a bit hard to count. Instead you count a set $X$, and find a surjective function $f:X \rightarrow Y$. If $f$ is $m$-to-one, so that for each $y \in Y$ there are exactly $m$ elements $x \in X$ so that $f(x) = y$. Then we will have $$|Y| = |X|/m.$$
This can be seen bijectively: I claim that there is a bijection $\phi: X \rightarrow Y \times \{1,2, \ldots, m\}$. Then it will follow that $m|Y| = |X|$. To get the bijection $\phi$ we just use $f$, but keep track of what our input was so we can go backward. For convenience, put some ordering on $X$. Then let $\phi(x) = (y,i)$ where $y = f(x)$ and $x$ is the $i$th element of $X$ that maps to $Y$. Exercise: show $\phi$ is a bijection.
In the above example, we let $Y$ be the set of all subsets of size $k$ of the set $\{1,2, \ldots, n\}$, and let $X$ be the set of ordered sets $(x_1, x_2, \ldots, x_k)$ of elements of $X$ with no repetition. Then define $f: X \rightarrow Y$ to map the ordered set $(x_1, \ldots, x_k)$ to the unordered set $\{x_1, \ldots, x_k\}$. For each set $S \in Y$ there are exactly $k!$ orderings of $S$, so the map $f: X \rightarrow Y$ is $k!$-to one. e.g., $(1,2,3), (1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$ all map to the same set $\{1,2,3\}$.
$\endgroup$
