= Rule of product
{title2=$|A_1\times\cdots\times A_k|=\prod_{j=1}^k|A_j|$}
{wiki}
= Multiplication principle
{synonym}
For finite <sets>, the number of ordered choices of one element from each is the product of the individual numbers of choices. More generally, if stage $j$ has exactly $n_j$ possible choices after every permitted history of earlier stages, the total number of full choice sequences is $\prod_j n_j$, by <mathematical induction> on the stages. This counts $b^a$ <functions> between sets of sizes $a,b$, and counts the <injective functions> by the <falling factorial> $b(b-1)\cdots(b-a+1)$ when $a\le b$.
With five people, choose a captain in five ways and a different deputy in four ways: \b[$5\cdot4=20$ ordered assignments]. The second choice depends on the first because the captain is excluded, but its number of permitted options is always four. The <rule of product> therefore applies without any assumption about <independent events>. To count two-person teams instead, each <subset> has two possible role assignments, so division by $2!=2$ gives ten teams. This division works because every team was counted equally often.
Back to article page
