Difference between revisions of "Constructive counting"

Revision as of 15:06, 24 December 2021

In combinatorics, constructive counting is a counting method where one "constructs" a set to count it. It is a close cousin of casework, as constructive counting usually involves breaking the problem down into several smaller counting problems.

Examples

Here are some problems with solutions that utilize constructive counting. It's worth noting that as problem-solving ability becomes more advanced, there are fewer problems that can be solved by constructive counting alone. At the same time, there are many, many more problems where constructive counting is a crucial intermediate step.

Example 1

How many four-digit numbers are there?

Solution: We break up the problem into the number of choices each digit can be. For the first digit, it can be any number from one to nine (it cannot be zero, or else it ceases have four digits), so it has $9$ options. As for the other three digits, they can be any number from zero to ten, so they all have $10$ options. We then multiply these together to get an answer of $9 \cdot 10 \cdot 10 \cdot 10 = 9000$ . $\square$

This may seem like a frivolous and fruitless trick, but the technique of breaking a problem down into several "choices" is truly fundamental and appears everywhere in combinatorics.

Example 2

How many lists of seven numbers are there such that each entry is between $2$ and $9$ inclusive and no two consecutive entries are equal?

Solution: A constructive approach is the simplest way to attack this question. Let each option be a digit out of the seven numbers. The first digit can be any digit from $2$ to $9$ , of which there are $8$ . The second can be any of $2$ to $10$ too, with the sole exception of the previous digit. Regardless of whatever the first digit is, we know that it removes one option, so there's $8 - 1 = 7$ options for the second digit.

The exact same logic applies to the third digit; it can be any of the $8$ digits except the one before it, so it has $7$ options. This continues until the seventh digit, which means that digits $2$ to $7$ all have $7$ options. Then our answer is $8 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 = 8 \cdot 7^6 = 941,192$ , as desired. $\square$

These two examples use choices specifically based on digits, but this isn't the entire picture of constructive counting. In general, constructive techniques include any breakage of a counting problem into several smaller counting problems. The following example displays this well:

Example 3

How many permutations of $AAAABBB$ are there?

Solution: There are multiple answers here, but a nice solution can come from constructing the set of the permutations on $AAAABBB$ . We can model the question as a row of seven boxes, like this: $\square \square \square \square \square \square \square,$ which we have to populate with $4$ $A$ s and $3$ $B$ s. We break up the problem into first placing the $A$ s, then placing the $B$ s.

Starting with the $A$ s, we must choose the $4$ boxes to place them into; this is

populating them is the same as choosing any $4$ of the boxes, which is given by $_7 C_4 = 35$ , where $_n C_k$ is a combination. An example of a placement of the $A$ s is $\square A A \square A \square A$ . For the $B$ s, their position is actually predetermined by choosing the $A$ s; the only place the three $B$ s can go is in the three empty boxes, so we don't have to account for them after choosing the $A$ s. Thus, there are $35$ different permutations of $AAAABBB$ , as required. $\square$ .

If we were to proceed like before, splitting it based on boxes and their choices, we'd get a much messier (but still viable) solution. Like in this problem, there are often multiple ways to construct a set. Others, however, have no other methods, like in the following question:

Example 4

2001 AMC 12 Problem 16: A spider has one sock and one shoe for each of its eight legs. In how many different orders can the spider put on its socks and shoes, assuming that, on each leg, the sock must be put on before the shoe?

Solution: Note that each leg has one designated shoe and a designated sock; each leg's shoe and sock belongs to only that leg. The question is then only asking about the order in time that it puts all 16 socks and shoes in. We can model the different orders as 16 boxes, where each box is populated with a certain sock or shoe, like this: $\square \square \square \square \square \square \square \square \square \square \square \square \square \square \square \square.$ We can use a similar approach to example three to solve this problem — we break the problem up into where each sock and shoe is located in the list of 16 boxes, then we permute the pair. We can first choose two boxes which a sock-shoe pair is located, then we permute them to see which of the boxes each shoe is located in. For the first leg, the location of its sock and shoe's two boxes are given by $_{16} C_2$ ; but on permuting them, we know that the sock appear first in the list, which means there's just one permutation.

