0
$\begingroup$

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).

$\endgroup$
8
  • $\begingroup$ I removed one line from the question. So it has changed the problem a little. $\endgroup$ Jun 9, 2015 at 16:35
  • $\begingroup$ I am adding some more explanation. Thanks for your patience. $\endgroup$ Jun 9, 2015 at 16:45
  • $\begingroup$ By "increasing sequence", do you mean "strictly increasing sequence"? $\endgroup$ Jun 9, 2015 at 17:06
  • $\begingroup$ No I meant greater than or equal to the previous element. $\endgroup$ Jun 9, 2015 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$
    – user208649
    Jun 10, 2015 at 1:31

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer. This is what I was looking for. $\endgroup$ Jun 10, 2015 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.