Note on Counting: Exercise 13.26 answer

Similar to the last post, this is a short note detailing some of my thoughts to the answer to Exercise 13.26 in the book Counting, by Prof Koh Khee Meng and Prof Tan Eng Guan. (NOTE: Despite the lone one star review on Amazon for the first edition of the book, this is imho a pretty good book. I’ll do a review of it soon.)

Question:

Find the number of 4-tuples of integers

(i) \( (a, b, c, d) \) satisfying \( 1 <= a < b < c < d <= 30; \)

(ii) \( (p, q, r, s) \) satisfying \( 1 <= p <= q <= r <= s <= 30; \)

The emphasis of this note is on part (ii). However, I shall talk a bit about part (i).

Part (i)

Without knowing the mathematics behind it, this problem will seem to be quite tedious if one tries to “brute force” it or approach it entirely from an entirely “computational” point of view. What I mean is this: we know that \( 1 <= a < b < c < d <= 30 \), so \( 1 <= a <= 27 \). Now if we fix \( a = 1 \), we know that \( 2 <= b <= 28 \). Now if we go on to fix \( b = 2 \), we know that \( 3 <= c <= 29 \). If we carry on to fix \( c = 3 \), we know that \( 4 <= d <= 30 \). Ok so for \( a = 1, b = 2, c = 3 \), there are \( 30 - 4 + 1 = 27 \) possible 4-tuples \( a, b, c, d \). And this is just one branch of a huge tree. We can go on to try out \( a = 1, b = 3, … \) . And we quickly see how “difficult” this problem can become.

Now, enter the beauty of combinatorics. I only know the bare basics of this field (I’ve very briefly browsed through some books covering more advanced topics in combinatorics and man, they’re difficult, very difficult) but I liken combinatorics to counting on a massive scale in an elegant way. Sometimes, we get an integer solution especially for a particular case of a more general problem, other times we get a formula and while it may not be computationally extremely fast to compute, it totally shines compared to a “brute force” method. So how does one think about this problem using combinatorics?

Observe that since \( a < b < c < d \), \ \(a, b, c \) and \( d \) must be unique. Combine this with \( 1 <= a \) and \( d <= 30 \), we quickly see that we’re trying to pick 4 unique integers from \( \left\{ 1, 2, …, 30 \right\} \) and there’s only one way to arrange in ascending order any 4 unique integers from this set. Therefore, there are \( { 30 \choose 4 } \) ways to do this.

Part (ii)

Part (ii) looks similar to Part (i) except that the less than signs have now become less than or equal to signs. Yet that changes the nature of the problem. My initial approach to Part (ii) was incorrect and I’m guessing that it is probably a common mistake made by newbies. I totally forgot what I was thinking about when I was doing it but my logic was probably something along the following lines: Since \( p <= q <= r <= s \) and \( 1 <= p \) and \( s <= 30 \), then there are 30 ways to choose \( p \), 30 ways to choose \( q \), 30 ways to choose \( r \) and 30 ways to choose \( s \). Hence there are \( 30^4 \) such tuples \( (p, q, r, s) \) . The major mistake of approach is that it does not take into account of the fact that \( p <= q <= r <= s \) and in fact implies that \( p, q, r, s \) can be unordered. The fact that this “solution” is the same as that of \( (p, q, r, s) \) where \( 1 <= p, q, r, s <= 30 \) should immediately sound an alarm.

I shall present 2 approaches. The first I thought of it myself after reading the answer in the Solutions Manual and encountering something similar elsewhere, the second is from the Solutions Manual but elaborated in more detail.

Part (ii): Approach 1

Since \( p <= q <= r <= s \), this means that it is possible to choose an integer from the set \( \left\{ 1, 2, …, 30 \right\} \) more than once. Hence 4-tuples like \( (1, 1, 1, 1), (5, 5, 10, 20), (26, 26, 26, 30) \) are tuples satisfying the conditions. Now, it may seem very difficult to solve this problem, but things take a turn once we think about how to reduce this to the problem of distributing identical objects into distinct boxes, where boxes can be empty. Here, the boxes are numbered \( 1, 2, …, 30 \) and we have 4 identical objects to distribute into 30 boxes. Putting one object into a box labelled \( i \) means that the integer \( i \) appears in the 4-tuple once. In general, placing \( k \) objects into a box labelled \( i \) means that the integer \( i \) appears \( k \) times in the 4-tuple. And there is only one way to arrange any 4 integers that are picked. It should not difficult to see that there is a bijection between the set of all \( (p, q, r, s) \) where \( 1 <= p <= q <= r <= s <= 30 \) and the set of all configurations of distributing 4 identical objects into 30 distinct boxes, each of which may be empty. I shall not prove this bijection here. Hence the number of such 4-tuples is \( { 4 + 30 - 1 \choose 4 } = { 33 \choose 4 }\).

Part (ii): Approach 2 (answer in the Solution Manual)

Solution in manual:

Let \( q’ = q + 1, r’ = r + 2 \) and \( s’ = s + 3 \). Then the problem can be restated as: Find the number of 4-tuples of integers \( (p, q’, r’, s’) \) satisfying \( 1 <= p < q’ < r’ < s’ <= 33 \). This is equivalent to choosing 4 integers from \( \left\{ 1, 2, …, 33 \right\} \) and assigning them in increasing magnitude to \( p, q’, r’ \) and \( s’ \). Thus, there are \( { 33 \choose 4 } \) ways.

