Jtdylktuy

I have questions about how to extend the basic combination equations so I can compute them recursively and, at the same time, add range and sorting constraints. I am trying to do this with high school level algebra and running into a lot of difficulty. There must be a better way to think about these things.

(Side note: I'm not a mathematician or a TeX expert, so please feel free to improve on my notation and formatting. However, please don't go too far in replacing words with symbols.)

Given a sequence of variables, $(x_1,dotsc, x_k)$, in a previous question we established that the constraint that all variables be in the range $[1..n]$ makes the number of possible sequences the number of permutations of $n$ taken $k$ at a time with replacement, which is $n^k$.

We also established that adding the requirement that $x_i ge x_{i+1}$ changed the possible number of sequences from permutations to combinations, again with replacement: $$binom{n+k-1}{k} = frac{(n+k−1)!}{k!(n−1)!}$$

Now I would like some help checking my work taking it further.

Recursion, part 1

Keeping the range $[1..n]$ and $x_i ge x_{i+1}$ restrictions.

Given the number of possible sequences $C_{k-1}$ of $(x_1,dotsc, x_{k-1})$, calculate $C_k$
$$C_k = XC_{k-1} = Xfrac{(n+(k−1)-1)!}{(k-1)!(n−1)!} = frac{(n+k−1)!}{k!(n−1)!}$$
$$X = frac{(k-1)!(n-1)!(n+k-1)!}{(n+k-2)!k!(n-1)!}$$
$$X = frac{(k-1)!}{k} frac{(n+k-1)!}{(n+k-2)!}$$
$$ X = frac{n+k-1}{k} implies C_k = C_{k-1} frac{n+k-1}{k} $$

Hey, that was easy! Let's try something a little harder.

Recursion, part 2

Adding restriction $x_k > L$

Now we add a restriction only on $x_k$ that on top of everything else $x_k > L$ for a specific $k$ and $L$. How now do we compute $C_k$ given $C_{k-1}$ and $k$? Seems to me we just subtract the combinations in the range $[1..L]$. Let us call $S_k^n$ the set of $k$-tuples in the set before the restriction and $S_k^{n,L}$ the desired set of $k$-tuples. I'm not great with set notation, but I think it goes like this (please correct me if I'm wrong):
$$begin{align}S_k^n & = {(x_1,dotsc, x_k) | x_i in [1..n] land x_i ge x_{i+1} } \
S_k^{n,L} & = {(x_1,dotsc, x_k) in S_k^n | x_k > L } end{align} $$

It looks like I should just be able to subtract the $x_k in [1..L]$ like this:

$$C_k = (C_{k-1}frac{n+k-1}{k} - C_{k-1}frac{L+k-1}{k}) = C_{k-1}frac{n-L}{k}$$
That looks wrong. The usual lower bound on $n$ is $n > 0$ and plugging $L = 0$ into the equation gives a different answer than the usual equation. Trying a few other examples show that it is in fact, wrong. (If this kind of mistake is common, maybe someone can put in their answer an explanation of the class of mistakes this one falls into.)

Trying again, we still have $x_k le x_{k-1}$, so the answer is less than $C_{k-1}(n-L)$, which means we cannot simply multiply our way out of it.

How many combinations are we subtracting? It is the number of combinations in $C_{k}$ where $x_{k} le L$. Wait, isn't that what I just did? No, not quite. I did some weird recursion that did not respect what came before it. Anyway, the number to subtract is larger than $binom{L+k-1}{k}$ because that is only the number of combinations where all the variables are $le L$. What about all the combinations where some of the variables are larger than $L$? For example
$$(5, 3, 2) in S_3^5text{, but } (5, 3, 2)notin S_3^2$$

We can map all those combinations back to something that starts at 1 with $y_i = x_i - L$. That means the size of that set is the same as the one in the range $[1..(n-L)]$ Now we have
$$|S_k^{n,L}| = binom{n+k-1}{k} - (binom{L+k-1}{k} + binom{n-L+k-1}{k})$$

That's wrong,too, because $S_k^{n-L}$ includes tuples that map back to $x_k > L$. What we really want is $|S_{k-1}^{n-L}|$ times the $(n-L)$ copies there are. No, that's not right, either, there's only one copy where $x_{k-1} = L$, but $binom{2}{k-1}$ copies of $x_{k-1} = 2$. This is not looking good.

I feel like an idiot. How did I miss that $x_i ge x_{i+1}$ and $x_k > L$ means that $x_i > L$ for all $i le k$?! Oh, I know, I was trying to get there from $C_{k-1}$ Anyway, now that I've circled back it is obvious that
$$ |S_k^{n,L}| = |S_k^{n-L}|$$
Still my question is, given $^nC_{k-1} = |S_{k-1}^{n}|$, is there a straightforward way to calculate $^{n-L}C_k = |S_{k-1}^{n-L}|$? Or should I just backtrack and start all over when, having computed $C_{k-1}$ I discover the $x_k > L$ restriction?