2.3.2 A More General Product Rule

• If a six-sided die is tossed five times in succession
  • rather than just twice,
• then each possible outcome is an ordered collection of five numbers
  • such as $\left(1,3,1,2,4\right)$ or $(6,5,2,2,2)$ .

$k$-tuple

• We will call an ordered collection of $k$ objects a $k$-tuple
• so
  • a pair is a 2-tuple and
  • a triple is a 3-tuple).

Each outcome of the die-tossing experiment is then a 5-tuple.

Product Rule for $k$-Tuples

Suppose

• a set consists of ordered collections of $k$ elements ($k$-tuples)
• there are $n_1$ possible choices for the first element;
  • for each choice of the first element,
    • there are $n_2$ possible choices of the second element
  • …
  • for each possible choice of the first $k-1$ elements,
    • there are $n_k$ choices of the $k$-th element.
• Then there are $n_1{n}_2\cdots \cdots n_k$ possible $k$ -tuples.

• An alternative interpretation involves carrying out an operation in $k$ stages.

• If

  • the first stage can be performed in any one of $n_1$ ways,
  • and for each such way there are $n_2$ ways to perform the second stage,
  • and for each way of performing the first two stages there are $n_3$ ways to perform the $3^{\text{rd }}$ stage,
  • and so on,

• then $n_1{n}_2\cdots \cdot n_k$ is the number of ways to carry out the entire $k$ -stage operation in sequence. This more general rule can also be visualized with a tree diagram.

• For the case $k=3$,

  • simply add an appropriate number of $3^{\mathrm{rd}}$ generation branches to the tip of each $2^{\mathrm{nd}}$ generation branch.

• If, for example, a college town has

  • four pizza places,
  • a theater complex with six screens,
  • three places to go dancing,

• then there would be

  • four $1^{\text{st }}$ generation branches,
  • six $2^{\text{nd }}$ generation branches emanating from the tip of each $1^{\text{st }}$ generation branch,
  • and three $3^{\text{rd }}$ generation branches leading off each $2^{\text{nd }}$ generation branch.

• Each possible 3-tuple corresponds to the tip of a $3^{\text{rd }}$ generation branch.

EX 2.19

(Example 2.17 continued)

• Suppose the home remodeling job involves first purchasing several kitchen appliances.
  • They will all be purchased from the same dealer,
  • and there are five dealers in the area.
  • With the dealers denoted by $D_1,\dots ,D_5$ ,
  • there are $N=n_1{n}_2{n}_3=\left(5\right)\left(12\right)\left(9\right)=540$ 3-tuples of the form $\left(D_i,P_j,Q_k\right)$,
• so there are 540 ways to choose
  • first an appliance dealer,
  • then a plumbing contractor,
  • and finally an electrical contractor.

EX 2.20

(Example 2.18 continued)

• If each clinic has both
  • three specialists in internal medicine and
  • two general surgeons,
• there are $n_1{n}_2{n}_3{n}_4=\left(4\right)\left(3\right)\left(3\right)\left(2\right)=72$ ways to select one doctor of each type
  • such that all doctors practice at the same clinic.