All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Counting appearances (Posted on 2017-11-01) Difficulty: 3 of 5
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 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      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
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 (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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