Number of ways to choose, with repetitions, $K$ integers from a set $\{1...n\}$ having Longest Increasing Subsequence (LIS) of length $L$ I know that we can get the answer, for a fixed $L$, using the sum $$\sum_{p_i}\binom{n + d_i}{K}$$
, where the summation is over all permutations $p_i$ of $K$ integers having $LIS$ equal to $L$, and $d_i$ is the number of descents of $p_i$.
The permutations comes from the fact that we only consider the relative order of the chosen $K$ numbers, bit I don't understand how to deal with repetitions in this set and how descents help with it. I suspect there is some bijection. Could you help me find it, please?
Note, that this question is somewhat algorithmic in nature and a more straightforward way would be to consider all weak orderings (Fubini number of them), but I'm interested in the relation between weak orderings, permutations, and weak orderings when we consider $LIS$ as the only characteristic.
Edit. Here's the link to the code that checks this fact for some quite large $N$ and small $K$, as I have to generate orderings of $K$ integers. Computations are done modulo some prime. https://ideone.com/mDo1pG
 A: Seems like I've managed to find an interpretation.
I initially though that permutation defines a strict ordering of $K$ numbers, but that leads into nowhere.
Let's denote $\{a_i\}$ as the sequence of chosen $K$ elements. Then the sequence corresponds to a permutation $p$ if $a_{p_i} \lt a_{p_j}$, for $i \lt j$, i.e. the position of $k$-th smallest element is $p_k$. It's easy to see that the $LIS$ is preserved: $$i \lt  j, p_i \lt p_j \implies a_{p_i} \lt a_{p_j}$$. If we didn't allow repetition, then $\binom{N}{K}$ would count the number of ways to choose a sequence that corresponds to a given permutation as we already know the order of chosen numbers — assign smallest of them to $a_{p_1}$, second smallest to $a_{p_2}$, etc.
Now, if we have a descent, that is $p_i \gt p_{i + 1}$, we can ease the requirement of $a_{p_i} \lt a_{p_{i + 1}}$ to that of $a_{p_i} \le a_{p_{i + 1}}$ because the two elements will never belong to some increasing subsequence in both cases, and, on the other hand, $a_{p_{i + 1}}$ can still be in all increasing subsequences it used to be as it can only become equal to — and never less than, due to construction — the previous element in the subsequence only if we have a descending run, but any two elements in a descending run can never be in some increasing subsequence.
Now, suppose that we have only one descent $p_i \gt p_{i + 1}$. Then there are $$\binom{N}{K}+\binom{N}{K-1} = \binom{N+1}{K}$$ ways to choose a sequence — first summand corresponds to the case where all numbers distinct, and the second one corresponds to the case where $a_{p_i} = a_{p_{i + 1}}$.
If we had two descents, there would be $$\binom{N}{K}+2\binom{N}{K-1} + \binom{N}{K-2} = \binom{N+2}{K}$$ ways. Since there are two ways to choose either descent we count the second summand twice.
In general, for a permutation with $d$ descents the sum is $$\sum_{i=0}^{d}\binom{d}{i}\binom{N}{K-i}=\binom{N+d}{K}$$
The equality is precisely the Vandermonde's identity, thanks to @Phicar for pointing it out.
Since every possible subset of descent indices is contained in at least one permutation (not sure about it; it's a claim by intuition), we can indeed map a permutation to some subset of weak orderings of $K$ elements — a permutation with $d$ descents maps to some subset of cardinality $2^{d}$.
I've also checked programmatically that $$\sum_p 2^{d} = \text{Fubini number}$$. So it seems that a bijection I looked for is indeed established, that is, a bijection between the set of permutations of $K$ numbers and a partition of a set of weak ordering of $K$ elements that preserves $LIS$.
It's a pity that many claims in this post seem to rely on intuition and checking small cases with a computer program, for I lack knowledge and skills to make a rigorous explanation.
To sum up. I think the matter is closed only after there is a rigorous proof of the last two summation identities.
