Csdrhrt

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.

The number of tuples $(x_1,dotsc, x_k)$ with $1leq x_1leq x_2leq dotsbleq x_kleq n$ (these are often called weakly increasing sequences) equals the number of tuples $(y_1dotsc, y_k)$ with $1leq y_1<y_2<dotsb<y_kleq 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}$.

Foobaz John gave a great, formal answer. This is my attempt at a "right-brained" answer.

You say you have $a$ and $b$, each of which could be an integer from $1$ to $10$, and you are asking about how many possible tuples of $(a, b)$ there are. Obviously, this is going to relate to combinations and permutations, because that is what they are all about.

If there are no restrictions and you consider $a$ to be different than $b$, that is a permutation question. Since $a$ and $b$ can each be $10$ different things, that is $10$ possibilities for $a$ and 10 possibilities for $b$, a.k.a. a permutation of $10$ things taken $2$ at a time with replacement. You can look it up, but it should be apparent that the answer is $10 times 10$ or $10^2$. More generally for $n$ things taken $r$ at a time with replacement (meaning the choices are completely independent), there are $n^r$ possibilities.

Then you add a restriction $b le a$ so how does that change things. Well, it is saying we need to exclude the same tuples we would exclude if order did not matter. If order mattered as in the previous case, we would have, for example, $(1, 2)$ and $(2, 1)$ and count those as 2 possibilities. If order does not matter, we would have to exclude one of those possibilities. The restriction $b le a$ excludes the same duplicates we would otherwise exclude because order did not matter.

This holds even as we extend this to more variables, because for any number of distinct integers, there is only 1 strictly decreasing order, and all the other orders are excluded. So now you have created a situation that is just like a combination. In fact, if the restriction were $b le a$ then the number of possiblities would be exactly what you would get for the combination of 10 things taken 2 at a time: 10 possible first choices * 9 possible second choices, $div$ 2 because only $1$ of the $2$ results has $b < a$. This is $binom{10}2$.

But, you say, I have $b le a$, not $b < a$. O Fine, we will add back in the tuples allowed by $b = a$. As it turns out, these are the same tuples you add to a combination when you allow replacement: all the tuples where there is a repeat. It also still remains the case that the $le$ restriction only allows one of the tuples even with more than 2 variables, because it requires duplicates to be next to each other. It only allows $(2,2,1)$, not $(2,1,2)$ or $(1,2,2)$.

So there you have it: a strict ordering (not allowing equality, a.k.a. duplicates) produces combinations without repeats, and a weak ordering (allowing equals/duplicates) produces combinations with replacement. This applies to any strict ordering of integers you want: less than, greater than, or something else like odds before evens.

For reference: Discrete Mathematics Calculators from Calculator Soup has the formulas and computes the values, too.