1
$\begingroup$

For example, a sequence has the defined growth property: if it is a sequence of positive integers $a_{1}, a_{2}, a_{3}....a_{n}$ and such that:

  1. $a_{1}=1.$
  2. $a_{n+1} \leq$ Max$_{1\leq i \leq n}$ ($a_{i}+1$)

We can quickly compute the number of such sequences of length n with the power of dynamic programing:

Let sequence(l, m) be the number of possible sequences with length l and maximum number in the sequence m. The total number of such sequences for a length can be calculated by summing all the sequences with maximum value ranging from 1 to n for length l. The recurrence can be described as:

sequence(l,m) = sequence(l-1, m-1 ) + m * sequence(l-1,m);

(sequence (l,1)=1, sequence(l,m)=0 if l< m)

As we create a table of size l * m, where we fill the matrix column by column. The base case: the first column of the table sequence(l, 1) = 1 and for the subproblems where l < m the number of sequences will be 0 since the maximum element in sequence can't be bigger than the length of sequence. We can now fill the table in the second column and apply the recurrence relation for every cell and obtain the value fro all combinations of l and m. Finally, We can sum up the last row to calculate the number of sequences.

Understand that the text already gives hint for creating the table. but I am still struggling to visualize it. First of all, What exactly is this sequence?

$a_{2} = a_{1+1} \leq max_{1 \leq i \leq 1}(a_{i}+1) $ which mean i can only be 1. Then $a_{2} \leq max(2)$

and $a_{3}\leq max(3)$ but what are some example of such sequence ? Any more guidance for completing the table?

What is exactly m in sequence(l, m)? Where should we place $a_{4}$ in the table of l * m?

$\endgroup$
  • $\begingroup$ A minor typo, "sequence(l,max)=0 if l< m" should be "sequence(l,m)=0 if l< m". $\endgroup$ – Apass.Jack Feb 1 at 18:44
  • $\begingroup$ thank you, updated the text to avoid any future unnecessary confusion. $\endgroup$ – Dmomo Feb 2 at 2:44
  • $\begingroup$ Please credit the source of all quoted material in the question. $\endgroup$ – D.W. Feb 3 at 5:23
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Feb 3 at 7:06
1
$\begingroup$

Here are all such sequences of length 1.

[1]

Here are all such sequences of length 2.

[1, 1]
[1, 2]

Here are all such sequences of length 3.

[1, 1, 1]
[1, 1, 2]


[1, 2, 1]
[1, 2, 2]
[1, 2, 3]

Here are all such sequences of length 4.

[1, 1, 1, 1]
[1, 1, 1, 2]


[1, 1, 2, 1]
[1, 1, 2, 2]
[1, 1, 2, 3]

[1, 2, 1, 1]
[1, 2, 1, 2]
[1, 2, 1, 3]

[1, 2, 2, 1]
[1, 2, 2, 2]
[1, 2, 2, 3]


[1, 2, 3, 1]
[1, 2, 3, 2]
[1, 2, 3, 3]
[1, 2, 3, 4]

Please observe how the sequences grow longer and longer with the condition $$a_{n+1} \leq \max_{1\le i \le n} (a_{i}+1) = 1+\max_{1\le i \le n} a_{i}$$ as well as the recurrence relation $$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m).$$


$a_{2} = a_{1+1} \leq \max_{1 \leq i \leq 1}(a_{i}+1) $ which mean i can only be 1. Then $a_{2} \leq \max(2)$. and $a_{3}\leq \max(3)$.

Yes, $a_{2} \leq \max(2)=2$. However, $a_{3}\leq \max(a_1+1, a_2+1)$. If $a_2=1$, then $a_3\le \max(1+1, 1+1)=2$. While $a_3\le \max(3)=3$ is true, it might be relaxed too much.


Let us see how we are going to fill the two dimensional array sequence($m$,$l$).

For example, how to use the following relation? $$\text{sequence}(4,4) = \text{sequence}(3, 3 ) + 4 * \text{sequence}(3,4)\,.$$ We know sequence$(3,3) = 1$ since there is only one sequence of length 3 and maximum number 3, $[1,2,3]$ or sequence$(3,3) = 1 + 3 * 0 = 1$. There is no sequence of length of length 3 and maximum number 4, since the maximum number in any sequence of length 3 is at most 3. So $$\text{sequence}(4,4) = 1 + 4 * 0 = 1\,,$$ which corresponds to the unique sequence of length 4 and maximum number 4, $[1,2,3,4]$.


