3

Find a recurrence relation for the number of strictly increasing sequences of positive integers such that the first term is 1 and last term is $n$, where $n$ is a positive integer. The sequence is: $a_1$, $a_2$, $a_3$, ... , $a_k$ and $a_1=1$, $a_k=n$ and $a_{j-1}$ < $a_j$ where $j=1,2,3, ... , k-1$.

Here $a_{j-1}$ means the $(j-1)th$ term of the sequence. The solution considers two cases when $a_{k-1} = n-1$ and when $a_{k-1} < n-1$.

I don't understand why two cases are considered.

Glen Selle
  • 107
Vibhav
  • 115
  • No recurrence... just note that having a $k$-term sequence of numbers in $1, \dotsc, n$ in increasing order, with $1$ and $n$ fixed, is just a subset of $k - 2$ of the $n - 2$ elegible values, so $\binom{n - 2}{k - 2}$ possibilities. – vonbrand Aug 27 '15 at 14:01
  • This is the question from Discrete Mathematics by Keneth Rosen, McGraw Hill. – Vibhav Aug 27 '15 at 14:50

3 Answers3

2

Let $f_n(m)$ be the number of $m$-length sequences with first term $1$, last term $n$.

A sequence of length $m$ which ends at $n$ is precisely one of the following two disjoint possibilities:

  • A sequence of length $m-1$ which ends at $n-1$, with $n$ appended
  • A sequence of length $m-1$ which ends at something less than $n-1$, with $n$ appended

The first case: there are $f_{n-1}(m-1)$ options for this.

The second case: there is one option for each of the $n-1$ ending points. Therefore, there are $f_1(m-1) + f_2(m-1) + \dots + f_{n-2}(m-1)$ options.

That is, $f_n(m) = \sum_{i=1}^{n-1} f_i(m-1)$.

The initial conditions are that $f_n(n) = 1$, $f_n(m) = 0$ if $m > n$, and $f_n(1) = 0$.

To be honest, I'm not really sure why they've asked you to split it into those two cases. It's a very artificial distinction.

Patrick Stevens
  • 36,135
  • How can I write superscript and subscript. I found a solution on google. But I don't understand. Here also, I didn't understand the second case. – Vibhav Aug 26 '15 at 13:53
  • This site uses LaTeX (or, more precisely, MathJax). What don't you understand of the second case? The second-to-last element of an $m$-length sequence is either $n$ or it is not. – Patrick Stevens Aug 26 '15 at 14:07
  • The answer I found on google is a.n = 2*a.n-1. – Vibhav Aug 26 '15 at 14:13
  • The answer must both depend on $k$ and $n$, according to your statement of the question. – Patrick Stevens Aug 26 '15 at 14:14
  • @PatrickStevens i don't think $f_1(m-1)$ will contribute to second case ..as in the question it is strictly increasing and $f_1(m-1)$ means that $1$ is the first element as well as the last element of length $m-1$ – sourav_anand Jan 31 '17 at 06:07
  • @PatrickStevens please comment – sourav_anand Feb 07 '17 at 07:32
1

Denote the number of $k$ sequences in $[1, n]$ by $s_{n, k}$. Then we have two cases:

  • $n - 1$ is part of the sequence: There are $s_{n - 1, k - 1}$ sequences of those, just chop off $n$
  • $n - 1$ is not part of the sequence: There are $s_{n - 1, k}$ such ones, you can just shift the end one down.

In all:

$$s_{n, k} = s_{n - 1, k} + s_{n - 1, k - 1}$$

As boundary conditions you have that $s_{n, 2} = 1$ for all $n \ge 2$, and that $s_{n, n} = 1$ for all $n \ge 2$.

It is easy to see that:

$$s_{n, k} = \binom{n - 2}{k - 2}$$

vonbrand
  • 27,812
0

Let $H_n$ be the number of these sequences.

Each sequence ending in $n$ either has $n − 1$ in it or it doesn’t. By removing the last term from a sequence that has $n−1$ in it, you’re left with an increasing sequence starting at $1$ and ending at $n−1$, of which there are $H_{n−1}$. If the sequence doesn’t have an $n − 1$ in it, then replacing $n$ with $n − 1$ leaves an increasing sequence starting at $1$ and ending at $n − 1$, of which there are $H_{n−1}$. So $H_n = 2H_{n−1}$.

There is one sequence starting at $1$ and ending at $2$, so $H_2 = 1$ (it doesn’t make sense to start with $H_2$).

Alex M.
  • 35,207
sourav das
  • 1