In how many of the integer numbers between 0 and 10,000 does the digit 3 appear to the left of 4 In how many of the integer numbers between $0$ and $10\,000$ does the digit $3$ appear some place to the left of the digit $4$? This would include, for example, the numbers $34$, $374$, $4384$ and $3874$, but would not include $27$, $43$, $3650$ or $4333$.
So I am thinking you do $$8\cdot9\cdot1\cdot1+1\cdot9\cdot1+8\cdot1\cdot9\cdot1+1\cdot9\cdot9\cdot1 = 234$$
But I feel like that is too low.
 A: Let $a_n$ denote the number of strings of $n$ digits that contain at least one $3$ somewhere to the left of at least one $4$. You want to calculate $a_4$.
If $b = 0, 1, 2, 4, 5, \dots 9$, there are exactly $a_{n-1}$ such strings whose first digit is $b$. The number of such strings whose first digit is $3$ is the same as the number of $(n-1)$-digit strings containing at least one $4$, or $10^{n-1} - 9^{n-1}$.
Therefore $a_n$ can be calculated using the recurrence relation
$$a_n = 9a_{n-1} + 10^{n-1} - 9^{n-1}, \quad a_1 = 0.$$
We have $a_2 = 1$, $a_3 = 28$, $a_4 = 523$.
Or: We can solve this linear recurrence relation to find 
$$a_n = 10^n - (n+9)9^{n-1}.$$ 
Then $a_4 = 10^4 - 13 \times 9^3 = 523.$
A: We can describe the valid numbers with a FSA using the digits as alphabet (the upper bound on the number is not yet included):

Here the black numbers at the arrows denote the symbol used for the transition. If there is no such number every symbol that isn't used with another transition is valid. The red numbers denote the number of symbols that that result in the given target state.
StatesA: No 3 found yet (initial state)
B: 3 found but no 4 found to the right of the first 3.
C: 4 found to the right of a 3 (final state)
We can represent this as a graph with the following adjacency matrix (weighted with number of symbols that can be used for each transition):
$$A=\begin{bmatrix}9&1&0\\0&9&1\\0&0&10\\\end{bmatrix}$$
Note that any path in this graph starting at vertex 1 corresponds to a number and every path also ending at vertex 3 is one of the numbers we want to count.
We only need to consider numbers 0, ..., 9999 since 10000 obviously doesn't fit the pattern. Therefore we only need to consider words with exactly 4 symbols ($\rightarrow$ path of length 4 in the graph).
Since we've chosen the edge weights of the graph appropriately the number to calculate can be directly read from last entry in the first row of the matrix
$$A^4=\begin{bmatrix}6561&2916&523\\0&6561&3439\\0&0&10000\\\end{bmatrix}$$
A: Revised answer
Marking the first $3$ and the first $4$ after $3$, there are only $6$ cases:
$$\begin{array}{}
3&4&\bullet&\bullet&\implies& 10\cdot10 = 100\\
3&\bullet&4&\bullet&\implies& 9\cdot 10 = 90\\
3&\bullet&\bullet&4&\implies& 9\cdot9 =81\\
\bullet&3&4&\bullet&\implies& 9\cdot10 = 90\\
\bullet&3&\bullet&4&\implies& 9\cdot 9 = 81\\
\bullet&\bullet&3&4&\implies& 9\cdot9 = 81
\end{array}$$
Adding up, $523$.
Note: The first $4$ after the first $3$ has been marked, but this doesn't preclude a $4$ coming before the first $3$.
A: Here is my non-math answer: 523. I wonder if breaking 
the answer out into 6 cases yields duplicates. i.e. the 
same number could be counted in more than one case.
SYS@dbtstmra AS SYSDBA> SELECT COUNT(*) FROM ( SELECT LPAD( rownum, 4, '0') mynum FROM dba_tab_columns WHERE rownum < 10000 ) WHERE mynum LIKE '%3%4%';

  COUNT(*)
----------
       523

1 row selected.

Elapsed: 00:00:00.25

A: Python:
>>> len([l for l in map(list, map(str, range(10001))) if '3' in l and '4' in l[l.index('3'):]])
523


Update:
The list map is not needed:
>>> len([l for l in map(str, range(10001)) if '3' in l and '4' in l[l.index('3'):]])
523

A: Call such an integer good. Pad with initial $0$'s if necessary to make a $4$-digit string from $0000$ to $9999$. 
The easy ones are the ones that begin with $3$. Any such string is good if the $3$-digit string after the initial $3$ contains a $4$. There are $10^3$ $3$-digit strings, of which $9^3$ have no $4$, giving $271$ with at least one $4$.
Now we count the "other" good strings. There are $9$ times as many as there are good strings that begin with $0$, which is the same as the number of $3$-digit good strings.
How many good $3$-digit strings are there? There are the ones that begin with $3$. The remaining $2$-digit string must contain a $4$. There are $19$ of these.
Then there are the ones that begin with something else. How many? $9$ times as many as there are good $4$-digit strings that begin with $00$. There is only $1$ of these. 
We get a total of $271+9(19+(9)(1))$.
Remark: The same idea will take care of the count from say $000000$ to $999999$.
A: As David shows, the formula for this with $d$ digits is
$$10^d - (d+9)9^{d-1}$$ 
We can prove this without the recurrence by showing that there are $9^d + d9^{d-1}$ ($=(d+9)9^{d-1}$) numbers where $3$ does not appear before $4$.
There are $9^d$ $d$-digit string with no $4$ at all, giving us $9^d$.
Every other $d$-digit string has at least one $4$.  Suppose the rightmost occurrence of $4$ is at digit $i \in [1, d]$, then every number before it has $9$ choices (anything but $3$, by assumption) and every number after it has $9$ choices (anything but $4$).  This gives us our $d9^{d-1}$.
Adding the two together gives us all numbers where $3$ is not before $4$, and since there are $10^d$ digits, the answer above is shown to be correct.
