How many n-digit binary strings are there with 01 repeated exactly k times?
Provide both the formula and the table for n up to n=20.
The string must begin with a digit 1.
If the binary string ends with a 1, the number of occurrences of 01 will be identical to the number of substrings of successive zeros. If the string does not end in 1, the number of occurrences of 01 will be one less than the number of strings of successive zeros. For example:
11000011001 has two strings of zeros; it also has two occurrences of 01.
11000011000 has two strings of zeros, but only one occurrence of 01.
In an n-digit binary number, there are n-1 places where the digit stream can either flip to its opposite: 0 to 1 or 1 to 0, or stay the same. Strings of 1's or 0's are demarcated by flips in these positions.
The number of occurrences of 01 equalling k then consists of two possibilities: there are k strings of zeros where the full string ends in a 1, or there are k+1 strings of zeros where one of these strings of zeros is at the end of the full string. The former situation has an even number of flip points: 2*k in fact; the latter situation has an odd number: 2*k+1, the odd one out being ineffective in producing an 01.
There are n-1 positions where the flips could take place, so the number of ways of getting k 01's is C(n-1,2*k)+C(n-1,2*k+1).
The table:
\
n \ k 0 1 2 3 4 5 6 7 8 9
\
3 3 1
4 4 4
5 5 10 1
6 6 20 6
7 7 35 21 1
8 8 56 56 8
9 9 84 126 36 1
10 10 120 252 120 10
11 11 165 462 330 55 1
12 12 220 792 792 220 12
13 13 286 1287 1716 715 78 1
14 14 364 2002 3432 2002 364 14
15 15 455 3003 6435 5005 1365 105 1
16 16 560 4368 11440 11440 4368 560 16
17 17 680 6188 19448 24310 12376 2380 136 1
18 18 816 8568 31824 48620 31824 8568 816 18
19 19 969 11628 50388 92378 75582 27132 3876 171 1
20 20 1140 15504 77520 167960 167960 77520 15504 1140 20
As a check, note that the numbers in each row add up to 2^(n-1) as that is the number of choices in the positions other than the first. For example, when n=5, the 16 binary sequences arranged by k:
k=0
11111
11110
11100
11000
10000
k=1
11101 11010
11011 10110
10111 10010
11001 10100
10011
10001
k=2
10101
DefDbl A-Z
Dim crlf$
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For n = 3 To 20
Text1.Text = Text1.Text & mform(n, "#0")
For k = 0 To (n - 1) / 2
v = combi(n - 1, 2 * k) + combi(n - 1, 2 * k + 1)
m$ = String(Int(5 + 8 * k / 20), "#") + "0"
Text1.Text = Text1.Text & mform(v, m)
Next
Text1.Text = Text1.Text & crlf
Next
Text1.Text = Text1.Text & crlf & " done"
End Sub
Function combi(n, r)
c = 1
For i = n To n - r + 1 Step -1
c = c * i
Next
For i = 2 To r
c = c / i
Next
combi = c
End Function
Function mform$(x, t$)
a$ = Format$(x, t$)
If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
mform$ = a$
End Function
|
|
Posted by Charlie
on 2017-11-01 16:09:16 |
solution