0
$\begingroup$

I was trying to find all subsequences constrained to the following conditions:

  1. remove element from the end.
  2. remove element from the beginning.
  3. remove element from both sides.

For example, given the sequence $(1,2,3,4)$ have subsequences $\{(1,2,3,4), (1,2,3), (1,2), (1), (2,3,4), (2,3), (2), (3,4), (3), (4)\}$. So, we have get total 10 subsequences.

Attempt: I was thinking of using combinators ${N}\choose{i}$, where $N$ is the length of subsequence in our case and $i$ is the limit boundary of subsequence that starts at $i=1$ and increase all the way to $N-1$. However, since jumps are not allowed, this approach does not seem valid as it will count subsequence like $(1,3,4)$ which is not allowed.

Can you think of an hint/approach based on combinators/permutations to solve this please if possible or this can only be solved iteratively (through for loops/recursion)?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

If I understand it correctly, you are counting the number of continuous subsequences. Every continuous subsequence one-to-one corresponds to a pair of positions representing its start position and end position, so the total number is $\binom{N}{2}$.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.