If we take this solution as correct, it shouldn’t be too hard to see that the number of 4-tuples \( (p, q’, r’, s’) \) satisfying \( 1 <= p < q’ < r’ < s’ <= 33 \) is exactly \( { 33 \choose 4 } \), especially after we’ve solved Part (i) of the question.

The next question that’ll probably come to mind is: is this given solution actually correct? The only way to find out is to prove it. We shall do it by establishing a bijection \( f : A \mapsto B \) where

$$A = \left{ (p, q, r, s) \right} \text{ where } 1 <= p <= q <= r <= s <= 30 \ B = \left{ (p, q’, r’, s’) \right} \text{ where } 1 <= p < q’ < r’ < s’ <= 33 \ \text{ and } q’ = q + 1, r’ = r + 2, s’ = s + 3 $$

First, we want to prove that the mapping \( f \) is injective.

We will prove this using the tedious way, by showing that 2 tuples \( (a, b, c, d) \) and \( (e, f, g, h) \), both from the set \( A \), but differing in value in only one position, will result in different 4-tuples in the set \( B \) via the mapping \( f \). We shall do that for each position in the 4-tuple.

First position: Consider \( (a, b, c, d) \in A \) and \( (a’, b, c, d)\in A \) where \( a \neq a’ \). Then \( f((a, b, c, d)) = (a, b + 1, c + 2, d + 3) \) and \( f((a’, b, c, d)) = (a’, b + 1, c + 2, d + 3) \) which differ in the first position.

Second position: Consider \( (a, b, c, d) \in A \) and \( (a, b’, c, d) \in A \) where \( b \neq b’ \). Then \( f((a, b, c, d)) = (a, b + 1, c + 2, d + 3) \) and \( f((a, b’, c, d)) = (a, b’ + 1, c + 2, d + 3) \) which differ in the second position.

Third position: Consider \( (a, b, c, d) \in A \) and \( (a, b, c’, d) \in A \) where \( c \neq c’ \). Then \( f((a, b, c, d)) = (a, b + 1, c + 2, d + 3) \) and \( f((a, b, c’, d)) = (a, b + 1, c’ + 2, d + 3) \) which differ in the third position.

Fourth position: Consider \( (a, b, c, d) \in A \) and \( (a, b, c, d’) \in A \) where \( d \neq d’ \). Then \( f((a, b, c, d)) = (a, b + 1, c + 2, d + 3) \) and \( f((a, b, c, d’)) = (a, b + 1, c + 2, d’ + 3) \) which differ in the fourth position.

Notice that for any 2 distinct 4-tuples \( (a, b, c, d) \) and \( (e, f, g, h) \), as long as some position differs, that position will still differ in \( f((a, b, c, d)) \) and \( f((e, f, g, h)) \). Hence \( f((a, b, c, d)) \neq f((e, f, g, h)) \) as long as \( (a, b, c, d) \neq (e, f, g, h) \) and the mapping \( f \) is injective.

Now we want to prove that the mapping \( f \) is surjective.

Consider \( (p, q’, r’, s’) \in B \). We know that \( p < q’ < r’ < s’ \). Consider \( (p, q’ - 1, r’ - 2, s’ - 3) \), the 4-tuple that will result by applying the inverse operation of \( f \). We want to show that \( (p, q’ - 1, r’ - 2, s’ - 3) \in A \).

For \( p \): We know that \( 1 <= p <= 30 \).

For \( q \): We know that \( p < q’ <= 31 \), hence \( p <= q’ - 1 \). Combine this with \( 1 <= p \) and \( q’ - 1 <= 30 \) and we have \( 1 <= q’ - 1 <= 30 \).

For \( r \): We know that \( q’ < r’ <= 32 \), hence \( q’ <= r’ - 1 \) and \( q’ - 1 <= r’ - 2 \). Combine this with \( 1 <= q’ - 1 \) and \( r’ - 2 <= 30 \) and we have \( 1 <= r’ - 2 <= 30 \).

For \( s \): We know that \( r’ < s’ <= 33 \), hence \( r’ <= s’ - 1 \) and \( r’ - 2 <= s’ - 3 \). Combine this with \( 1 <= r’ - 2 \) and \( s’ - 3 <= 30 \) and we have \( 1 <= s’ - 3 <= 30 \).

Therefore, \( 1 <= p, q’ - 1, r’ - 2, s’ - 3 <= 30 \) and \( (p, q’ - 1, r’ - 2, s’ - 3) \in A \) and the mapping \( f \) is surjective.

Since \( f \) is injective and surjective, \( f \) is bijective. Hence \( \left\vert{A}\right\vert = \left\vert{B}\right\vert \) and we know that \( \left\vert{B}\right\vert = { 33 \choose 4 } \), so \( \left\vert{A}\right\vert = {33 \choose 4} \).

Alright, we know for sure that the solution is correct, but, how does one come up with the insight that is the mapping \( f \)? To me, that is still a mystery. It’s kind of like seeing Strassen Algorithm and wondering how Strassen came up with it; it does take a very smart and creative person to come up with such insights.

Perhaps the authors intended for Part (i) of the question to be a hint, since we do know how to compute the size of the set \( \left\{(p, q, r, s)\right\} \) where \( 1 <= p < q < r < s <= 30 \). Then perhaps the reader will think about reducing Part (ii) to something solvable by the same concept in Part (i)? Haha, only the authors will know.