What is exactly $m$ in $\text{sequence}(l, m)$? Where should we place $a_4$ in the table of $l * m$?

It looks like you need to understand the recurrence relation.

$$ \text{sequence}(l,m) = \text{sequence}(l-1, m-1 ) + m * \text{sequence}(l-1,m),$$

where $\text{sequence}(l,m)$, $l\ge2$, $m\ge1$ is the number of sequences whose length is $l$ and whose maximum number is $m$. For example, a sequence $(a_1, a_2,a_3,a_4)$ is a sequence of length 4 and whose maximum number is $\max(a_1, a_2,a_3,a_4)$. If that maximum number is $k$, it contributes 1 to $\text{sequence}(4, k)$ if it satisfies the two conditions. For example, sequence $(1,2,3,2)$ contributes 1 to $\text{sequence}(4, 3)$ while sequence $(1,1,2,2)$ contributes 1 to $\text{sequence}(4, 2)$.

Let $a_1, a_2, \cdots, a_l$ be such a sequence. Let us consider its first $l-1$ items, $a_1, a_2,\cdots, a_{l-1}$.

  • The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is smaller than $m-1$. Then $$a_{l} = a_{(l-1)+1}\leq \max_{1\le i \le l-1} (a_{i}+1) = 1+\max_{1\le i \le l-1} a_{i}\lt m$$, which contradicts that fact that the maximum number of all of them is $m.

    So this situation cannot happen.

  • The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is $m-1$. Then $a_l$ must be $m$. Otherwise, the maximum number of the whole sequence will be $m-1$ instead of the required $m$.

    So for each sequence counted in $\text{sequence}(l-1, m-1 )$, we have a sequence that should be counted in $\text{sequence}(l, m)$. We have a summand $\text{sequence}(l-1, m-1)$

  • The maximum number of $a_1, a_2,\cdots, a_{l-1}$ is $m$. Then $a_l$ can be anyone of $1, 2, \cdots, m$ $m$. So for each sequence counted in $\text{sequence}(l-1, m)$, we have $m$ sequences that should be counted in $\text{sequence}(l, m)$. That is, we have a summand $ m * \text{sequence}(l-1, m)$.

Combining all three cases above, we obtain that recurrence relation.

$\endgroup$
  • $\begingroup$ Yes. It was done relaxing too much that I mentally just skip the something important. Where should we put $a_{4}$ in the table of l * m ? bit confused by "Let sequence(l, m) be the number of possible sequences with length l and maximum number in the sequence m." $\endgroup$ – Dmomo Feb 2 at 2:34
  • $\begingroup$ Whenever you see sequence(l, m), read it as myCount(l,m) like a mathematical function or myCount[m][l] like a Java 2D array, since it maps a pair of integers to another integer. $\endgroup$ – Apass.Jack Feb 2 at 3:17
  • $\begingroup$ Why [1, 1, 3] is not in the sequence of length3 again? It seems totally valid one, it never exceed the length and the maximum is 3. $\endgroup$ – Dmomo Feb 2 at 15:50
  • $\begingroup$ For sequence [1,1,3], a_1=1, a_1=1, a_3=3. Now let us the requirement, $a_{n+1} \leq\max_{1\leq i \leq n}(a_{i}+1)$. Let $n=2$. We get $a_3\le\max_{1\le i\le2}(a_i+1)=\max(a_1+1, a_2+1)=\max(2,2)=2$. However, 3>2. (That is why I said "it might be relaxed too much" in my answer.) $\endgroup$ – Apass.Jack Feb 2 at 16:36
  • $\begingroup$ How would you utilize sequence(𝑙,𝑚)=sequence(𝑙−1,𝑚−1)+𝑚∗sequence(𝑙−1,𝑚). As sequence(4,4), the sequence of the length of 4 and has 4 as maximum number. equal to sequence(3,3) +3∗sequence(3,4), which can't really add up together. sequence(3,3) = 5 + 3* 0 =5 while from sequence (4,4) is 15 in your example. $\endgroup$ – Dmomo Feb 2 at 20:49

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.