How to conceptualize "dividing out" a number (e.g. in permutations, Bayes' Theorem)?

Question

I'm trying to achieve a better conception of what it means to "divide out" a variable/number, because I'm currently have a lot of trouble justifying to myself why it actually works the way it does in certain contexts. I apologize if this is too much of an elementary question but I can't seem to come to a satisfying conclusion.

I understand division in the context of explicit numbers but here (see pg. 3) is an example of where I get confused:

"so the number of ways of selecting r objects and ignoring all permutations of the remaining $(n − r)$ objects not chosen is to divide out the unwanted permutations:

No. of perms. $= \dfrac{1 \times 2 \times 3 \times···\times (n − r) \times (n − r + 1) \times··· \times(n − 1) \times n}{1 \times 2 \times 3 \times··· \times (n − r)}$"

So basically, why does this work, and how would explain it to a clever 5 year old?

Similarly, what does it mean to "divide out" $P(B)$ in the classic representation of Bayes' Theorem, i.e.

$P(A|B) = \dfrac{P(B|A)P(A)}{P(B)}$?

Answer 1

Look at the number of permutations of $3$ things out of $5$. Call the five things $ABCDE$. $$ \begin{array}{c|c|ccc} \overbrace{\begin{array}{cccc} ABC & ACB & ADB & AEB \\ ABD & ACD & ADC & AEC \\ \underbrace{ABE}_B & \underbrace{ACE}_C & \underbrace{ADE}_D & \underbrace{AED}_E \end{array}}^{\text{starting with $A$}} & \overbrace{\begin{array}{cccc} BAC & BCA & BDA & BEA \\ BAD & BCD & BDC & BEC \\ \underbrace{BAE}_A & \underbrace{BCE}_C & \underbrace{BDE}_D & \underbrace{BED}_E \end{array}}^{\text{starting with $B$}} & \cdots\cdots\cdots\cdots\cdots \end{array} $$ When three are listed in some order, the first one could be $A$ or $B$ or $C$ or $D$ or $E$. Five choices. Only two are listed above, but you can see what the other three are. Within each of those, the second can be any of four. And the third can be any of three. So the total number of permutations in the list is $5\times 4\times3= 60$.

So what if we want combinations rather than permutations. Notice that one of the permutations listed above is $BEC$. In how many orders can $BEC$ be listed? Here they are: $$ \overbrace{BCE\quad BEC}^\text{starting with $B$} \quad \overbrace{CBE\quad CEB}^\text{starting with $C$} \quad \overbrace{EBC\quad ECB}^\text{starting with $E$} $$ It is listed $3\times2\times1=6$ times. That means that this combination got listed $6$ times in the first list above. Every combination got listed $6$ times. So divide the length of the first list by $6$: $$ \frac{5\times4\times3}{3\times2\times1} = \frac{60}{6} = 10. $$ In other words, the number of combinations is $10$.

Answer 2

I won't attempt to explain this to a clever $5$ year old; but anyway, you are (tacitly) looking for the following definition/theorem pair.

Definition. Let $X$ denote a set non-empty set. Then given an equivalence relation $\sim$ on $X$, call $\sim$ regular iff there exists a natural number $n$ such that for all $x \in X,$ the corresponding cell $x^\sim$ has cardinality $n$.

If $\sim$ is regular, write $|\!\sim\!|$ for the cardinality of any (and hence every) cell of $\sim$.

POSSIBLE SOURCE OF CONFUSION: The number $|\!\sim\!|$ will usually be distinct from the number $|X/\!\sim\!|$, which is the number of cells corresponding to $\sim$. Nevertheless, these numbers are far from independent:

Theorem. Let $X$ denote a set non-empty set and $\sim$ denote a regular equivalence relation on $X$. Then: $$|X/\!\sim\!| = |X|/|\!\sim\!|$$

We can apply this to your example as follows. Given a set $X$ and cardinal numbers $b$ and $a$, write $\Pi_S(b,a)$ for the subset of $\mathcal{P}(X) \times \mathcal{P}(X)$ given as follows:

$(B,A) \in \Pi_X(b,a)$ iff:

• $|B| = b$
• $|A| = a$
• $\{B,A\}$ partitions $X$.

We're trying to show that:

Theorem. If $X$ is a finite set and $b,a$ are cardinal numbers with $b+a = |X|$, then: $$|\Pi_X(b,a)| = \frac{|\mathrm{Lo}(X)|}{\mathrm{Lo}(b)\mathrm{Lo}(a)}$$

where I define $\mathrm{Lo}(X)$ as the set of linear orderings of $X$, and $\mathrm{Lo}(b)$ as the number of ways of linearly ordering any (and hence every) set with $b$ elements. Of course, we secretly know that $\mathrm{Lo}(b) = b!$, but this is really irrelevant to the argument that follows:

Proof. Fix $X$, $b$ and $a$. There is a function $\pi^b : \mathcal{P}(X) \leftarrow \mathrm{Lo}(X)$ that takes a linear ordering of $X$ to the set of all elements in the final $b$-long stretch, and another function $\pi_a : \mathcal{P}(X) \leftarrow \mathrm{Lo}(X)$ that takes a linear ordering of $X$ to the set of all elements in the initial $a$-long stretch. This yields a function:

$$\langle \pi^b,\pi_a\rangle : \mathcal{P}(X) \times \mathcal{P}(X) \leftarrow \mathrm{Lo}(X)$$

It turns out that this mapping has image equal to $\Pi_X(b,a)$. Hence:

$$|\Pi_X(b,a)| = \left|\frac{\mathrm{Lo}(X)}{\mathrm{coimg}(\langle \pi^b,\pi_a\rangle)}\right|$$

It also turns out that the equivalence relation induced on $\mathrm{Lo}(X)$, namely $\mathrm{coimg}(\langle \pi^b,\pi_a\rangle),$ is regular. Hence:

$$|\Pi_X(b,a)| = \frac{|\mathrm{Lo}(X)|}{|\mathrm{coimg}(\langle \pi^b,\pi_a\rangle)|}$$

In fact, we can find the number of elements in any (and hence every) cell of this partitioning explicitly:

$$|\mathrm{coimg}(\langle \pi^b,\pi_a\rangle)| = \mathrm{Lo}(b)\mathrm{Lo}(a)$$

Hence:

$$|\Pi_X(b,a)| = \frac{|\mathrm{Lo}(X)|}{\mathrm{Lo}(b)\mathrm{Lo}(a)}$$

Edit. Another way of formulating this argument is with the notion of a $k$-bijection, see my answer here.