How to count number of increasing sequences of length $k$ where the first element can be $x_1$ ways, the second in $x_2$ ways and so on till $n$ and $n \geq k$.

I am not able to solve this problem. I am just a beginner in combinatorics and I have never solved a similar problem before. So please help me and suggest some techniques for solving this. Thanks.

EDIT: Some more explanation:
Consider $n$ multi-sets of length $x_1, x_2, x_3, ...$. All the multi-sets contain the same element repeated $x_i$ times and the elements are in strictly increasing order, ie the repeated number $p_i$ from set $a_i$ (having $x_i$ elements) is less than all the elements of the next multisets. I have to count the number of increasing sequences of length $k$ where each element can be chosen from any of the sets and sequences like 1,2,3 and 1,2,3 are considered different (because of being multisets).

  • $\begingroup$ I removed one line from the question. So it has changed the problem a little. $\endgroup$ – Tyler Durden Jun 9 '15 at 16:35
  • $\begingroup$ I am adding some more explanation. Thanks for your patience. $\endgroup$ – Tyler Durden Jun 9 '15 at 16:45
  • $\begingroup$ By "increasing sequence", do you mean "strictly increasing sequence"? $\endgroup$ – Pierre-Guy Plamondon Jun 9 '15 at 17:06
  • $\begingroup$ No I meant greater than or equal to the previous element. $\endgroup$ – Tyler Durden Jun 9 '15 at 17:07
  • 1
    $\begingroup$ Sets aren't indexed, that multiset would be more commonly written as $\{3\cdot 1\}$. Are you sure that this is what the question intends? $\endgroup$ – TokenToucan Jun 10 '15 at 1:31

I'll do my best to give a plausible interpretation of the problem. We will be creating a weakly increasing ($x_i\leq x_{i+1}$) sequence of length $k$. I'm not sure you really want $n$ multisets, as you want some way to "tag" elements within a multiset. So instead I'll say you have a base alphabet of $n$ letters (we might as well call them $1,2,\dots,n$) and the letter $i$ can come in $a_i$ different colors.

So, for instance, we could have $n=3$ and allow $1$ to be either red or green, and force $2$ and $3$ to be red. Thus if we want a sequence of length $3$, we could have as possible sequences $$ 1^g2^r3^r, \:1^r2^r3^r,\: 1^r1^r1^g, $$ where the superscript denotes the color of each letter.

Now to count all such sequences. Let $j_i$ denote the number of times that $i$ occurs in our sequence, regardless of color. First, we determine $j_i$ for $1\leq i\leq n$. Once we have determined each $j_i$, it is clear what order the uncolored letters must go in, as the sequence is to be weakly increasing. All that is left is to color them. The color of each letter does not affect the increasing nature of the sequence, so we just have $a_i$ colors for the $j_i$ occurrences of $i$, giving us $a_i^{j_i}$ ways to color the $i$s, and thus $$ a_1^{j_1}a_2^{j_2}\dots a_n^{j_n} $$ ways to color the entire sequence. Now summing over the possible values of $j_i$, we get the nasty sum $$ \text{Number of sequences of length }k=\sum_{j_1=0}^n\sum_{j_2=0}^{k-j_1}\dots \sum_{j_{n-1}=0}^{k-j_1-\dots-j_{n-2}}a_1^{j_1}a_2^{j_2}\dots a_{n-1}^{j_{n-1}}a_n^{j_n} $$ where of course there is no summation for $j_n$ as it is determined by the previous $j_i$.

Does this simplify? Maybe in special cases, such as having a constant number of ways to color each letter. But in general I have not found a better answer.

Hope this helps.

  • $\begingroup$ Thanks for the answer. This is what I was looking for. $\endgroup$ – Tyler Durden Jun 10 '15 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.