CAPS Match 2024

Consider a sweet $n$-configuration $⟨A_{i,j}{⟩}_{1\le i,j\le n}$ with $A_{n,n}\subset \{1,2,\dots ,k\}$. For any $x\in \{1,2,\dots ,k\}$ and $i\in \{1,2,\dots ,n\}$ define $$p_x(i)=|\{j:x\in A_{i,j}\}|.$$ Since $A_{i,j}\subseteq A_{i,j+1}$ for all suitable $i,j$, the set $\{j:x\in A_{i,j}\}$ consists of $p_x(i)$ largest elements of $\{1,2,\dots ,n\}$. Since $A_{i,j}\subseteq A_{i+1,j}$ for all suitable $i,j$, the function $p_x:\{1,2,\dots ,n\}\to \{0,1,2,\dots ,n\}$ is nondecreasing. Therefore every sweet $n$-configuration determines a family $⟨p_x{⟩}_{1\le x\le k}$ of nondecreasing functions $p_x:\{1,2,\dots ,n\}\to \{0,1,\dots ,n\}$. Conversely, every such a family determines a sweet $n$-configuration $⟨A_{i,j}{⟩}_{1\le i,j\le n}$ with $A_{n,n}\subset \{1,2,\dots ,k\}$ in the following way: $A_{i,j}=\{x\in \{1,2,\dots ,k\}:j\ge n+1-p_x(i)\}$. Therefore $f(n,k)=g(n{)}^k$ where $g(n)$ is the number of nondecreasing functions $p:\{1,2,\dots ,n\}\to \{0,1,\dots ,n\}$.

Using the stars-and-bars method, there is a bijection between the family of nondecreasing functions $p:\{1,2,\dots ,n\}\to \{0,1,\dots ,n\}$ and the set of sequences consisting of $n$ stars and $n$ bars. The bijection is given by $$p\to \underset{p(1)}{\underbrace{\ast \ast \cdots \ast }}|\underset{p(2)-p(1)}{\underbrace{\ast \ast \cdots \ast }}|\underset{p(3)-p(2)}{\underbrace{\ast \ast \cdots \ast }}|\dots |\underset{p(n)-p(n-1)}{\underbrace{\ast \ast \cdots \ast }}|\underset{n-p(n)}{\underbrace{\ast \ast \cdots \ast }}$$ Thus $g(n)=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$.

The problem boils down to determining which of the numbers $${\left(\genfrac{}{}{0ex}{}{2n}{n}\right)}^{n^2},{\left(\genfrac{}{}{0ex}{}{2n^2}{n^2}\right)}^n,$$ where $n=2024$, is larger. Note that $$\begin{array}{rl}\left(\genfrac{}{}{0ex}{}{2n^2}{n^2}\right)& =\frac{{\prod }_{i=1}^{n^2}(n^2+i)}{{\prod }_{i=1}^{n^2}i}=\prod _{i=1}^{n^2}\left(\frac{n^2+i}{i}\right)=\prod _{j=0}^{n-1}\prod _{i=1}^n\frac{n^2+jn+i}{jn+i}>\prod _{j=0}^{n-1}{\left(\frac{n^2+jn+n}{jn+n}\right)}^n=\\ & =\prod _{j=0}^{n-1}{\left(\frac{n+j+1}{j+1}\right)}^n={\left(\prod _{j=1}^n\frac{n+j}{j}\right)}^n={\left(\left(\genfrac{}{}{0ex}{}{2n}{n}\right)\right)}^n\end{array}$$ and therefore $${\left(\genfrac{}{}{0ex}{}{2n^2}{n^2}\right)}^n>{\left(\genfrac{}{}{0ex}{}{2n}{n}\right)}^{n^2}.$$

Remark: A sketch of a slightly different way of thinking about $f(n,k)={\left(\genfrac{}{}{0ex}{}{2n}{n}\right)}^k$: Consider an $n\times n$ table. In a cell with coordinates $(i,j)$, list all the elements of the set $A_{i,j}$. Fix an element $x\in \{1,\dots ,k\}$ and consider the cells that contain the number $x$. By the condition, those cells form a region closed under making a step right and making a step up. Such regions are delimited by grid paths that start at $[0,n]$, end at $[n,0]$, and only steps right or down. There are $\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ possible paths for each $x$, thus $f(n,k)={\left(\genfrac{}{}{0ex}{}{2n}{n}\right)}^k$.