Sequences that contain subsequence $1,2,3$ How many sequences can we construct using $a$ $1$'s, $b$ $2$'s and $c$ $3$'s under the condition that we can find $1$ before $2$ before $3$ (somewhere, in that order, but not necessarily consecutive)?
For example $2,3,1,3,2,1,1,3$ would fit.
And, if the answer turns out to be easy, is it possible to generalize to four or more different symbols (numbers) ?
 A: If you had just $2$ and $3$ and you need the subsequence $2,3$ you could position the $2s$ in $\binom {b+c}b-1=d(b,c)$ ways, because the inadmissible one is with all the twos in sequence at the end. Let $f(a,b,c)$ be the number you are looking for.
Then the first number in the sequence is either $1$, in which case you need to pick out $b+c$ places for the twos and threes and then arrange them in one of the $d(b,c)$ ways, or the first number is $2$ or $3$, so that $$f(a,b,c)=\binom {a+b+c-1}{b+c}\left(\binom {b+c}b-1\right)+f(a,b-1,c)+f(a,b,c-1) $$
That does not look as though it will readily yield an easy answer, but it allows systematic computation. The final answer should be symmetric in $a$ and $c$, and this expression is not obviously so, so there may be a better way of looking at it.
A: Some small cases:
f(1,N,1): The 1 must go before the 3; pick any two of $N+2$ digits to be those two, except if 1 is adjacent to 3, so $$f(1,N,1)={N+2\choose2}-{N+1\choose1}={N+1\choose2}$$
f(2,N,1): The 1s and 3s either go 113 or 131.  In the first case, you have a solution unless 113 is a solid block; and in the second case unless 13 is a solid block, so $$f(2,N,1)={N+3\choose3}-{N+1\choose1}+{N+3\choose3}-{N+2\choose2}$$
In the same way
$$f(3,N,1)={N+4\choose4}-{N+1\choose1}+{N+4\choose4}-{N+2\choose2}+{N+4\choose4}-{N+3\choose3}$$ 
and in general
$$f(M,N,1)=M{N+M+1\choose M+1}+1-{N+M+1\choose M}\\
={N+M+1\choose M,N,1}+1-{N+M+2\choose M+1}$$
which gives a nice formula for the number that lack a 123.
For $f(2,N,2)$ that has 1133,1313,1331,3113 or 3131, it comes to 
$$f(2,N,2)=5{N+4\choose4}-2{N+1\choose1}-2{N+2\choose2}-{N+3\choose3}\\
=5{N+4\choose4}+4+N+1-{N+4\choose3}-{N+3\choose2}-{N+2\choose1}-{N+1\choose0}\\
={N+4\choose N,2,2}+N+5-{N+5\choose3}-{N+4\choose4}$$
EDIT: Some more calculation has led to this formula:  Let D=a+b+c, then 
$$f(a,b,c)={D\choose a,b,c}+{D\choose0}+{D\choose1}+...+{D\choose a-1}\\
-{D\choose c}-{D\choose c+1}-...-{D\choose a+c}$$
A: Given a finite alphabet ${\cal A}=\{1,\ldots,k\}$, a word $w=w_1\cdots w_n$ over $\cal A$ and letter counts $a:{\cal A}\to {\Bbb Z}$, let
$$f(w_1\cdots w_n; a_1,\ldots,a_k)$$
denote the number of words over $\cal A$ with $w$ as a subsequence, in which letter $i$ occurs $a_i$ times.  We give a simple recursive formula for $f$.  The problem asks for $f(123;a,b,c)$.
We enumerate valid words as follows.  Define $u_i$ to be the number of occurrences of $i$ to the left of the first occurrence of $w_1$ (which we may assume is the beginning of the desired subsequence.)  (Note $u_i=0$ if $i=w_1$.)  Then the leftmost $w_1$ occurs at position $1+\sum_i u_i$, and there are
$$\binom{\sum_i u_i}{u_1,\ldots,u_k}$$
ways to fill in the letters to the left of that spot.  The number of ways to finish off the word can be computed recursively, as the remainder contains the subword $w_2\cdots w_n$ as a subsequence, and contains $v_i$ copies of letter $i$, where
$$v_i=\begin{cases}a_i-u_i,&i\ne w_1\\a_i-1,&i=w_1.\end{cases}$$
 This leads to the recurrence
$$f(w_1\cdots w_n;a_1,\ldots,a_k)=
  \sum_{u_i\le a_i\atop u_{w_1}=0}
  \binom{\sum_i u_i}{u_1,\ldots,u_k}f(w_2\cdots w_n;v_1,\ldots,v_k).$$
For initial conditions, we have $f(\textbf{w};\textbf{a})=0$ if any $a_i<0$, and $f(\epsilon;\textbf{a})=\binom{a_1+\cdots+a_k}{a_1,\ldots,a_k}$ if $\epsilon$ is the empty word.
Here's Mathematica code which implements the recurrence:
Clear[f];
f[_, a_List] := 0 /; Or @@ Thread[a < 0];
f[{}, a_List] := Multinomial @@ a;
f[w_List, a_List] := f[w, a] = Block[{i = w[[1]]},
    Plus @@ ((Multinomial @@ ReplacePart[#, i -> 0]) f[Rest[w], a - #] & /@
    Tuples[ReplacePart[Range[0, #] & /@ a, i -> {1}]])];

This agrees with the special cases Michael computed in his answer; for example,
f[{1, 2, 3}, {2, #, 2}] & /@ Range[5]

and
Multinomial[#,2,2] + #+5 - Binomial[#+5, 3] - Binomial[#+4, 4]& /@ Range[5]

both return
{11, 47, 127, 275, 520}.

A: Now for $a 1$s, $b 2$s, $c 3$s and $d 4$s.
I think the answer, with $D=a+b+c+d$, is 
$$f(a,b,c,d)={D\choose a,b,c,d}-3^D+
\left(\sum_{i=0}^{a-1}+...+\sum_{i=0}^{d-1}\right){D\choose i}2^{D-i}\\
-\left(\sum_{i=0}^{a-1}\sum_{j=0}^{b-1}+...\right){D\choose i,j,D-i-j}$$
I explain this by counting strings without a 1,2,3,4 subset.
A string without the 1234 subset can be divided into four sections P,Q,R,S:
P contains 2s,3s and 4s
Q contains 1s,3s and 4s
R contains 1s,2s and 4s
S contains 1s,2s and 3s
Sections P,Q,R and S are in that order; some of them may be empty.
There are three choices at each digit, so there would be $3^D$ of these strings.  Take a ternary string T, each digit is $x$,$y$ or $z$.
Let E be the binary string of length 3D, which is $[T=x,T=y,T=z]$
(1) Replace the first $a$ of the $1$s in E with $4$s;
(2) Replace the next $b$ of the $1$s in E with $3$s;
(3) Replace the next $c$ of the $1$s in E with $2$s; and
(4) Leave the rest of the $1$s as $1$s.
To prevent double-counting, none of the four digits must stretch over more than $D$ places.  So delete ternary strings with fewer than $a$ $x$s.  There are $\sum_0^{a-1}{D\choose i}2^{D-i}$ of those.
Similarly, there cannot be fewer than $b$ suitable digits in the next $D$ digits of $E$.  There are $\sum_0^{b-1}{D\choose i}2^{D-i}$ of these ternary strings.
Finally, by Inclusion-Exclusion, add back in ternary strings with two of the four sections stretching more than $D$ places.  There is not enough room for three sections to stretch more than $D$ places.
