I'm working on a problem where I have to figure out how many possible answers there could be. It would be straight multiplication or combinations if it did not have this complication that it has. There are a bunch of variables, and each one is constrained to a range, but most of the time there is also some constraint to the relationships between the variables. I'm having a hard time with the resulting math, and am looking for help understanding the principles that drive the equations.
Let's take a relatively simple example. I have variables $x_1, x_2, \ldots, x_k$ and each one is constrained to a range. For illustration, lets say they are all constrained to the same range, $[1,10]$. So far this is easy, the number of combinations is just $10^k$, $10$ being the number of items in the range.
Now we add a restriction, $x_{k+1} \le x_k$, which is to say that each variable is not allowed to be larger than the one before it, and already I'm on shaky ground figuring out how to calculate the number of combinations.
(TL;DR How do I calculate the number of combinations of $x_1, x_2, \ldots, x_k$ given that each one is constrained to a (possibly different) range and also constrained to be not larger than the one before it? And why is it that when the ranges are the same and start at $1$, the formula is exactly the same as for combinations with replacement?)
I try induction. Obviously for $k = 1$ the answer is $10$.
For $k = 2$, I see that when $x_1 = 1,\; x_2 =[1,1]$, and when $x_1 = 2, \;x_2 = [1,2]$ which leads me to $$\sum_{i=1}^{n} i = \frac {n(n+1)}{2}$$
I understand this formula as pairing up high and low items yielding, for $n=10$, $\frac {n}{2} = 5$ pairs each totaling $(n+1) = 11$:$$(10+1)+(9+2)+(8+3)+(7+4)+(6+5) = 5 \cdot 11 = \frac {n}{2}(n+1)$$
So I definitely understand the sum of the series, and I see how it applies in this case. I also see how to adjust it if the range does not start at $1$ but instead starts at $m$, as you then have $\frac {n-(m-1)}{2}$ pairs of $(n+m)$.$$\frac {n^2-nm+n+nm-m^2+m}{2} = \frac {n(n+1)+m(1-m)}{2} = \frac {n(n+1)-m(m-1)}{2}$$$$ = \frac {n(n+1)}{2} – \frac {(m-1)((m-1)+1)}{2} = \sum_{i=1}^{n} i – \sum_{i=1}^{m-1} i$$
So I feel good about how well I understand this, but I do not understand how to use it as the basis of the induction for $k = 3$.
In combinatorics I'm used to multiplying, but I didn't get from $10$ to $55$ by multiplying, so for $k = 3$ I guess I am now looking at $$\sum_{i=1}^{n}\sum_{j=1}^{i}j$$ which I am having a harder time understanding. I tried searching for "sum of sum of series" but was overwhelmed by "sum of series" answers.
I try the same trick but the pairs are not there. $i_{10} = 55, i_1 = 1, i_9 = 45, i_2 = 3$ but of course $(55 + 1) \ne (45 + 3)$.
Then a miracle happens! I see that the correct answer is $\binom{n+k-1}{k}$.
The thing is, I barely understand why $\binom{n+k-1}{k}$ is the combination of $n$ things taken $k$ at a time with replacement. (I look at it as being able to choose from $k-1$ replacements in addition to the original $n$ items.) I'm even more confused here where we have added the restriction $x_{i+1} \le x_i$. I would have guessed if anything the restriction would lead to the formula for a combination without replacement. Is this just a coincidence or is there some fundamental equivalence I'm missing? And I really don't see how to derive this answer anyway; I just happened upon it.
More importantly, I'm trying to generalize this to arrive at a much more generic calculator I can implement in software, perhaps with $k$ recursions, where I can figure out the number of combinations available with $k$ variables, each of which has an arbitrary lower and upper bound, but also is bound by the value of another variable. So I really need to understand the derivation or the principles her of chaining those limits. Please help me understand.
My current thinking is that Combinations with Replacement differ from Permutations with replacement only in that with Combinations, order doesn't matter, and the $\le$ restriction effectively enforces that only one order of any combination is allowed. Therefore, my guess is that if the restriction were changed to $\lt$, then it would be Combinations without Replacement.
If you can point me to further specific topics to explore in math or computer science, that would also be helpful. I could not find anything beyond standard combinations and permutations that seemed relevant.
Best Answer
The number of tuples $(x_1,\dotsc, x_k)$ with $1\leq x_1\leq x_2\leq \dotsb\leq x_k\leq n$ (these are often called weakly increasing sequences) equals the number of tuples $(y_1\dotsc, y_k)$ with $1\leq y_1<y_2<\dotsb<y_k\leq n+k-1$ via the bijective map $y_i=x_i+i-1$. The latter sequences are in bijection with $k$ element subsets of $[n+k-1]=\{1,\dotsc, n+k-1\}$ (given a $k$-element subset of $[n+k-1]$ order its elements to produce the tuple $(y_1,\dotsc, y_k)$). It folows that the number of weakly increasing sequences is $\binom{n+k-1}{k}$.