So, there are just $_{16} C_2$ different places in which the first leg's sock and shoe can be located in the 16 boxes. By similar logic, the second leg has $_{14} C_2$ places in the boxes, the third has $_{12} C_2$ , and so on. The final answer is then the product of the leg's choices, which is $\binom{16}{2}\binom{14}{2}\cdots\binom{2}{2} = \left(\frac{16 \cdot 15}{2}\right) \left(\frac{14 \cdot 13}{2}\right) \cdots \left(\frac{2 \cdot 1 }{2}\right) = \frac{16!}{2^8}.$ Thus, our final answer is $\frac{16!}{2^8}$ , or $D$ . $\square$ .

This problem was much more challenging than the others mentioned thus far, but it's a lovely illustration of just how piercing a cleverly chosen construction can be to counting problems.

Example 5

2004 AIME I Problem 6: An integer is called snakelike if its decimal representation $a_1a_2a_3\cdots a_k$ satisfies $a_i<a_{i+1}$ if $i$ is odd and $a_i>a_{i+1}$ if $i$ is even. How many snakelike integers between 1000 and 9999 have four distinct digits?

Solution: We construct the set of snakelike integers. All the recursive requirement is saying is that the second digit must be greater than the first and third, and the fourth must be greater than the third. But before we start construction, we must divide our investigation into several cases, based on whether we allow zeroes

Case 1: Snakelike integers with no zero. First, we choose the four integers. They must be between $1$ and $9$ inclusive, and no digit can be repeated, so the combination that describes this is $_9 C_4 = 126$ . Next, we find out how many permutations of these digits keep the number snakelike. For simplicity, consider the case of $1$ , $3$ , $5$ , and $7$ . The total possibilities are $1537, 1735, 3517, 3715, \textrm{ and } 5713.$ This applies to all snakelike integers with no zero, which means there $5$ arrangements that keep the number snakelike. Thus we have $126 \cdot 5 = 630$ snakelike integers with four distinct digits and no zero.

Case 2: Snakelike integers with one zero. First, we choose the other three integers, which by similar logic above is $_9 C_3 = 84$ . Next, we permute these digits. Without loss of generality, let our other three digits be $1$ , $3$ , and $5$ . The total possibilities are $1305, 1503, \textrm{ and } 3501.$ Hence, there are $84 \cdot 3 = 252$ snakelike integers with four distinct digits and one zero.

It's easy to see that introducing a second zero would mandate them being the first and third digits. However, this breaks our requirement that our integers must be between $1000$ and $9999$ , so there are no four-digit snakelike integers with two or more zeroes. Thus, our total is $630 + 252 = 882$ snakelike integers with four distinct digits, as desired. $\square$ .

It's worth noting that as problem-solving ability becomes more advanced, there are fewer problems that can be solved by constructive counting alone; the list of examples terminates at a late-introductory level consequentially. At the same time, there are many, many more problems at a higher level where constructive counting is a crucial intermediate step, combined with other counting strategies to reach an answer.

More examples

2005 AIME I Problems/Problem 5

@@ Line 7: / Line 7: @@
 ''How many four-digit numbers are there?''
-'''Solution''': We construct the set of four-digit numbers, by finding the number of possibilities each digit can be, then multiplying them all together. For the first digit, it can be any number from one to nine (it cannot be zero, or else it ceases to be four-digit), so it has <math>9</math> options. As for the other three digits, they can be any number from zero to ten, so they all have <math>10</math> options. From the multiplication principle, our answer is thus <math>9 \cdot 10 \cdot 10 \cdot 10 = 9000</math>. <math>\square</math>
+'''Solution''': We break up the problem into the number of choices each digit can be. For the first digit, it can be any number from one to nine (it cannot be zero, or else it ceases have four digits), so it has <math>9</math> options. As for the other three digits, they can be any number from zero to ten, so they all have <math>10</math> options. We then multiply these together to get an answer of <math>9 \cdot 10 \cdot 10 \cdot 10 = 9000</math>. <math>\square</math>
+This may seem like a frivolous and fruitless trick, but the technique of breaking a problem down into several "choices" is truly fundamental and appears everywhere in combinatorics.
 === Example 2 ===
