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

$\endgroup$

1 Answer 1

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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