Definition 1: For integers \(a\) and \(b\), we say that \(a\) divides \(b\) if there is an integer \(c\) with the property that \(ac=b\). In this case, we write \(a\mid b\).
The phrases "\(a\) is a divisor of \(b\)" and "\(b\) is a multiple of \(a\)" both have the exact same meaning as "\(a\) divides \(b\)". Notice that, by this definition, every integer is a divisor of \(0\), but the only divisor of \(0\) is \(0\) itself. We give a few facts that will be used in this solution. Their proofs are not included.
Fact 1: If \(a\) and \(b\) are positive integers such that \(a\mid b\), then \(a\leq b\).
Fact 2: If \(a\), \(b\), and \(c\) are integers such that \(a\mid b\) and \(a\mid c\), then \(a\mid (b-c)\) and \(a\mid (b+c)\).
Fact 3: If \(a\), \(b\), and \(c\) are integers such that \(a\mid b\) and \(b\mid c\), then \(a\mid c\).
Suppose \((a,b)\) is a splendid sequence. By definition, this means \(a\mid b\) and \(b\mid a\). Since the integers in a splendid sequence must be positive, Fact 1 implies that \(a\leq b\) and \(b\leq a\), which implies \(a=b\). If \(p\) is a prime number such that \(p\mid a\), then \(p\mid b\) by Fact 3. However, no prime number can divide both \(a\) and \(b\) because \((a,b)\) is splendid. Therefore, no prime number divides \(a\). Similarly, no prime number divides \(b\), and so \(a=b=1\).
Therefore, the only splendid sequence of length \(2\) is \((1,1)\).
There are several "generic" sequences that one might find. The simplest is probably the sequence \((1,1,1,\dots, 1)\). That is, the sequence \((a_1,a_2,a_3,\dots,a_n)\) with \(a_i=1\) for all \(i\) is always a splendid sequence. This is because no prime number divides \(1\), and \(1\) divides every integer. Another splendid sequence is \((1,2,3,4,\dots,n-1,1)\). For each integer \(k\) in this sequence, other than the \(1\)’s on the end and \(n-1\), the integers next to it are \(k-1\) and \(k+1\), so their sum is \((k-1)+(k+1)=2k\), which is a multiple of \(k\). The integers next to \(n-1\) are \(n-2\) and \(1\), which have a sum of \(n-1\).
In the remaining parts of the solution as well as in the Appendix, we will often denote a sequence by a bold letter. For example, we might refer to the sequence \((a_1,a_2,\dots,a_n)\) by \(\textbf{x}\).
Assume that \(\textbf{x}=(a_1,a_2,\dots,a_n)\) is a splendid sequence. We will show that \[\textbf{y}=(a_1,a_2,\dots,a_i,c,a_{i+1},\dots,a_n)\] is a splendid sequence when \(c=a_i+a_{i+1}\).
If some prime number \(p\) divides every integer in \(\textbf{y}\), then it also divides every integer in \(\textbf{x}\). Since \(\textbf{x}\) is a splendid sequence, there is no such prime number, so no prime number divides all of the integers in \(\textbf{y}\).
If \(i=1\), then \(\textbf{y} = (a_1,c,a_2,a_3,\dots,a_n)\) and \(c=a_1+a_2\). Since \(\textbf{x}\) is a splendid sequence, \(a_1\mid a_2\). We also have that \(a_1\mid a_1\), so \(a_1 \mid (a_1+a_2)\) or \(a_1\mid c\) by Fact 2. Since every integer divides itself, \(c\mid (a_1+a_2)\). To see that \(a_2\mid(c+a_3)\), we note that \(a_2\mid(a_1+a_3)\) because \(\textbf{x}\) is splendid and \(a_2\mid a_2\) because every integer divides itself. By Fact 2, \(a_2\mid(a_1+a_2+a_3)\) so \(a_2\mid(c+a_3)\). The integers \(a_3\) through \(a_n\) all have exactly the same neighbours in \(\textbf{y}\) as they do in \(\textbf{x}\), which is a splendid sequence, so \(\textbf{y}\) satisfies all other divisibility conditions required for it to be a splendid sequence.
If \(i=n-1\), then \(\textbf{y}\) is splendid by a similar argument to the one in the previous paragraph.
If \(1<i<n-1\), then \(\textbf{y} = (a_1,a_2,\dots,a_{i-1},a_i,c,a_{i+1},a_{i+2},\dots,a_n)\). When \(k<i\) and when \(k>i+1\), \(a_k\) divides the sum of its neighbours because it has the exact same neighbours as it did in \(\textbf{x}\). In \(\textbf{y}\), the neighbours of the integer \(a_i\) are \(a_{i-1}\) and \(c\). Since \(\textbf{x}\) is a splendid sequence, \(a_i\mid(a_{i-1}+a_{i+1})\). We also have that \(a_i\mid a_i\), and so by Fact 2, \(a_i\mid(a_i+a_{i-1}+a_{i+1})\) which means \(a_i\mid(a_{i-1}+c)\). By similar reasoning, \(a_{i+1}\mid(c+a_{i+2})\). The integer \(c\) is equal to the sum of its neighbours in \(\textbf{y}\) by definition, so it also divides the sum of its neighbours. Therefore, every integer in \(\textbf{y}\) divides the sum of its neighbours. We already argued that no prime number divides every integer in \(\textbf{y}\), so \(\textbf{y}\) is a splendid sequence.
Suppose \(\textbf{x} = (a_1,a_2,a_3,\dots,a_n)\) is a splendid sequence. If \(n=2\), then the solution to part (a) implies that \(a_1=a_n=1\).
Suppose \(n\geq 3\). By definition, we have that \(a_n\mid a_{n-1}\) and that \(a_{n-1}\mid(a_{n-2}+a_n)\). By Fact 3, \(a_n\mid(a_{n-2}+a_n)\). Since \(a_n\mid a_n\), we can apply Fact 2 to get that \(a_n\mid(a_{n-2}+a_n-a_n)\) which implies that \(a_n\mid a_{n-2}\).
Since \(\textbf{x}\) is splendid, we also have that \(a_{n-2}\mid (a_{n-3}+a_{n-1})\). We have just shown that \(a_n\) divides \(a_{n-2}\), so by Fact 3, \(a_n\mid (a_{n-3}+a_{n-1})\). We also have that \(a_n\mid a_{n-1}\), so Fact 2 implies \(a_n\mid(a_{n-3}+a_{n-1}-a_{n-1})\) or \(a_n\mid a_{n-3}\). Continuing in this way, we can show that \(a_n\mid a_i\) for all \(i\) with \(1\leq i\leq n\). By the condition that no prime number can divide every integer in \(\textbf{x}\), we conclude that \(a_n=1\). Essentially the same argument shows that \(a_1=1\).
Most of the work is to prove these two claims.
Claim 1: If \((a_1,a_2,\dots,a_n)\) is a splendid sequence of length \(n\geq 3\) that contains at least one integer that is greater than \(1\), then there is some \(i\) with \(1 < n\) such that \(a_i=a_{i-1}+a_{i+1}\) and \((a_1,a_2,\dots,a_{i-1},a_{i+1},a_{i+2},\dots,a_n)\) is a splendid sequence. That is, there is an integer in the sequence that is equal to the sum of its neighbours, and if it is removed, the remaining shorter sequence is a splendid sequence.
Claim 2: If \((a_1,a_2,\dots,a_n)\) is a splendid sequence of length \(n\geq 2\), then \(a_i \leq 2^{n-2}\) for every \(i\).
Proof of Claim 1. To prove Claim 1, suppose \(\textbf{x} = (a_1,a_2,\dots,a_n)\) is a splendid sequence with at least one integer greater than \(1\) and let \(i\) be such that \(a_i\) is the largest integer in the sequence, choosing the rightmost occurrence if there is a "tie". More precisely, \(i\) is the largest integer with the property that \(a_i\geq a_j\) for all \(1\leq j \leq n\).
By part (d), \(a_n=a_1=1\), and since there is at least one integer in \(\textbf{x}\) that is greater than \(1\), neither \(a_1\) nor \(a_n\) can be the largest integer in \(\textbf{x}\), which means \(1<i<n\). The choice of \(i\) ensures that \(a_{i-1} \leq a_i\) and \(a_{i+1} \leq a_i\). If \(a_i=a_{i+1}\), then since \(a_i\) is the largest integer in the sequence, this would imply that \(a_i\) is not the rightmost occurrence of the largest integer in the sequence. Therefore, we actually have that \(a_{i+1} < a_i\).
The inequalities \(a_{i-1} \leq a_i\) and \(a_{i+1} < a_i\) imply that \(a_{i-1} + a_{i+1} < 2a_i\) and since \(\textbf{x}\) is splendid, \(a_i\mid (a_{i-1}+a_{i+1})\). As well, all integers in a splendid sequence are positive, which means that \(a_{i-1}+a_{i+1}\) is a positive multiple of \(a_i\) that is less than \(2a_i\). The only such multiple is \(a_i\) itself, and so \(a_{i-1}+a_{i+1}=a_i\).
We have shown that one of the integers in \(\textbf{x}\) is equal to the sum of its neighbours. To finish proving the claim, we need to show that \(\textbf{y} = (a_1,a_2,\dots,a_{i-1},a_{i+1},a_{i+2},\dots,a_n)\) is a splendid sequence. In \(\textbf{y}\), only \(a_{i-1}\) and \(a_{i+1}\) have different neighbours than they did in \(\textbf{x}\), so the divisibility conditions we need to verify are that \(a_{i-1} \mid (a_{i-2}+a_{i+1})\) and \(a_{i+1} \mid (a_{i-1}+a_{i+2})\)
We know that \(a_{i-1}\mid(a_{i-2}+a_i)\) and we have just shown that \(a_i=a_{i-1}+a_{i+1}\). Substituting, we get that \(a_{i-1}\mid (a_{i-2}+a_{i-1}+a_{i+1})\). By Fact 2, \(a_{i-1}\mid(a_{i-2}+a_{i-1}+a_{i+1}-a_{i-1})\) or \(a_{i-1}\mid(a_{i-2}+a_{i+1})\). A nearly identical argument shows that \(a_{i+1}\mid(a_{i-1}+a_{i+2})\). Therefore, \(\textbf{y}\) satisfies the divisibility conditions.
If a prime number \(p\) divides every integer in \(\textbf{y}\), then \(p\mid a_{i-1}\) and \(p\mid a_{i+1}\), so \(p\mid a_i\) by Fact 2 since \(a_i=a_{i-1}+a_{i+1}\). This would mean \(p\) divides every integer in \(\textbf{x}\), which is not the case since \(\textbf{x}\) is splendid. ◻
We will now prove Claim 2 by mathematical induction. The essence of the proof is that, by Claim 1, the largest integer in a splendid sequence must be the sum of two integers in a shorter splendid sequence. Therefore, the maximum size of an integer in a splendid sequence of length \(n+1\) is at most twice the maximum size of an integer in a splendid sequence of length \(n\). This means that there is always a fixed upper bound on the size of integers in a splendid sequence of a fixed length.
Proof of Claim 2. To get an idea of how the induction will work, we first prove this for \(n=2\), \(n=3\), and \(n=4\). For \(n=2\), we showed in the solution to part (a) that the only splendid sequence of length \(2\) is \((1,1)\). The largest element in this sequence is \(1=2^{0}=2^{2-2}=2^{n-2}\), so the claim holds for \(n=2\).
Now suppose \((a_1,a_2,a_3)\) is a splendid sequence of length \(3\). If \(a_1=a_2=a_3=1\), then every integer in the sequence is less than \(2^{3-2}=2\). Otherwise, since \(a_1=a_3=1\) by part (d), Claim 1 implies that \(a_2=a_1+a_3=1+1=2\) is the largest integer in the sequence, so all integers in the sequence are at most \(2 = 2^{3-2}\).
Continuing to \(n=4\), suppose \((a_1,a_2,a_3,a_4)\) is a splendid sequence. Again, if the sequence consists entirely of \(1\)’s, then \(a_i\leq 2^{4-2}=4\) for all \(i\). Otherwise, either \((a_1,a_3,a_4)\) is a splendid sequence of length \(3\) and \(a_2=a_1+a_3\), or \((a_1,a_2,a_4)\) is a splendid sequence of length \(3\) and \(a_3=a_2+a_4\). Either way, three of the four integers are in a splendid sequence of length \(3\), and the fourth is the sum of two integers in a splendid sequence of length \(3\). We just showed that an integer in a splendid sequence of length \(3\) is at most \(2^{3-2}\), so an integer in a splendid sequence of length \(4\) is at most \(2^{3-2}+2^{3-2}=2\times2^{3-2}=2^{4-2}\). Therefore, no integer in the sequence \((a_1,a_2,a_3,a_4)\) can exceed \(2^{4-2}\).
Now for the inductive step. Suppose, for some \(n\geq 2\), that every integer in every splendid sequence of length \(n\) is at most \(2^{n-2}\). This is our inductive hypothesis. Consider a splendid sequence \((a_1,a_2,\dots,a_n,a_{n+1})\) of length \(n+1\). If \(a_i=1\) for all \(i\), then \(a_i\leq 2^{n-2}\) for all \(i\). Otherwise, Claim 1 implies that there is some \(i\) so that \(a_i=a_{i-1}+a_{i+1}\) and \((a_1,a_2,\dots,a_{i-1},a_{i+1},\dots,a_n, a_{n+1})\) is a splendid sequence of length \(n\). By the inductive hypothesis, this means each of \(a_1\), \(a_2\), \(a_3\), , \(a_{i-1}\), \(a_{i+1}\), , \(a_n\), and \(a_{n+1}\) is at most \(2^{n-2}\), and since \(2^{n-2}<2^{(n+1)-2}\), each of these integers is at most \(2^{(n+1)-2}\). For \(a_i\), we have \(a_i=a_{i-1}+a_{i+1}\) and since \(a_{i-1}\leq 2^{n-2}\) and \(a_{i+1}\leq 2^{n-2}\), we conclude that \(a_i\leq 2^{n-2}+2^{n-2}=2(2^{n-2})=2^{(n+1)-2}\) as well. We have shown that every integer in a splendid sequence of length \(n+1\) is at most \(2^{(n+1)-1}\). This completes the induction and the proof. ◻
By Claim 2, every integer in a splendid sequence of length \(n\) is at most \(2^{n-2}\). There are only finitely many sequences of length \(n\) consisting of positive integers less than or equal to \(2^{n-2}\), regardless of whether they are splendid. Therefore, for fixed \(n\), there are only finitely many splendid sequences of length \(n\).
The proof of part (f) will use some language about sets. Specifically, we will use the language of injective, surjective, and bijective functions. If you have seen this before, you should be ready to read the solution to part (f). Otherwise, we recommend reading Appendix 1 first.
As pointed out in the hint, the number of splendid sequences of length \(n\) is equal to the \((n-1)\)st Catalan number. The \(n\)th Catalan number is equal to \(\dfrac{1}{n+1}\dbinom{2n}{n}\), so the number of splendid sequences of length \(n\) is \(\dfrac{1}{n}\dbinom{2n-2}{n-1}\). The sequence of Catalan numbers shows up in many contexts. A useful example for this solution is given in Definition 2.
Definition 2: For each positive integer \(n\geq 1\), we call a sequence \((b_1,b_2,\dots,b_n)\) of positive integers a tame sequence if \(b_1=1\) and \(b_{k+1}\leq b_k+1\) for every integer \(k\) with \(1\leq k < n\). In other words, \(b_1=1\) and every other integer in the sequence is at most \(1\) more than the previous integer.
The name tame sequence was made up for the purpose of this solution, but it is known that the number of tame sequences of length \(n\) is equal to the \(n\)th Catalan number. There are proofs of this in various places in the literature. For completeness, we have included a proof in Appendix 2. It is stated as Claim 5.
Let \(T_n\) denote the set of tame sequences of length \(n\) and \(S_n\) denote the set of splendid sequences of length \(n\). We will show, for \(n\geq 2\), that there is a bijection with domain \(T_{n-1}\) and codomain \(S_n\). By the discussion in Appendix 1, this will show that the number of splendid sequences of length \(n\) is the \((n-1)\)st Catalan number.
Recall from part (c) that if \((a_1,a_2,\dots,a_n)\) is a splendid sequence of length \(n\), then \[(a_1,a_2,a_3,\dots,a_i,a_i+a_{i+1},a_{i+1},\dots,a_n)\] is a splendid sequence of length \(n+1\).
From this point on, it will be notationally useful to prepend a zero at the beginning of splendid sequences. For example, the sequence \((0,1)\) will now be the unique splendid sequence of length \(1\). The sequence \((0,1,2,5,3,1)\) is a splendid sequence of length \(5\). This means that a splendid sequence of length \(n\) now has \(n+1\) integers, the first of which is \(0\). For instance, \(a_1=0\), \(a_2=1\), \(a_3=2\), \(a_4=5\), \(a_5=3\), and \(a_6=1\) is how we would index the sequence \((0,1,2,5,3,1)\) going forward. Notice that the observation from part (c) mentioned above also works if we insert the sum between the first and second integers, \(0\) and \(1\). You should convince yourself of this before moving on.
For each \(n\geq 2\), we define a function, \(f_n\), with domain \(T_{n-1}\) and codomain \(S_n\). The way \(f_n\) works is to use a tame sequence as a list of instructions to build a splendid sequence. Consider a tame sequence \(\textbf{x} = (b_1,b_2,\dots,b_{n-1})\) of length \(n-1\). Starting with \((0,1)\), the unique splendid sequence of length \(1\), we read \(\textbf{x}\) from left to right and each integer in the tame sequence tells us where to insert a sum to get a longer splendid sequence. Specifically, in the \(k\)th step, the integer \(b_k\) tells us that we should insert a sum between \(a_{b_k}\) and \(a_{b_{k+1}}\) to get a longer splendid sequence.
For example, suppose \(n=6\) and the tame sequence is \(\textbf{x} = (1,2,3,2,1,1)\). Start with \((0,1)\), which has \(a_1=0\) and \(a_1=1\). The first integer in \(\textbf{x}\) is \(1\), so in the first step we insert the sum between \(a_1\) and \(a_2\). This means we go from \((0,1)\) to \((0,0+1,1)=(0,1,1)\). To start the second step, we reindex to \(a_1=0\), \(a_2=1\), and \(a_3=1\). The next integer in \(\textbf{x}\) is \(2\), so we insert the sum between \(a_2\) and \(a_3\) to get \((0,1,1+1,1)=(0,1,2,1)\). The next integer in \(\textbf{x}\) is \(3\), so we insert the sum between the third and fourth integers in the current splendid sequence to get \((0,1,2,2+1,1)=(0,1,2,3,1)\). Continuing, we get \((0,1,1+2,2,3,1)=(0,1,3,2,3,1)\), followed by \((0,0+1,1,3,2,3,1)=(0,1,1,3,2,3,1)\), and finally \((0,0+1,1,1,3,2,3,1)=(0,1,1,1,3,2,3,1)\). Thus, \(f_7(\textbf{x})=(0,1,1,1,3,2,3,1)\).
By part (c), if \(\textbf{x}\) is a tame sequence of length \(n-1\), then \(f_n(\textbf{x})\) is a splendid sequence of length \(n\). Also note that at the start of the \(k\)th step, the splendid sequence has \(k+1\) integers in it. Because of the way tame sequences are defined, the \(k\)th integer in a tame sequence is at most \(k\), so at each step, the splendid sequence is always long enough for the instruction to makes sense.
For each \(n\geq 2\), we will show that the function \(f_n\) is a bijection. The proof will be by induction, but we first need a definition and then a useful fact.
Definition 3: For a splendid sequence \((a_1,a_2,a_3,\dots,a_{n+1})\) of length \(n\) (remember that \(a_1=0\)), we say that \(a_i\) is a peak if \(a_i=a_{i-1}+a_{i+1}\).
By Claim 1 (see the solution to part (e)), every splendid sequence with an integer greater than \(1\) has at least one peak. Moreover, if that peak is "removed", the resulting shorter sequence is splendid. As well, with our new notation, if there is no integer greater than \(1\), then the sequence is of the form \((0,1,1,1,\dots,1)\) and the first (leftmost) \(1\) is its only peak. If it is removed, the resulting shorter sequence is also splendid. Indeed, the reason for introducing the \(0\) at the beginning was to avoid having to treat the sequence of all \(1\)’s separately in this part of the argument.
Now for the useful fact:
Claim 3: Suppose \(\textbf{y} = (a_1,a_2,\dots,a_{n+1})\) is a splendid sequence of length \(n\) and that \(\textbf{x} = (b_1,b_2,\dots,b_{n-1})\) is a tame sequence of length \(n-1\) such that \(f_n(\textbf{x})=\textbf{y}\). If we let \(b_{n-1}=m\), then \(a_{m+1}\) is the leftmost peak of \(\textbf{y}\).
A proof of Claim 3 is given at the end. We will now prove by induction that \(f_n\) is a bijection for all \(n\geq 2\).
It was observed in part (a) that the only splendid sequence of length \(2\) is \(\textbf{y} = (0,1,1)\). As well, the only tame sequence of length \(2-1=1\) is \(\textbf{x} = (1)\). It is easily checked that \(f_2(\textbf{x})=\textbf{y}\). The sets \(T_1\) and \(S_2\) each have only one element. There is only one function between two sets with one element, and it is always a bijection (convincing yourself of this is a good exercise in understanding definitions). Therefore, \(f_2\) is a bijection.
For the inductive hypothesis, we assume for some \(n \geq 2\) that \(f_n\) is a bijection.
We will show that \(f_{n+1}\) is a bijection, which means we need to show that it is injective and surjective. To show that it is surjective, we assume that \(\textbf{y} = (a_1,a_2,\dots,a_n,a_{n+1},a_{n+2})\) is in \(S_{n+1}\) and let \(a_k\) be its leftmost peak. By Claim 1 from the solution to part (e), the sequence \(\textbf{z} = (a_1,a_2,\dots,a_{k-1},a_{k+1},\dots,a_n,a_{n+1},a_{n+2})\) is in \(S_n\). Since \(f_n\) is a bijection by the inductive hypothesis, it is surjective, so there is some tame sequence \(\textbf{w} = (b_1,b_2,\dots,b_{n-1})\) in \(T_{n-1}\) with \(f_{n-1}(\textbf{w})=\textbf{z}\). For convenience, let \(m=b_{n-1}\).
Recall that the leftmost peak of \(\textbf{x}\) is \(a_k\). Note that \(k\neq 1\) since \(a_1=0\) can never be a peak. Therefore, \(k\geq 2\) and so \(k-1\geq 1\).
Suppose \(a_r\) is the leftmost peak of \(\textbf{z}\). If \(r\leq k-2\), then \(a_r\) is a peak of \(\textbf{y}\) because \(a_r\) has the same neighbours in \(\textbf{y}\) and \(\textbf{z}\) when \(r\leq k-2\). However, \(a_k\) was chosen to be the leftmost peak of \(\textbf{y}\), so we cannot have \(r\leq k-2\). This means \(r\geq k-1\), but by Claim 3, \(r=m+1\), so we get \(k-1\leq m+1\). Combining with \(1\leq k-1\), we have that \(1\leq k-1 \leq m+1=b_{n-1}+1\), which means the sequence \((b _1,b_2,\dots,b_{n-1},k-1)\) is a tame sequence. We will call this tame sequence \(\textbf{x}\).
To recap, the tame sequence \(\textbf{x}\) is obtained by appending \(k-1\) to \(\textbf{w}\), the splendid sequence \(\textbf{y}\) is obtained by inserting the sum between the \((k-1)\)st and \(k\)th integer in \(\textbf{z}\), and \(f_n(\textbf{w})=\textbf{z}\). It follows that \(f_{n+1}(\textbf{x})=\textbf{y}\). We have found \(\textbf{x}\in T_n\) such that \(f_{n+1}(\textbf{x})=\textbf{y}\). Since \(\textbf{y}\) was an arbitrary element of \(S_{n+1}\), this concludes the proof that \(f_{n+1}\) is surjective.
We will now show that \(f_{n+1}\) is injective. To do this, we suppose \(\textbf{x}=(b_1,b_2,\dots,b_n)\) and \(\textbf{w} = (c_1,c_2,\dots,c_n)\) are in \(T_n\) with \(f_{n+1}(\textbf{x}) = f_{n+1}(\textbf{w})\). We will show that \(\textbf{x} = \textbf{w}\).
Let \(\textbf{y}=(a_1,a_2,\dots,a_{n+1},a_{n+2})\) be such that \(\textbf{y}=f_{n+1}(\textbf{x})=f_{n+1}(\textbf{w})\). Suppose \(a_k\) is the leftmost peak of \(\textbf{y}\). By Claim 3, both \(c_n=k-1\) and \(b_n=k-1\). This shows that \(c_n=b_n\). As well, if we set \(\textbf{u} =(b_1,b_2,\dots,b_{n-1})\) and \(\textbf{v} = (c_1,c_2,\dots,c_{n-1})\) and \(\textbf{z} = (a_1,a_2,\dots,a_{k-1},a_{k+1},\dots,a_{n+1},a_{n+2})\), then \(f_n(\textbf{u})=f_n(\textbf{v})=\textbf{z}\). By the inductive hypothesis, \(f_n\) is bijective, and hence, it is injective, so \(\textbf{u}=\textbf{v}\). This shows that \(\textbf{x}\) and \(\textbf{w}\) have the same first \(n-1\) integers, and since \(b_n=c_n\) as well, we have that \(\textbf{x}=\textbf{w}\), which concludes the proof that \(f_{n+1}\) is injective.
We have now shown that \(f_{n+1}\) is bijective, which proves that \(T_{n-1}\) and \(S_n\) have the same number of elements when \(n\geq 2\). Therefore, the number of splendid sequences of length \(n\) is \[\dfrac{1}{n}\dbinom{2n-2}{n-1}\] as claimed earlier.
Proof of Claim 3. The proof is by induction on \(n\). It was noted earlier that the only tame sequence of length \(2-1=1\) is \(\textbf{x} = (1)\) (\(b_1=1\)), the only splendid sequence of length \(2\) is \(\textbf{y} = (0,1,1)\) (\(a_1=0\), \(a_2=1\), \(a_3=1\)), and that \(f_2(\textbf{x})=\textbf{y}\). The leftmost peak of \(\textbf{y}\) is \(a_2\) and \(2=b_1+1\). This shows that Claim 3 is true when \(n=2\).
For the inductive hypothesis, we suppose, for some \(n\geq 2\), that if \(\textbf{y} = (a_1,a_2,\dots,a_n,a_{n+1})\) is a splendid sequence of length \(n\) and \(\textbf{x}=(b_1,b_2,\dots,b_{n-1})\) is a tame sequence of length \(n-1\) such that \(f_n(\textbf{x})=\textbf{y}\), then the leftmost peak of the \(\textbf{y}\) is \(a_{m+1}\) where \(m=b_{n-1}\).
Suppose \(\textbf{y} = (a_1,a_2,\dots,a_n,a_{n+1},a_{n+2})\) is a splendid sequence of length \(n+1\) and that \(\textbf{x}=(b_1,b_2,\dots,b_n)\) is a tame sequence of length \(n\) with \(f_{n+1}(\textbf{x})=\textbf{y}\). Because of how \(f_{n+1}\) is applied, \(a_{m+1}\) is a peak of \(\textbf{y}\). As well, \(\textbf{z} = (a_1,a_2,\dots,a_m,a_{m+2},\dots,a_{n+1},a_{n+2})\) is a splendid sequence of length \(n\) such that \(f_n(\textbf{w})=\textbf{z}\) where \(\textbf{w} = (b_1,b_2,\dots,b_{n-1})\). For convenience, set \(b_n=m\) and \(b_{n-1}=k\). Suppose the leftmost peak of \(\textbf{y}\) is \(a_r\) for some \(r\). For now, assume \(r<m+1\). It is not difficult to show that it is impossible for a splendid sequence to have two consecutive peaks. This means we must have \(r\leq m-1\) since \(r\) must be at least two less than \(m+1\). If this happens, \(a_r\) is also a peak of \(\textbf{z}\) because \(a_{m-1}\) has exactly the same neighbours in \(\textbf{z}\) and \(\textbf{y}\). By the inductive hypothesis, \(a_{k+1}\) is the leftmost peak of \(\textbf{z}\), so \(r=k+1\) and we get \(k+1 \leq m-1\). Since \(\textbf{z}\) is a tame sequence, \(b_n\leq b_{n-1}+1\) or \(m\leq k+1\). This implies that \(m\leq k+1\leq m-1\) so \(m\leq m-1\), which is impossible. Therefore, we cannot have \(r<m+1\), which means \(a_{m+1}\) is indeed the leftmost peak of \(\textbf{y}\). This completes the induction and the proof. ◻
Suppose \(X\) and \(Y\) are finite sets, where by "set" we mean an unordered collection of objects. Suppose there is a "rule" that, for every element in the set \(X\), produces an element in the set \(Y\). For instance, if the sets were \(X=\{(1,2), (5,3), (1,-2)\}\) and \(Y=\{(4,1), (5,2), (9,5)\}\) (both sets of three ordered pairs), the "rule" might be "square the second entry, then reverse the order". With this rule, \((1,2)\) becomes \((4,1)\), \((5,3)\) becomes \((9,5)\), and \((1,-2)\) becomes \((4,1)\), so every element of \(X\) is transformed into an element of \(Y\). Such a rule is called a function. The set \(X\) is called its "domain" and \(Y\) is called its "codomain". If the function is named \(f\), we would use \(f(x)\) to denote the function applied to an element \(x\) in the domain. You have probably seen functions before where the domain and codomain are all or part of the set of real numbers, but the notion of a function applies in a much broader context. Below are three important properties that functions may (or may not) have.
Injectivity: A function \(f\) with domain \(X\) and codomain \(Y\) is called injective if for every two elements of the domain, \(x_1\) and \(x_2\), if \(x_1\neq x_2\), then \(f(x_1)\neq f(x_2)\). In other words, a function is injective if its application to two different elements of the domain always gives two different results. Note that when trying to prove that a function is injective, we typically assume that \(f(x_1)=f(x_2)\) and deduce that \(x_1=x_2\). You might want to think about this logic.
Surjectivity: A function \(f\) with domain \(X\) and codomain \(Y\) is called surjective if for every \(y\in Y\) there exists an \(x\in X\) so that \(f(x)=y\). In other words, a function is surjective if every element of the codomain is the result of applying \(f\) to some element in the domain. [We might also say that the range equals the codomain to describe surjectivity.]
Bijectivity: A function \(f\) is with domain \(X\) and codomain \(Y\) is called bijective or is a bijection if it is both injective and surjective.
There is a lot to be said about injective, surjective, and bijective functions, but for us, the useful observation will be that if \(X\) and \(Y\) are finite sets and there is a bijective function \(f\) with domain \(X\) and codomain \(Y\), then \(X\) and \(Y\) have the same number of elements. Indeed, if \(X\) has \(m\) elements and \(Y\) has \(n\) elements, then being injective implies that \(m\leq n\) and being surjective implies that \(m\geq n\). Thus, being bijective implies that \(m\leq n\leq m\), so \(m=n\).
Observe that the example given at the beginning of this appendix is neither injective nor surjective, so it is not bijective. However, \(X\) and \(Y\) do have the same number of elements. It is important to keep in mind that we are only claiming that if there is a bijection from \(X\) to \(Y\), then they have the same number of elements. There are six bijective functions from \(X\) to \(Y\), the example we gave just happens to not be one of them.
We will now show that the number of tame sequences of length \(n\) is equal to the \(n\)th Catalan number, \(\dfrac{1}{n+1}\dbinom{2n}{n}\). The proof relies on the material from Appendix 1. As well, the results here are well known and proofs of them can be found in the literature.
Definition 4: For each positive integer \(n\), a sequence of \(2n\) integers is called a jagged sequence of length \(2n\) if properties \(P1\) and \(P2\) hold:
\(P1\). Exactly \(n\) of the integers are equal to \(1\) and exactly \(n\) of the integers are equal to \(-1\).
\(P2\). For each integer \(k\) with \(1\leq k\leq 2n\), the sum of the first \(k\) integers in the sequence is non-negative.
Claim 4: There are \(\dfrac{1}{n+1}\dbinom{2n}{n}\) jagged sequences of length \(2n\).
Proof of Claim 4. Fix a positive integer \(n\). Let \(X\) be the set of sequences of \(2n\) integers that satisfy \(P1\) and fail \(P2\). Also, let \(Y\) be the set of sequences of \(2n\) integers, \(n+1\) of which equal \(-1\) and \(n-1\) of which equal \(1\). We will show that \(X\) and \(Y\) have the same number of elements.
Suppose \(\textbf{x} = (a_1,a_2,\dots,a_{2n})\) is in \(X\). Since \(\textbf{x}\) fails \(P2\), there must be some \(k\) with \(1\leq k \leq 2n\) and the property that the sum of the first \(k\) entries is negative. Let \(k\) be the smallest such position in the sequence. If \(a_1=-1\), then \(k=1\). This means \(n\) of the integers in the list \(a_2,a_3,\dots,a_{2n}\) are equal to \(1\), and \(n-1\) of them are equal to \(-1\). Therefore, the sequence \[(a_1,-a_2,-a_3,\dots,-a_{2n})\] has \(n+1\) integers equal to \(-1\) and \(n-1\) integers equal to \(1\), which means it is in \(Y\).
If \(k\neq 1\), then \(a_1\geq 0\), \(a_1+a_2\geq 0\), and so on up to \(a_1+a_2+\cdots+a_{k-1}\geq 0\), but \(a_1+a_2+\cdots+a_k<0\). Since \(a_1+a_2+\cdots+a_{k-1}\geq 0\) but \(a_1+a_2+\cdots+a_{k-1}+a_k<0\), we must have that \(a_k\) is negative, but \(a_k=\pm 1\), so \(a_k=-1\). As well, each of the \(a_i\) are integers, so the two sums above are integers, which means \(a_1+a_2+\cdots+a_{k-1}=0\) and \(a_1+a_2+\cdots+a_{k-1}+a_k=-1\) (there is no other way to add \(-1\) to a non negative integer and get a negative integer). The fact that \(a_1+a_2+\cdots +a_{k-1}=0\) implies that exactly half of the integers in the list \(a_1,\dots,a_{k-1}\) are equal to \(-1\), and so the number of \(-1\)’s in \((a_1,a_2,\dots,a_k)\) is one more than the number of \(1\)’s. Since the number of \(-1\)’s and \(1\)’s is equal in \(\textbf{x}\), this means the number of \(1\)’s in \((a_{k+1},\dots,a_{2n})\) is one more than the number of \(-1\)’s. All of this implies that \[(a_1,a_2,\dots,a_k,-a_{k+1},-a_{k+2},\dots,-a_{2n})\] has two more \(-1\)’s than \(1\)’s. Two numbers that differ by \(2\) and have a sum of \(2n\) must be \(n-1\) and \(n+1\), so the sequence above is in \(Y\).
The above work defines a function, that we will call \(f\), with domain \(X\) and codomain \(Y\). Specifically, if \(\textbf{x}=(a_1,a_2,\dots,a_{2n})\) in \(X\) and \(k\) the smallest integer such that \(a_1+a_2+\cdots+a_k<0\), \(f(\textbf{x})=(a_1,a_2,\dots,a_k,-a_{k+1},\dots,-a_{2n})\). That is, \(f(\textbf{x})\) is the sequence obtained by negating every integer from \(a_{k+1}\) to the end of the sequence. We will show that \(f\) is a bijection.
To see that \(f\) is injective, suppose \(\textbf{w} = (a_1,a_2,\dots,a_{2n})\) and \(\textbf{x} = (b_1,b_2,\dots,b_{2n})\) are in \(X\) with \(f(\textbf{w})=f(\textbf{x})\). We suppose that \(k\) is the smallest such that \(a_1+a_2+\cdots+a_k<0\) and \(m\) is the smallest such that \(b_1+b_2+\cdots+b_m<0\). We might as well assume that \(k\leq m\). Our assumption says that the sequences \((a_1,a_2,\dots,a_k,-a_{k+1},-a_{k+1},\dots,-a_{2n})\) and \((b_1,b_2,\dots,b_k,-b_{m+1},-b_{m+1},\dots,-b_{2n})\) are equal. Since \(k\leq m\), this means \(a_i=b_i\) when \(1\leq i\leq k\) and when \(m+1\leq i\leq 2n\). Observe that \(a_1+a_2+\cdots+a_k=b_1+b_2+\cdots+b_k\), and since \(a_1+a_2+\cdots+a_k<0\) by assumption, we get that \(b_1+b_2+\cdots+b_k<0\). This means \(m\leq k\) as well and so \(k=m\). Since \(a_i=b_i\) when \(1\leq i\leq k\) and \(k+1\leq i\leq 2n\), we have that \(a_i=b_i\) for all \(i\). In other words, \(\textbf{w}=\textbf{x}\), so \(f\) is injective.
Now suppose \(\textbf{y} = (c_1,c_2,c_3,\dots,c_{2n})\) is a sequence is in \(Y\). Because \(\textbf{y}\in Y\), exactly \(n+1\) of the integers in \(\textbf{y}\) are equal to \(-1\) and \(n-1\) of them are equal to \(1\). Consider the list of sums \[\begin{align*} c_1 \\ c_1+c_2 \\ c_1+c_2+c_3 \\ \vdots \\ c_1+c_2+c_3+\cdots+c_{2n}\end{align*}\] The first "sum", \(c_1\), is either \(-1\) or \(1\). The final sum is \((n-1)-(n+1)=-2\). As we move from one sum to the next in the list above, we add \(c_i\) for some \(i\), which means the sums either increase or decrease by \(1\) as we move down the list. Therefore, there is at least one sum that equals \(-1\) (it could be the first). Suppose \(k\) is the smallest such that \(c_1+c_2+c_3+\cdots+c_k=-1\). Then the sequence \[\textbf{x} = (c_1,c_2,\dots,c_k,-c_{k+1},-c_{k+2},\dots,c_{2n})\] is in \(X\) and \(f(\textbf{x})=\textbf{y}\). To see that \(\textbf{x}\in S\), we have that \(c_1+c_2+\cdots+c_k=-1\) and \(c_1+c_2+\cdots+c_{2n}=-2\), ad so it must be that \(c_{k+1}+c_{k+1}+\cdots+c_{2n}=-1\). Therefore, \(c_1+c_2+c_3+\cdots+c_k+(-c_{k+1})+(-c_{k+2})+\cdots+(-c_{2n})=0\). This means \(\textbf{x}\) has the same number of \(1\)’s and \(-1\)’s, which means there are \(n\) of each. As well, the sequence fails \(P2\) because the first \(k\) integers have a negative sum. This shows that \(\textbf{x}\in X\), and that \(f(\textbf{x})=\textbf{y}\) is essentially by the definition of \(\textbf{x}\). Therefore, \(f\) is surjective, which completes the proof that it is a bijection.
The number of sequences in \(Y\) is \(\dbinom{2n}{n+1}\). This is because we can choose where to put the \(-1\)’s in \(\dbinom{2n}{n+1}\) ways, and then there is no choice of where to place the \(1\)’s. By what we have shown, we now know that there are \(\dbinom{2n}{n+1}\) sequences in \(X\) as well.
We can now compute the number of jagged sequences. The number of sequences of \(2n\) integers that satisfy \(P1\) is \(\dbinom{2n}{n}\) by reasoning similar to that in the previous paragraph. To get the number of jagged sequences of length \(2n\), we need to subtract from \(\dbinom{2n}{n}\) the number of sequences that satisfy \(P1\) but fail \(P2\), which is exactly the number of sequences in \(X\). Therefore, the number of jagged sequences is \[\begin{align*} \binom{2n}{n}-\dbinom{2n}{n+1} &= \dfrac{(2n)!}{n!n!}-\dfrac{(2n)!}{(n+1)!(n-1)!} \\ &= \dfrac{(2n)!}{n!(n-1)!}\left(\dfrac{1}{n}-\dfrac{1}{n+1}\right) \\ &= \dfrac{(2n)!}{n!(n-1)!}\times\dfrac{1}{n(n+1)} \\ &= \dfrac{1}{n+1}\times\dfrac{(2n)!}{n!n!} \\ &= \dfrac{1}{n+1}\binom{2n}{n}\end{align*}\]
◻
Claim 5: The number of tame sequences of length \(n\) is \(\dfrac{1}{n+1}\dbinom{2n}{n}\).
Proof of Claim 5. We will find a bijection from the set of jagged sequences of length \(2n\) to the number of tame sequences of length \(n\).
Suppose \(\textbf{x} = (a_1,a_2,\dots,a_{2n})\) is jagged and that \(i_1<i_2<\dots<i_n\) are the indices where the \(1\)’s occur. That is, \(a_{i_1}=a_{i_2}=\cdots=a_{i_n}=1\) and all other integers in \(\textbf{x}\) are equal to \(-1\). We will now define a sequence \(\textbf{y} = (b_1,b_2,b_3,\dots,b_n)\) so that \(b_k\) is the sum of the integers in \(\textbf{x}\) from \(a_1\) up to and including the \(k\)th integer equal to \(1\). In symbols, \(b_k=a_1+a_2+\cdots+a_{i_k}\).
Of the first \(i_k\) integers in \(\textbf{x}\), exactly \(k\) of them are equal to \(1\) and the other \(i_k-k\) of them are equal to \(-1\). Therefore, their sum (which is \(b_k\) by definition), is \(b_k=k-(i_k-k)=2k-i_k\). Thus, for a jagged sequence \(\textbf{x} = (a_1,a_2,\dots,a_{2n})\), we define \(f(\textbf{x})\) to be the sequence \((b_1,b_2,\dots,b_n)\) where \(b_k=2k-i_k\).
We will show that \(f\) is a bijection, but we first need to confirm that \(f(\textbf{x})\) is always tame, which means we need to show that \(b_1=1\), \(b_k\geq 1\) for all \(k\), and that \(b_{k+1}\leq b_k+1\) for all \(k<n\). We know that \(a_1=1\) by \(P2\), so this means \(i_1=1\) and \(b_1=2(1)-i_1=2-1=1\). Suppose \(i_k\geq 2k\). In \(\textbf{x}\), there are only \(k\) \(1\)’s up to and including \(a_{i_k}\), which means that among the first \(i_k\) integers in \(\textbf{x}\), there are at least as many \(-1\)’s as \(1\)’s. This means the sum of the first \(i_k\) integers cannot be positive. Therefore, we must have that \(i_k<2k\), and since both are integers, \(i_k+1\leq 2k\), which rearranges to \(1\leq 2k-i_k\), which gives \(b_k\geq 1\). To see that \(b_{k+1}\leq b_k+1\), note that \(i_{k}+1\leq i_{k+1}\), so \(i_k-i_{k+1} \leq -1\). Then \[\begin{align*} b_{k+1}-b_k &= 2(k+1)-i_{k+1}-(2k-i_k) \\ &= 2k+2-i_{k+1}-2k+i_k \\ &= 2+i_k-i_{k+1} \\ &\leq 2-1 \\ &= 1\end{align*}\] and so \(b_{k+1}-b_k \leq 1\) or \(b_{k+1}\leq b_k+1\). This completes the proof that \(f(\textbf{x})\) is tame.
To see that \(f\) is injective, notice that \(b_k=2k-i_k\) can be rearranged to get \(i_k=2k-b_k\). In other words, if \(f(\textbf{x})=\textbf{y}\), then \(i_k\) is uniquely determined from \(b_k\). This means that from \(\textbf{y}\), the positions of the \(1\)’s in \(\textbf{x}\) are uniquely determined, so the entirety of \(\textbf{x}\) is uniquely determined by \(\textbf{y}\). This means there is only one \(\textbf{x}\) with the property that \(f(\textbf{x})=\textbf{y}\), so \(f\) is injective.
To see that \(f\) is surjective, suppose \(\textbf{y}=(b_1,b_2,\dots,b_n)\) is a tame sequence. For each \(k\) from \(1\) through \(n\), define \(i_k=2k-b_k\), then define \(\textbf{x}=(a_1,a_2,\dots,a_{2n})\) so that \(a_{j}=1\) if \(j=i_k\) for some \(k\), and \(a_j=-1\) otherwise.
That \(f(\textbf{x})=\textbf{y}\) follows by rearranging \(i_k=2k-b_k\) to get \(b_k=2k-i_k\). However, to conclude that \(f\) is surjective, we need to verify that \(\textbf{x}\) is indeed a jagged sequence.
By one of the conditions of tameness, \(b_1=1\), so so we have that \(i_1=2(1)-1=1\). Using the assumption that \(b_{k+1}\leq b_k+1\) which can be rearranged to \(b_k-b_{k+1}\geq-1\), we get that \[\begin{align*} i_{k+1}-i_k &= 2(k+1)-b_{k+1} - (2k-b_k) \\ &= 2k+2-b_{k+1}-2k+b_k \\ &= 2+b_k-b_{k+1} \\ &\geq 2+ (-1) \\ &= 1\end{align*}\] which means \(i_{k+1}-i_k\geq 1\) and it follows that \(i_{k+1}>i_k\). Finally, since \(b_n\) is positive, \(i_n=2n-b_n<2n\). We have shown that \(1=i_1<i_2<\cdots<i_n<2n\). This shows that all of the \(i_k\) are distinct, so \(\textbf{x}\) satisfies \(P1\).
Rearranging \(i_k=2k-b_k\), we get \(b_k=k-(i_k-k)\), and by the reasoning from earlier, this means the sum of the first \(i_k\) integers in \(\textbf{x}\) (always ending with the \(k\)th \(1\)) is equal to \(b_k\), which is positive because \(\textbf{y}\) is tame. Now consider the sum \(a_1+a_2+\cdots+a_m\) for some an arbitrary \(m\) with \(1\leq m \leq 2n\). If \(m=i_k\) for some \(k\), then the sum is positive by the reasoning just given. Otherwise, there is some \(k\) for which \(i_k < m < i_{k+1}\). Since every integer in \(\textbf{x}\) strictly between \(a_{i_k}\) and \(a_{i_{k+1}}\) equals \(-1\) by construction, we must have that \[a_1+a_2+\cdots+a_m \geq a_1+a_2+\cdots+a_m+a_{m+1}+\cdots+a_{i_{k+1}-1}\] because the latter is obtained from the former by adding some (possibly zero) \(-1\)’s. We know that \(a_{i_{k+1}}=1\) and that \[a_1+a_2+\cdots+a_m+a_{m+1}+\cdots+a_{i_{k+1}-1}+a_{i_{k+1}}\] is positive, so this means \(a_1+a_2+\cdots+a_m\geq 0\).
We have shown that \(\textbf{x}\) satisfies \(P2\) as well, so \(\textbf{x}\) is a jagged sequence with \(f(\textbf{x})=\textbf{y}\). Therefore, \(f\) is surjective, which completes the proof that it is bijective. Therefore, the number of tame sequences of length \(n\) is \(\dfrac{1}{n+1}\dbinom{2n}{n}\). ◻