Number of numbers Given a set of digits {D1, D2, D3 ... DM}, how many sequences of length 'N' are possible with the constraint that a digit 'K' can only appear in the sequence if all the digits less than 'K' present in the given set, have already appeared in the sequence at least once. Of course, the digits may repeat themselves.
As an example when N=3, with the set being S={1,2,3} the following can be the sequences: {111, 112, 121, 122, 123}
We cannot consider {222, 223, 233 or 333} as '1' is present in the given set S, and a '2' cannot be included in the o/p sequence until a '1' is already present.
Thanks!
 A: These are the Bell numbers. The most familiar interpretation of $B_n$ is that it is the number of partitions of a set of $n$ elements. Here you have another common interpretation: $B_n$ is the number of rhyme schemes of an $n$-line stanza. These are usually represented by letters rather than by numbers, but the rule is the same: the first line is labelled $A$, the first line different from $A$ is labelled $B$, and so on, so that you never use a label that is more than one place further in the alphabet than furthest label already used.
The Bell numbers are sequence OEIS A$000110$; at that link you’ll find much more information and copious references. They satisfy the recurrence
$$B_{n+1}=\sum_{k=0}^n\binom{n}kB_k$$
and have the rather elegant generating function 
$$g(x)=e^{e^x-1}\;,$$
but they don’t have any nice closed form.
Added: To see that the number of rhyme schemes of length $n$ is the same as the number of partitions of $\{1,\ldots,n\}$, consider the following correspondence. If $a_1a_2\ldots a_n$ is a (numerical) rhyme scheme as described in the question, let $m=\max\{a_1,\ldots,a_n\}$. For $a=1,\ldots,m$ let $P_a=\{k:a_k=a\}$; then $\{P_1,\ldots,P_m\}$ is the partition of $\{1,\ldots,n\}$ corresponding to $a_1\ldots a_n$. This association is easily seen to be bijective.
As an example with $n=4$, the rhyme schemes $1111,1213$, and $1234$ correspond to the partitions $\big\{\{1,2,3,4\}\big\},\big\{\{1,3\},\{2\},\{4\}\big\}$, and $\big\{\{1\},\{2\},\{3\},\{4\}\big\}$, respectively.
A: This looks like  $$\displaystyle \sum_{i=1}^M S_2(N,i)$$ where $S_2(N,i)$ are Stirling numbers of the second kind.
For $M \le N$ the partial sums are given in OEIS A102661. For $M \ge N$ this gives Bell numbers as Brian M. Scott notes.  
