Reference request for combinatorial problem related to $\max$ relation

Question

Let $x_{i - j}\in\{1,2,\ldots, N\}$, where $i\in\{1,2,\ldots,N\}$ (is fixed) and $0\leq j\leq i$.

Based on such context, I am interested in an explicit formula for the numbers of configurations of $(x_{i},x_{i-1},\ldots,x_{0})$ which satisfy the following relation: \begin{align*} \max\{x_{i},x_{i-1} - 1, x_{i-2} - 2, \ldots, x_{0} - i\} = i \end{align*}

I do not need a full answer (though I would be glad to have one).

I would like to know if anyone could give me some reference so that I could solve it by myself.

I am quite interested in a closed formula if possible.

Any suggestion such as books and articles are more than welcome.

Answer 1

I also don't have a reference, but I think one should be able to do this fairly explicitly as follows [it appears that Peter Taylor alludes to this strategy in their comment above]:

First, note that much easier than your original question is to count the number of tuples $(x_i,...,x_0)$ with $$\max\{x_i,x_{i-1}-1,x_{i-2}-2,...,x_0-i\} \le i,$$ since a tuple has this property exactly when each $x_{i-j} \le j+i$. Since by assumption each $x_{i-j} \in \{1,...,N\}$, for each $j$ we have exactly $\min(i+j,N)$ choices for the value of $x_{i-j}$. Thus we see that the number of such tuples is $ \prod_{j=0}^i \min(i+j,N) $; in particular, if $2i \le N$, then the number of such tuples is just $(i)(i+1)\cdots(2i-1)(2i) = \frac{(2i)!}{(i+1)!}$.

But note that we can exactly analogously compute that the number of tuples $(x_i,...,x_0)$ with $$ \max \{ x_i , x_{i-1} - 1,..., x_0 - i \} \le i - 1$$ is $\prod_{j=0}^i \min(i+j-1,N)$, which again is $(i-1)(i)\cdots(2i-1)$ if $2i-1 \le N$.

But the difference between these two quantities gives exactly the number of tuples with $$ \max \{ x_i , x_{i-1} - 1,..., x_0 - i \} = i,$$ which is what you were looking for. So, for instance if $2i \le N$, the quantity you're looking for is $$ i(i+1)\cdots(2i) - (i-1)(i)\cdots(2i-1) = [(2i - (i-1))](i)(i+1)\cdots(2i-1) = (i+1) \frac{(2i-1)!}{(i-1)!}. $$

The more general lesson here is that the condition $\max(a bunch of junk)=c$ is often hard to get your hands on; but the condition $max(a bunch of junk) \le c$ is equivalent to $j \le c$ for each piece of junk $j$, which is often easier. Thus, its often fruitful to convert problems of the former type into problem of the latter type, just as we did here.

Answer 2

I don't have a reference, but I can suggest an approach for you to solve it yourself. The idea is to condition on the first argument that achieves the maximum. I'll illustrate it for the case $N=5$ and $i=3$. The four cases are

\begin{align} x_3 &= 3,& x_2 &\le 4,& x_1 &\le 5,& x_0 &\le 6 \\ x_3 &< 3,& x_2 &= 4,& x_1 &\le 5,& x_0 &\le 6 \\ x_3 &< 3,& x_2 &< 4,& x_1 &= 5,& x_0 &\le 6 \\ x_3 &< 3,& x_2 &< 4,& x_1 &< 5,& x_0 &= 6 \\ \end{align}

This approach yields $$1\cdot 4\cdot 5 \cdot 6 + 2\cdot 1 \cdot 5 \cdot 6 + 2\cdot 3 \cdot 1\cdot 6 + 2\cdot 3 \cdot 4 \cdot 1 = 240$$ configurations.