In how many of the integer numbers between 0 and 10,000 does the digit 3 appear to the left of 4

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.

States

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

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

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