Systematic Counting

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\framed }[0]{\MakeFramed {\advance \hsize -\width \FrameRestore }} \newcommand {\shaded }[0]{\def \FrameCommand {\fboxsep =\FrameSep \colorbox {shadecolor}}\MakeFramed {\FrameRestore }} \newcommand {\shaded* }[0]{\def \FrameCommand {\fboxsep =\FrameSep \colorbox {shadecolor}}\MakeFramed {\advance \hsize -\width \FrameRestore }} \newcommand {\leftbar }[0]{\def \FrameCommand {\vrule width 3pt \hspace {10pt}}\MakeFramed {\advance \hsize -\width \FrameRestore }} \newcommand {\titled-frame }[1]{\def \FrameCommand {\fboxsep 8pt\fboxrule 2pt \TitleBarFrame {\textbf {#1}}}\def \FirstFrameCommand {\fboxsep 8pt\fboxrule 2pt \TitleBarFrame [$\blacktriangleright $]{\textbf {#1}}}\def \MidFrameCommand {\fboxsep 8pt\fboxrule 2pt \TitleBarFrame [$\blacktriangleright $]{\textbf {#1\ (cont)}}}\def \LastFrameCommand {\fboxsep 8pt\fboxrule 2pt \TitleBarFrame {\textbf {#1\ (cont)}}}\MakeFramed {\advance \hsize -20pt \FrameRestore }} \newcommand {\FrameCommand }[0]{\setlength \fboxrule {\FrameRule }\setlength \fboxsep {\FrameSep }\fbox } \newcommand {\FirstFrameCommand }[0]{\FrameCommand } \newcommand {\MidFrameCommand }[0]{\FrameCommand } \newcommand {\LastFrameCommand }[0]{\FrameCommand } \newcommand {\FrameHeightAdjust }[0]{6pt} \newcommand {\bysame }[0]{\mbox {\rule {3em}{.4pt}}\,} \newcommand {\N }[0]{\mathbb N} \newcommand {\C }[0]{\mathbb C} \newcommand {\W }[0]{\mathbb W} \newcommand {\Z }[0]{\mathbb Z} \newcommand {\Q }[0]{\mathbb Q} \newcommand {\R }[0]{\mathbb R} \newcommand {\A }[0]{\mathbb A} \newcommand {\D }[0]{\mathcal D} \newcommand {\F }[0]{\mathcal F} \newcommand {\ph }[0]{\varphi } \newcommand {\ep }[0]{\varepsilon } \newcommand {\aph }[0]{\alpha } \newcommand {\QM }[0]{\begin {center}{\huge \textbf {?}}\end {center}} \newcommand {\le }[0]{\leqslant } \newcommand {\ge }[0]{\geqslant } \newcommand {\a }[0]{\wedge } \newcommand {\v }[0]{\vee } \newcommand {\l }[0]{\ell } \newcommand {\mat }[0]{\mathsf } \newcommand {\vec }[0]{\mathbf } \newcommand {\subset }[0]{\subseteq } \newcommand {\supset }[0]{\supseteq } \newcommand {\emptyset }[0]{\varnothing } \newcommand {\xto }[0]{\xrightarrow } \newcommand {\qedsymbol }[0]{$\blacksquare $} \newcommand {\bibname }[0]{References and Further Reading} \newcommand {\bar }[0]{\protect \overline } \newcommand {\hat }[0]{\protect \widehat } \newcommand {\tilde }[0]{\widetilde } \newcommand {\tri }[0]{\triangle } \newcommand {\minipad }[0]{\vspace {1ex}} \newcommand {\leftexp }[2]{{\vphantom {#2}}^{#1}{#2}} \newcommand {\epsilon }[0]{\varepsilon } \newcommand {\theta }[0]{\vartheta } \newcommand {\l }[0]{\ell } \newcommand {\d }[0]{\,d} \newcommand {\sectionOutcomes }[0]{} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument }$

Problems about systematic counting.

Easy counting problems are easy. But in challenging counting problems, it becomes very important to use a systematic method for listing all of the possibilities. Without a systematic approach, it is to easy to miss some possibilities or to list other possibilities more than once (or both).

Here are some strategies that are very useful when solving such problems:

Fix one choice, and systematically change the other parts through all possibilities. Change the first choice to the next option, and repeat.
List the possibilities in dictionary or numerical order, either forward or backward.

These strategies can be combined. And a “road map” can help you manage the process.

Some examples are given below.

A wedding planner offers three different entrées (Beef, Chicken, and Vegetarian), four different sides (Fruit, Hummus, Pasta, and Salad), and two desserts (Ice cream and Tiramisù). List all of the dinner possibilities.

Solution:: List them in dictionary order: $\begin {array}{c} BFI \\ \answer [format=string]{BFT} \\ \answer [format=string]{BHI} \\ \answer [format=string]{BHT} \\ \answer [format=string]{BPI} \\ \answer [format=string]{BPT} \\ \answer [format=string]{BSI} \\ \answer [format=string]{BST} \\ CFI \\ \answer [format=string]{CFT} \\ \answer [format=string]{CHI} \\ \answer [format=string]{CHT} \\ \answer [format=string]{CPI} \\ \answer [format=string]{CPT} \\ \answer [format=string]{CSI} \\ \answer [format=string]{CST} \\ \answer [format=string]{VFI} \\ \answer [format=string]{VFT} \\ \answer [format=string]{VHI} \\ \answer [format=string]{VHT} \\ \answer [format=string]{VPI} \\ \answer [format=string]{VPT} \\ \answer [format=string]{VSI} \\ \answer [format=string]{VST} \end {array}$ Note that the entrée is fixed first at Beef Chicken Vegetarian with all of the possible side and dessert combinations, in dictionary order.
Good work! Note also that the structure of this listing can help explain why there are $3\times \answer {4}\times \answer {2}=\answer {3\cdot 4\cdot 2}$ possible meals.
Here is a road map that can help you imagine the above list as a process of systematically traveling all possible roads:

PICT

List all right-rectangular prisms of volume $24$ and whole-number sides. Assume the three dimensions are distinguishable.

Solution:: $\begin {array}{|c|c|c|} \hline \text {length} & \text {width} & \text {height} \\ \hline 1 & 1 & 24 \\ 1 & 2 & 12 \\ 1 & 3 & 8 \\ 1 & 4 & 6 \\ 1 & 6 & 4 \\ 1 & 8 & 3 \\ 1 & 12 & 2 \\ 1 & 24 & 1 \\ 2 & 1 & 12 \\ 2 & 2 & 6 \\ 2 & 3 & 4 \\ 2 & 4 & 3 \\ 2 & 6 & 2 \\ 2 & 12 & 1 \\ 3 & 1 & 8 \\ 3 & 2 & 4 \\ 3 & 4 & 2 \\ 3 & 8 & 1 \\ 4 & 1 & 6 \\ 4 & 2 & 3 \\ 4 & 3 & 2 \\ 4 & 6 & 1 \\ 6 & 1 & 4 \\ 6 & 2 & 2 \\ 6 & 4 & 1 \\ 8 & 1 & 3 \\ 8 & 3 & 1 \\ 12 & 1 & 2 \\ 12 & 2 & 1 \\ 24 & 1 & 1 \\ \hline \end {array}$ In the solution, note that when the length has been fixed, the width and height are systematically varied in order of increasing $\answer [format=string]{width}$ . Then, after all of the width-height combinations have been exhausted, the $\answer [format=string]{length}$ is changed to the next allowable value and “refixed,” and the width and height are again systematically varied.

PICT

Some readers may complain that the above list of volume- $24$ prisms contains much duplication. And this would be true if we consider, for example, a $6\times 4\times 1$ prism to be the same as a $4\times 1\times \answer {6}$ prism.

Again, list all right-rectangular prisms of volume $24$ and whole-number sides. This time, assume the three dimensions are not distinguishable.

Solution:: To prevent overcounting, require that $\text {length} \le \text {width} \le \text {height}$ . $\begin {array}{|c|c|c|} \hline \text {length} & \text {width} & \text {height} \\ \hline 1 & 1 & 24 \\ \answer {1} & \answer {2} & \answer {12} \\ \answer {1} & \answer {3} & \answer {8} \\ \answer {1} & \answer {4} & \answer {6} \\ \answer {2} & \answer {2} & \answer {6} \\ \answer {2} & \answer {3} & \answer {4} \\ \hline \end {array}$ How do we know we are done?

The next entry with a length of $2$ would be $(2,4,3)$ , which is already listed—or which violates the condition that $\text {length} \le \text {width} \le \text {height}$ .
The next length possibility would be $3$ , and the first entry in such a row would be $(3,4,2)$ , which is already listed.

PICT

In the red/green light context, list all combinations of $2$ red lights from among $5$ lights.

Solution:: List in dictionary order: $\begin {array}{c} GGGRR \\ \hline \\ \answer [format=string]{GGRGR} \\ \answer [format=string]{GGRRG} \\ \hline \\ \answer [format=string]{GRGGR} \\ \answer [format=string]{GRGRG} \\ \answer [format=string]{GRRGG} \\ \hline \\ \answer [format=string]{RGGGR} \\ \answer [format=string]{RGGRG} \\ \answer [format=string]{RGRGG} \\ \answer [format=string]{RRGGG} \end {array}$ In the solution, note the separations demonstrating that once the position of the first red light is chosen, the $\answer [format=string]{second}$ red light systematically varies among all possible remaining positions, in dictionary order.

PICT