Problem

Source: CGMO 2020 Day2 P8

Tags: combinatorics



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)$.