Expected number of ordered sub-sequences in a sequence Let $S$ be a sequence of integers, of length $n$. Compute the expected value of ordered sub-sequences contained with-in it.
Am I correct in assuming, that there is a need for a set $N$, from which the elements of $S$ are picked, in order to be able do draw conclusions about the expected value? Can we make the set $\mathbb{N}$? How does the problem change if we expand our set to $\mathbb{Q}$?
How may I go about constructing a distribution, that allows such computations?
My attempt, falls short. 
Let $E_l$ be the event of picking an ordered sequence of length $l$. Let $c_l$ be the last integer chosen.
$\mathrm{p(E_{l+1} | E_l)} = \mathrm{p(E_l)}\mathrm{p(\mathbb{1}_{n>c})}$
$\mathrm{p(\mathbb{1}_{n>c})} = 1- \frac{c_l}{|N|}$
$\mathrm{p(E_{l+1} | E_l)} = \mathrm{p(E_l)} - \frac{c_l\mathrm{p(E_l)}}{|N|}$
As the $c_l$ is unknown, I am unable to solve the recurrence. Should I treat it like a random variable as well (similar to how the variance is taken as a random variable in $T$ distribution)?
Example:
Let $N\subset\mathbb{N}$, and the sequence chosen at random (with repetition) is
$S=\{3,2,4,2,4,3,4,5\}$
S contains two ordered sub-sequences, namely 
$sS_1=\{2,4\}$ , $sS_2=\{2,4\}$, $sS_3=\{3,4,5\}$
The number of ordered sub-sequences is three.
Please forgive any non-formalities, I am an amateur exploring his interest.
 A: Here are two approaches to solve (the second one changes the question but gives more intuition): 
Problem:
Let $\{X_1, X_2, X_3, ...\}$ be an infinite sequence of independent and identically distributed (i.i.d.) random variables with cumulative distribution function (CDF) $F_X(x) = P[X_i\leq x]$ for all $x \in \mathbb{R}$.  We want to count runs of increasing subsequences, not counting subsequences of size 1 (and not counting overlaps).
Approach 1 (dynamic programming):
Define $m[k]$ as the expected number of increasing subsequenes (of size at least 2) within a random string of length $k$.  How do we find $m[k]$? 
For each integer $l>0$, define:
\begin{align}
\theta[l] &= P[\{X_1 < X_2 < ... < X_l\} \cap\{X_l \geq X_{l+1}\}]\\
z[l] &= P[\{X_1 < X_2 < ... < X_l\}]
\end{align}
Assuming the $\theta[l]$ and $z[l]$ values are known, we get a recursion for $m[k]$: 
\begin{align}
m[0]&=0\\
m[1]&=0\\
m[k]&= \theta[1]m[k-1] + \left[\sum_{l=2}^{k-1}\theta[l](1+m[k-l])\right] + z[k]\quad \forall k \geq 2
\end{align} 
Explanation: The first term of the above equation considers the situation when the first increasing subsequence has length 1.  In that case, we do not count it, and the total number of increasing subsequences in the sequence is the same as the total number in the remaining $k-1$ numbers.  The second term considers the cases when the first increasing subsequence is size $l \in \{2, ..., k-1\}$.  In that case we count it, and the total number is 1 plus the number in the remaining $k-l$ numbers of the sequence.  The last term considers the situation when the entire $k$-length sequence is increasing (so we count it as "1"). 
With this approach, the $m[k]$ values can be computed recursively in terms of $m[i]$ values for $i \in\{0, ..., k-1\}$. This assumes we know $\theta[l]$ and $z[l]$ for all relevant $l$. These can be computed in terms of the particular CDF function $F_X(x)$ that you have.  The simplest case is when $F_X(x)$ is continuous for all $x \in \mathbb{R}$, since all continuous CDF functions give rise to the same $\theta[l]$ and $z[l]$ values.  Indeed, a continuous CDF ensures the probability of two numbers being exactly the same is 0.  Hence, (with prob 1) all numbers are distinct. Since all permutations are equally likely, we get $z[l]=1/l!$ in that case.  (Similarly, you can compute $\theta[l]$ by counting the number of orderings associated with its event.)
Here are particular values computed from the above recursion (for the continuous CDF case): 
\begin{align}
m[30] &=8.608011\\
m[40] &= 11.517894\\
m[50] &= 14.427778 \\
m[100] &=28.977195\\
m[500] &= 145.372537
\end{align}
Approach 2 (renewal theory):
Let's change the question to the following: 
1) What is $\lim_{k\rightarrow\infty} \frac{m[k]}{k}$? 
2) Consider a "frame" as a run length of increasing numbers (including frames of size 1).  What is the average frame length?  
By renewal theory we can say: 
$$ \lim_{k\rightarrow\infty} \frac{m[k]}{k} = \frac{P[\mbox{frame length $\geq 2$}]}{E[\mbox{frame length}]} = \frac{1-\theta[1]}{E[\mbox{frame length}]} $$ 
If the CDF $F_X(x)$ is continuous then $\theta[1]=1/2$ (since the events $\{X_1<X_2\}$ an $\{X_1>X_2\}$ are equally likely). If we define $L$ as the random run length then $L=\sum_{i=1}^{\infty}X_i$ where $X_i$ is an indicator function that is 1 if $\{X_1<X_2 < ...< X_i\}$, and 0 else. So: 
$$ E[\mbox{frame length}]=E[L]=\sum_{i=1}^{\infty} E[X_i] = \sum_{i=1}^{\infty} \frac{1}{i!} = e-1$$
Thus, with a continuous CDF we get: 
$$ \lim_{k\rightarrow\infty} \frac{m[k]}{k} = \frac{1/2}{e-1} = \frac{1}{2(e-1)} \approx 0.290988353 $$
