 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Counting appearances (Posted on 2017-11-01) 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.

 No Solution Yet Submitted by Ady TZIDON No Rating Comments: ( Back to comment list | You must be logged in to post comments.) solution Comment 1 of 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      110    10   120   252    120     1011    11   165   462    330     55       112    12   220   792    792    220      1213    13   286  1287   1716    715      78       114    14   364  2002   3432   2002     364      1415    15   455  3003   6435   5005    1365     105       116    16   560  4368  11440  11440    4368     560      1617    17   680  6188  19448  24310   12376    2380     136      118    18   816  8568  31824  48620   31824    8568     816     1819    19   969 11628  50388  92378   75582   27132    3876    171        120    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=01111111110111001100010000`
`k=111101    1101011011    1011010111    1001011001    101001001110001`
`k=210101`

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 Please log in:
 Login: Password: Remember me: Sign up! | Forgot password

 Search: Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2021 by Animus Pactum Consulting. All rights reserved. Privacy Information