This is more of a rewrite of Brian Tung's answer, since I haven't generated any computer code to find these, but I figure this is ever so slightly more elegant:
The two things to simplify are:
- The numbers in order never appear with a leading "0", and
- The numbers rotate where 2016 can start for each length of digits.
In every case, we just look at two forms for the number of digits adjacent and see where 2016 appears, and rotate the possible wildcard locations. Whatever digit leads in this rotation, it can't be a 0, which eliminates a few edges. 2017 also doesn't appear between digits, like in "9991000", because it doesn't start with a 9.
First off, "2016" contains 4 digits. If we are looking at the sequence before we hit "1000", we would want 2016 to appear in a subsequence like "abcabd". However, every digit in 2016 is distinct, so it could only appear at the end as "cabd". This can't work, since the "a" digit is a first digit, so a = 0 would mean we don't have 3 digits. A similar sort of argument will work with 3, 2, and 1 digit numbers.
For the 6 digit numbers, we can see 2016 isn't a part of 100000. This leaves the case of 4 and 5 digit repetitions.
For 4 digits, we have the form "abcdabc". 2016 appears as "abcd", "bcda", and "cdab". "dabc" is out, because that would make a = 0 which is a leading digit. We have three instances where 2016 appears in the 4 digit numbers then. Note I am not including the last character of the second number, since that just double counts the very first "abcd". That pattern continues throughout.
For 5 digits, we have a free digit, which we could call X, because 2016 is one digit short. We need to fill "abcdeabcd". Let's put the X after 2016, which I believe is doable without loss of generality. Then we compare the letter strings to "2016X"
Then "abcde" = 2016X gives 10 more, "bcdea" gives 9 more since X cannot be 0 here, "cdeab" gives 10 more, and "deabc" another 10. "eabcd" is illegal because a always is 0, so this is the total count of 39 for 5 digits.
Adding up both cases, 39 + 3 = 42 appearances.
This type of argument would also generalize to different numbers, especially ones without zeroes in the decimal expansion. We can see with some algebra that for a k digit number, not starting with 9 and without zeroes in its decimal representation, in the first 10^n numbers we expect about:
$$ \sum_{d = k}^n d * \lfloor{10^{d - k}}\rfloor $$
many appearances, where d is the current number of digits we are considering in the argument here.
So we would expect 50 + 4 = 54 for a number like 1234, but because of the zeroes for numbers like 2016, things get a little complicated. It seems at a glance that you just subtract 11 and 1 from the cases for 2016, so it might be you subtract multiples of these when you add zeroes in. Not sure. I'd also have to think a little bit harder about the cases that involved the edges of digits: numbers like "9100" that appear at "991000" and every higher power.
But hopefully that gives a little insight. Listing the occurrences in order seems to get a result with less understanding than even some half-baked arguments here.