Let $n$ be a given positive integer. Let $\mathbb{N}_+$ denote the set of all positive integers. Determine the number of all finite lists $(a_1,a_2,\cdots,a_m)$ such that: (1) $m\in \mathbb{N}_+$ and $a_1,a_2,\cdots,a_m\in \mathbb{N}_+$ and $a_1+a_2+\cdots+a_m=n$. (2) The number of all pairs of integers $(i,j)$ satisfying $1\leq i<j\leq m$ and $a_i>a_j$ is even. For example, when $n=4$, the number of all such lists $(a_1,a_2,\cdots,a_m)$ is $6$, and these lists are $(4),$ $(1,3),$ $(2,2),$ $(1,1,2),$ $(2,1,1),$ $(1,1,1,1)$.
Problem
Source: CGMO 2020 Day2 P8
Tags: combinatorics
13.08.2020 15:57
Nice problem! Here is an outline of the solution. The answer is $2^{n-2} + 2^{\left\lfloor n/2\right\rfloor - 1}$. (Note that this sequence is not currently in the OEIS. Anyone has the time to add it there? The values at $n = 1, 2, \ldots, 14$ are $1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160$; it starts out like A329699 but is not the same.) The proof is a good example of a sign-reversing involution. First, some notations: A finite list $\left(a_1, a_2, \ldots, a_m\right)$ satisfying condition (1) is called a composition of $n$. Let $C$ denote the set of all compositions of $n$. If $\left(a_1, a_2, \ldots, a_m\right)$ is a composition of $n$, then the number of all pairs of integers $(i,j)$ satisfying $1\leq i<j\leq m$ and $a_i>a_j$ will be called the inversion number of $\left(a_1, a_2, \ldots, a_m\right)$. (This is similar to the inversion number of a permutation.) Let $A$ be the set of all compositions of $n$ having even inversion number. Thus, we must prove that $\left|A\right| = 2^{n-2} + 2^{\left\lfloor n/2\right\rfloor - 1}$. Let $B$ be the set of all compositions of $n$ having odd inversion number. Then, the two sets $A$ and $B$ are disjoint, and their union is $C$. Hence, $\left|A\right| + \left|B\right| = \left|C\right| = 2^{n-1}$ (since it is well-known that the number of compositions of $n$ is $2^{n-1}$). Thus we know the sum $\left|A\right| + \left|B\right|$. If we can also find the difference $\left|A\right| - \left|B\right|$ (specifically, we are going to show that $\left|A\right| - \left|B\right| = 2^{\left\lfloor n/2\right\rfloor}$), then we will be able to compute $\left|A\right|$ by solving a simple system of linear equations. So we need to find the difference $\left|A\right| - \left|B\right|$. In other words, we need to find the difference between the number of compositions of $n$ having even inversion number and the number of compositions of $n$ having odd inversion number. We shall do this by matching all compositions of the latter kind with compositions of the former kind, and seeing what compositions of the former kind remain unmatched. (This is what Benjamin and Quinn call the DIE method.) Here is how to define this matching, which is (formally speaking) an injection $\iota$ from $B$ to $A$: If $\left(a_1, a_2, \ldots, a_m\right) \in B$, then there must exist some positive integer $i \leq m/2$ satisfying $a_{2i-1} \neq a_{2i}$. (Why? Because otherwise, the composition $\left(a_1, a_2, \ldots, a_m\right)$ would satisfy $a_1 = a_2$ and $a_3 = a_4$ and $a_5 = a_6$ and so on, which would force it to have an even inversion number -- in contradiction to $\left(a_1, a_2, \ldots, a_m\right) \in B$.) Take the smallest such $i$, and swap the entries $a_{2i-1}$ and $a_{2i}$ of the composition. The resulting composition will belong to $A$ (check this!). We define $\iota\left(a_1, a_2, \ldots, a_m\right)$ to be this resulting composition. Thus, we have defined a map $\iota : B \to A$. In order to see that it is injective, we shall construct a partial inverse. We define $A'$ to be the set of all compositions $\left(a_1, a_2, \ldots, a_m\right)$ of $n$ that satisfy $a_1 = a_2$ and $a_3 = a_4$ and $a_5 = a_6$ and so on. As we have learnt in the previous paragraph, there exist no such compositions in $B$; hence, they all lie in $A$. In other words, $A' \subseteq A$. Notice that $\iota\left(B\right) \subseteq A \setminus A'$ (because swapping the two distinct entries $a_{2i-1}$ and $a_{2i}$ of a composition still leaves them distinct), so we can consider $\iota$ as a map from $B$ to $A \setminus A'$. Now, we define a map $\kappa : A \setminus A' \to B$ in the same way as we defined the map $\iota : B \to A$, except that the existence of $i$ is now guaranteed by the fact that we are starting in $A \setminus A'$. It is easy to see that this map $\kappa$ is inverse to $\iota$ (at least if we consider $\iota$ as a map from $B$ to $A \setminus A'$). Thus, $\kappa$ is a bijection, so that $\left|B\right| = \left|A \setminus A'\right|$. Hence, $\left|A\right| - \left|B\right| = \left|A\right| - \left|A \setminus A'\right| = \left|A'\right|$ (since $A'$ is a subset of $A$). We thus only need to show that $\left|A'\right| = 2^{\left\lfloor n/2\right\rfloor}$. This is an easy exercise in enumeration. The slickest proof is probably by induction on $n$: If $n$ is odd, then any composition in $A'$ must have odd length (because if it had even length, then all its entries would appear in pairs of equal entries; but this would entail that its sum is even, contradicting the fact that its sum is $n$), and we can thus easily find a bijection between $A'$ and the analogous set for $n-1$ instead of $n$ simply by decrementing the last entry of our composition (and removing it entirely if it becomes $0$). If $n$ is even, then any composition in $A'$ either has the form $\left(u_1, u_1, u_2, u_2, \ldots, u_k, u_k\right)$ for some positive integers $u_1, u_2, \ldots, u_k$, or has the form $\left(u_1, u_1, u_2, u_2, \ldots, u_k, u_k, v\right)$ for some positive integers $u_1, u_2, \ldots, u_k, v$ where $v$ is necessarily even (since the sum of all entries of the composition is $n$, thus is even); but both kinds of compositions can easily be bijected to the compositions of $n/2$ (for example, $\left(u_1, u_1, u_2, u_2, \ldots, u_k, u_k, v\right)$ gets sent to $\left(u_1, u_2, \ldots, u_k, v/2\right)$). Thus, we get $\left|A'\right| = 2 \cdot 2^{n/2-1} = 2^{n/2} = 2^{\left\lfloor n/2\right\rfloor}$ when $n$ is even. As explained above, this solves the problem.
14.08.2020 07:43
The answer should be $2^{n - 2} + 2^{\lfloor\frac{n}{2}\rfloor - 1}$ instead? We consider two cases. Case 1: $n = 2k$. Let $f(k)$ be the answer. Obviously, $f(1) = 2$. We claim that $f(k) = 4^{k - 1} + 2^{k - 1}$. This holds for $k = 1$. Assume for $k < x$, this holds. For $k = x$, the $a_i$ have several possibilities: If $m\leq2$, then there are $x + 1$ such pairs. If $m\geq3$ and $a_1 = a_2$, then $(1, j)$ is such pair if and only if $(2, j)$ is such pair, and $(1, 2)$ ia not such pair. So the number of pairs is $f(x - a_1)$. So in this case, there are $f(1) + f(2) +\dots+ f(x - 1) = \frac{4^{x - 1} - 1}{3} + 2^{x - 1} - 1$ pairs. If $m\geq3$ and $a_1\neq a_2$, then note that among $(a_1, a_2, \dots, a_m)$ and $(a_2, a_1, \dots, a_m)$ there are exactly one such pair as the number of such $(i, j)$ of them differ by $1$. So there are $2^{2x - 4} + 2^{2x - 5} + 2\times2^{2x - 6} + 2\times2^{2x - 7} +\dots+ (x - 1)\times2^0 = \frac{2^{2x - 1} + 1}{3} - x$ such pairs in this case. So there are total $4^{x - 1} + 2^{x - 1}$ such pairs, which completes the induction. Case 2: $n = 2k + 1$. Similarly the answer is $2^{2k - 1} + 2^{k - 1}$. $\therefore$ The answer is $2^{n - 2} + 2^{\lfloor\frac{n}{2}\rfloor - 1}$.
14.08.2020 13:49
darij grinberg wrote: ~~~, but both kinds of compositions can easily be bijected to the compositions of $n/2$ (for example, $\left(u_1, u_1, u_2, u_2, \ldots, u_k, u_k, v\right)$ gets sent to $\left(u_1, u_2, \ldots, u_k, v/2\right)$). Thus, we get $\left|A'\right| = 2^{\left\lfloor n/2\right\rfloor - 1}$. As explained above, this solves the problem. @darij grinberg You have small mistake at the last line of your solution. By your reasoning, $\left|A' \right| = 2^{\left\lfloor n/2\right\rfloor - 1} \times 2 = 2^{\left\lfloor n/2\right\rfloor}$. Hence the answer is $2^{n-2}+2^{\left\lfloor n/2\right\rfloor - 1}$.
14.08.2020 18:02
Thanks @Paperwind and @EagleEye (name checks out!). Of course the error was in the part I handwaved away...