+''How many lists of seven numbers are there such that each entry is between <math>2</math> and <math>9</math> inclusive and no two consecutive entries are equal?''
+'''Solution''': A constructive approach is the simplest way to attack this question. Let each option be a digit out of the seven numbers. The first digit can be any digit from <math>2</math> to <math>9</math>, of which there are <math>8</math>. The second can be any of <math>2</math> to <math>10</math> too, with the sole exception of the previous digit. Regardless of whatever the first digit is, we know that it removes one option, so there's <math>8 - 1 = 7</math> options for the second digit.
+The exact same logic applies to the third digit; it can be any of the <math>8</math> digits except the one before it, so it has <math>7</math> options. This continues until the seventh digit, which means that digits <math>2</math> to <math>7</math> all have <math>7</math> options. Then our answer is <math>8 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 \cdot 7 = 8 \cdot 7^6 = 941,192</math>, as desired. <math>\square</math>
+These two examples use choices specifically based on digits, but this isn't the entire picture of constructive counting. In general, constructive techniques include any breakage of a counting problem into several smaller counting problems. The following example displays this well:
+=== Example 3 ===
 ''How many permutations of <math>AAAABBB</math> are there?''
-'''Solution''': We construct the set of the permutations of <math>AAAABBB</math>. We can imagine this as a row of seven boxes, like <cmath>\square \square \square \square \square \square \square.</cmath> We first "pick" the boxes that <math>B</math> can occupy. This is given by <math>_7 C_3 = 35</math>, where <math>_n C_k</math> is a [[combination]]. Here's one possibility: <cmath>\square B B \square \square B \square.</cmath> From here, we let the four remaining boxes contain the <math>A</math>s, which completes the construction. Thus, there are <math>35</math> different permutations. <math>\square</math>.
+'''Solution''': There are multiple answers here, but a nice solution can come from constructing the set of the permutations on <math>AAAABBB</math>. We can model the question as a row of seven boxes, like this: <cmath>\square \square \square \square \square \square \square,</cmath> which we have to populate with <math>4</math> <math>A</math>s and <math>3</math> <math>B</math>s. We break up the problem into first placing the <math>A</math>s, then placing the <math>B</math>s.
+Starting with the <math>A</math>s, we must choose the <math>4</math> boxes to place them into; this is
+populating them is the same as choosing any <math>4</math> of the boxes, which is given by <math>_7 C_4 = 35</math>, where <math>_n C_k</math> is a [[combination]]. An example of a placement of the <math>A</math>s is <cmath>\square A A \square A \square A</cmath>. For the <math>B</math>s, their position is actually predetermined by choosing the <math>A</math>s; the only place the three <math>B</math>s can go is in the three empty boxes, so we don't have to account for them after choosing the <math>A</math>s. Thus, there are <math>35</math> different permutations of <math>AAAABBB</math>, as required. <math>\square</math>.
+If we were to proceed like before, splitting it based on boxes and their choices, we'd get a much messier (but still viable) solution. Like in this problem, there are often multiple ways to construct a set. Others, however, have no other methods, like in the following question:
-=== Example 3 ===
+=== Example 4 ===
 ''[[2001 AMC 12 Problems/Problem 16 | 2001 AMC 12 Problem 16]]: A spider has one sock and one shoe for each of its eight legs. In how many different orders can the spider put on its socks and shoes, assuming that, on each leg, the sock must be put on before the shoe?
-'''Solution''': We construct the orders the spider can get dressed, We can model the order as 16 boxes, where each box is populated with a certain sock or shoe. First, we choose where each sock-shoe pair is located in the 16 boxes. The first sock-shoe pair is <math>_{16} C_2</math>, the second is <math>_{14} C_2</math>, and so on. Thus, the total orders of sock-shoe pairs <cmath>\binom{16}{2}\binom{14}{2}\cdots\binom{2}{2}= \frac{16!}{2^8}.</cmath> There is only one arrangement of the sock-shoe pair that leaves them in the correct order, so we don't need to permute them further. Thus, our final answer is <math>\frac{16!}{2^8}</math>. <math>\square</math>
+'''Solution''': Note that each leg has one designated shoe and a designated sock; each leg's shoe and sock belongs to only that leg. The question is then only asking about the order in time that it puts all 16 socks and shoes in. We can model the different orders as 16 boxes, where each box is populated with a certain sock or shoe, like this: <cmath>\square \square \square \square \square \square \square \square \square \square \square \square \square \square \square \square.</cmath> We can use a similar approach to example three to solve this problem — we break the problem up into where each sock and shoe is located in the list of 16 boxes, then we permute the pair. We can first choose two boxes which a sock-shoe pair is located, then we permute them to see which of the boxes each shoe is located in. For the first leg, the location of its sock and shoe's two boxes are given by <math>_{16} C_2</math>; but on permuting them, we know that the sock appear first in the list, which means there's just one permutation.
+So, there are just <math>_{16} C_2</math> different places in which the first leg's sock and shoe can be located in the 16 boxes. By similar logic, the second leg has <math>_{14} C_2</math> places in the boxes, the third has <math>_{12} C_2</math>, and so on. The final answer is then the product of the leg's choices, which is <cmath>\binom{16}{2}\binom{14}{2}\cdots\binom{2}{2} = \left(\frac{16 \cdot 15}{2}\right) \left(\frac{14 \cdot 13}{2}\right) \cdots \left(\frac{2 \cdot 1 }{2}\right) = \frac{16!}{2^8}.</cmath> Thus, our final answer is <math>\frac{16!}{2^8}</math>, or <math>D</math>. <math>\square</math>.
-=== Example 4 ===
+This problem was much more challenging than the others mentioned thus far, but it's a lovely illustration of just how piercing a cleverly chosen construction can be to counting problems.
+=== Example 5 ===
 ''[[2004 AIME I Problems/Problem 6 | 2004 AIME I Problem 6]]: An integer is called snakelike if its decimal representation <math> a_1a_2a_3\cdots a_k </math> satisfies <math> a_i<a_{i+1} </math> if <math> i </math> is [[odd integer | odd]] and <math> a_i>a_{i+1} </math> if <math> i </math> is [[even integer | even]]. How many snakelike integers between 1000 and 9999 have four distinct digits?''
