Why on earth would you think that we need bother with probability? We don’t. The only thing that matters is the number of elements and the number of options for each.
Example. Take a binary sequence defined as follows. The first element has P(1) = P(0) = 0.5
All succeeding elements have a probability of 0.4 of being the same as the immediately preceding element and a probability of 0.6 of being different.
Do you think this makes a difference to the number of possible sequences? Why would it? It mucks you up if you try dragging probability into it, but if you just stick with combinatorics - which it is - it makes no difference at all.
-
If you have a sequence of length 1 it is trivially true. There are N possible values and N = N^1
-
If you have a sequence with n possible values and you add an element with m possible values the total number of combinations is n x m. i.e. for each of the possible values of the sequence there are m possible combinations - 1 for each of the possible values of the new element.
From these we may proceed by mathematical induction. We need only to show that if a sequence of L elements each of which may take N possible values has N^L possible values then such a sequence of L+1 elements has N^(L+1) possible values.
From 2) above we see that if such a sequence of L elements has N^L possible values then a sequence of L+1 elements has N^L x N possible values. N^L x N = N ^(L+1)
From 1) above we know that for L=1 there are N^L = N possible values
Therefore for all L >= 1 a sequence of L elements, each of which has N possible values has a total of N^L possible values.
QED