Number of list of increasing n-tuples Let $l=(t_i)_{i\leq k}$ be a list of tuple such that :


*

*$t_0=(0,...,0)$

*$\forall i\leq k-1$, $\exists 1\leq j\leq n$ such that $t_{i+1}[j]=t_i[j]+1$

*$\forall m\neq j$, $t_i[m]=t_{i+1}[m]$


In other words, $l$ is a list of $n$ tuples such that only one position increase by one at each step.
I want to know the number of such list given $n$ (the size of the tuple) and $l$ (the largest element in the tuples). Actually I just need a big O of this number.
The better bound I found is $(l^n)^{(l*n)}$ but it does not take in account the structure of the lists (single increment).
I'm am sure we can do better but failed to do so.
Thanks.
 A: Let your largest element be $t_k=(l_1,l_2,\ldots,l_n)$ with $k=\sum_{i=1}^n l_i$. Your problem is stated with $l_1=l_2=\ldots=l$, but this generalization isn't any more difficult.
Your list can be uniquely described by stating, for each element $t_i, i \le k-1$ which index will have the value exactly 1 less when compared to $t_{i+1}$ (aka: what value has $j$ in your second bullet point).
Since at each index $i$, the value goes from $0$ in $t_0$ to $l_i$ in $t_k$, the index $i$ will be chosen exactly $l_i$ times. Conversely, if you are given a list of $k$ indexes and index $i$ occurs exactly $l_i$ times, this can be turned back into a list of tuples that starts with $(0,0,\ldots,0)$ and ends with $t_k$. Your list of tuples and the list of indices are in a direct 1-to-1 correspondence.
Counting the number of those index lists is easy. You have k elements to bring into a list (order them), but not all of them are different (there are $l_1$ indices of $1$, a.s.o.) That would be permutations with repetition in my terminology, which Wikipedia calls Permutations with Multisets
https://en.wikipedia.org/wiki/Permutation#Permutations_of_multisets
The formula would be
$$\text{#lists} = \frac{k!}{l_1!\cdot l_2!\cdot \ldots l_n!}$$
In your case we have $k=nl$, $l_1=l_2=\cdots l$ and thus
$$\text{#lists} = \frac{(nl)!}{l!^n}$$