-'''Solution''': We construct the set of snakelike integers. All the recursive requirement is saying is that the second digit must be greater than the first and third, and the fourth must be greater than the third. But before we start construction, we must divide our investigation into several cases, based on whether we allow zeroes
+'''Solution''': We construct the set of snakelike integers. All the recursive requirement is saying is that the second digit must be greater than the first and third, and the fourth must be greater than the third. But before we start construction, we must divide our investigation into several [[casework | cases]], based on whether we allow zeroes
-'''Case 1''': Snakelike integers with no zero. First, we choose the four integers. They must be between <math>1</math> and <math>9</math> inclusive, and no digit can be repeated, so the combination that describes this is <math>_9 C_4 = 126</math>. Next, we find out how many permutations of these digits keep the number snakelike. Without loss of generally, let our digits be <math>1</math>, <math>3</math>, <math>5</math>, and <math>7</math>. The total possibilities are <cmath>1537, 1735, 3517, 3715, \textrm{ and } 5713.</cmath> If one would like to be rigorous about it, one could choose one digit to be first, then count how many possible permutations of the other three keep the integer snakelike. Hence, out of our <math>126</math> digits, there are <math>5</math> arrangements of them that keep the number snakelike, and thus we have <math>126 \cdot 5 = 630</math> snakelike integers with four distinct digits and no zero.
+'''Case 1''': Snakelike integers with no zero. First, we choose the four integers. They must be between <math>1</math> and <math>9</math> inclusive, and no digit can be repeated, so the combination that describes this is <math>_9 C_4 = 126</math>. Next, we find out how many permutations of these digits keep the number snakelike. For simplicity, consider the case of <math>1</math>, <math>3</math>, <math>5</math>, and <math>7</math>. The total possibilities are <cmath>1537, 1735, 3517, 3715, \textrm{ and } 5713.</cmath> This applies to all snakelike integers with no zero, which means there <math>5</math> arrangements that keep the number snakelike. Thus we have <math>126 \cdot 5 = 630</math> snakelike integers with four distinct digits and no zero.
 '''Case 2''': Snakelike integers with one zero. First, we choose the other three integers, which by similar logic above is <math>_9 C_3 = 84</math>. Next, we permute these digits. Without loss of generality, let our other three digits be <math>1</math>, <math>3</math>, and <math>5</math>. The total possibilities are <cmath>1305, 1503, \textrm{ and } 3501.</cmath> Hence, there are <math>84 \cdot 3 = 252</math> snakelike integers with four distinct digits and one zero.
 It's easy to see that introducing a second zero would mandate them being the first and third digits. However, this breaks our requirement that our integers must be between <math>1000</math> and <math>9999</math>, so there are no four-digit snakelike integers with two or more zeroes. Thus, our total is <math>630 + 252 = 882</math> snakelike integers with four distinct digits, as desired. <math>\square</math>.
+It's worth noting that as problem-solving ability becomes more advanced, there are fewer problems that can be solved by constructive counting alone; the list of examples terminates at a late-introductory level consequentially. At the same time, there are many, many more problems at a higher level where constructive counting is a crucial intermediate step, combined with other counting strategies to reach an answer.
 === More examples ===

Page

Toolbox

Search