1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – hardmath Jul 11 '18 at 1:23
  • $\begingroup$ @hardmath By random I meant they maybe increasing or decreasing or none $\endgroup$ – resound Jul 11 '18 at 1:39
  • $\begingroup$ @Kusanagi You shouldn't say "random". Instead you should say "arbitrary". $\endgroup$ – Zach Teitler Jul 11 '18 at 4:04
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – resound Jul 11 '18 at 4:00
  • $\begingroup$ 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}$ $\endgroup$ – saulspatz Jul 11 '18 at 4:04

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.