Very interesting question.
I've founded a function, but I just don't have time to post a proof.
The first function is the number of sequances with length n and starting number k:
Then the number we're looking for is:
How to put this into an equation, I'm not sure. I'll have to think about it some more.
]]>In how many different way can this be done?
]]>