# An Interesting subsequence problem

Suppose I have a sequence of $n$ random positive numbers: $A$. I then create subsequences of $A$ of a given length, say $K$. Is it possible by combinatorics to find the number of times a number in $A$ appears at either end positions in the subsequence i.e. at starting position or end position?

For Example if $A = \{1,2,3,4\}$ and $k = 3$, then subsequences are $\{1,2,3\}, \{1,2,4\}, \{1,3,4\}$ and $\{2,3,4\}$. Here $1$ appears $3$ times at position $1$ or call it start position(here it won't appear at the last position as we keep the order of the elements in the subsequence same as $A$, which is obvious), $2$ appears once at the start position. Also, $3$ appears appears once at end position and $4$ appears thrice.

Now what I tried: Suppose we do this for $1$ in $A$ so I fix the position of $1$ at the first position in my subsequence. Now I need $2$ more numbers from $A$ or $K-1$ in general. Also, I now only have the elements that are after 1 to choose from A which would be equal to $n-($position of $A)$. Here I need to choose from $3$ elements($4-1$). So the number of such subsequences is equal to the number of times 1 appears at the first position = $_3C_2$. To be exact I would say $_3C_2\cdot 1$, multiplying with 1 because I use the same permutation(or arrangement) as in $A$

I think similarly we can do this for the last position. Another question is, am I really doing it the right way? Does Combinatorics really work this way? Is the way of thinking really correct? More than the question I got concerned with the way I was thinking. Is this how a Mathematics student would really approach this problem?

Can we also find how many times a number appears at positions other than first and last because let's say in total it appears $X$ times considering any position and then I can subtract the number of times it appears at either of the end positions. But how to determine $X$ or is there a direct way to find the appearances at positions other than end positions? A direct way is appreciated as it would help me with improving the thinking part.

• On its face the description of a sequence of $n$ positive numbers as random is meaningless. Do you know a probability distribution that applies to the selection of numbers? Are the numbers chosen independently? Determining the answer to problems like how many "times a number in A appears at either end" might be understood as an expected value, but the subject matter then would be probability rather than pure combinatorics (absent some simplifying assumptions about the distribution). – hardmath Jul 11 '18 at 1:23
• @hardmath By random I meant they maybe increasing or decreasing or none – resound Jul 11 '18 at 1:39
• @Kusanagi You shouldn't say "random". Instead you should say "arbitrary". – Zach Teitler Jul 11 '18 at 4:04

If I understand the question correctly, we have a sequence of $n$ distinct numbers, $a_1,a_2,\dots,a_n$ and we want to know how many subsequences of length $k$ have $a_i$ in position $j.$ We have to choose $j-1$ of the $i-1$ numbers before $a_i$ and we have to choose $k-j$ of the $n-i$ numbers after $a_i,$ so the answer is $$\binom{i-1}{j-1}\binom{n-i}{k-j}$$
• That's exactly what I wanted. Also how to compute the total number of times each element would appear considering all subsequences of length K and all positions. Is it $_n-1C_k-1$ – resound Jul 11 '18 at 4:00
• Yes, that's right. Note that to get the formatting right, you have to put braces around the subscripts: $_{n-1}C_{k-1}$ displays as $_{n-1}C_{k-1}$ – saulspatz Jul 11 '18 at 4:04