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

 Close neighbours (Posted on 2013-04-15)
Denote by S the set of all binary integers that can be written using exactly m zeros and n ones, leading zeros permitted.

How many couples in this set differ exactly by one?

Check your formula for m=6, n=3 and for m=3, n=6.

 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 lower integer of the pair ends in 00, the number of 1's will rise at the expense of the 0's

If the lower integer ends with 01, they become 10 and the numbers of 1's and zeros stay the same.

If the lower integer ends with 10, they become 11 and the number of 1's rises at the expense of the 0's.

If the lower integer ends 11, they both become 0, decreasing the count of 1's by two and increasing that of 0's by two. The carry of 1 can either increase the  1 count of the pair to the left by 1, by zero, or again reduce it by 2.

So, of the C(m+n,m) numbers with m zeros and n 1's, only the ones ending in 01 differ by 1. The count of these numbers is C(m+n-2,m-1).

In the test cases presented:

for m=6, n=3; C(7,5) = 21

All the combinations of 6 zeros and 3 1's:

`111000000 000000111 000001011 000001101 000001110 000010011 000010101 000010110000011001 000011010 000011100 000100011 000100101 000100110 000101001 000101010000101100 000110001 000110010 000110100 000111000 001000011 001000101 001000110001001001 001001010 001001100 001010001 001010010 001010100 001011000 001100001001100010 001100100 001101000 001110000 010000011 010000101 010000110 010001001010001010 010001100 010010001 010010010 010010100 010011000 010100001 010100010010100100 010101000 010110000 011000001 011000010 011000100 011001000 011010000011100000 100000011 100000101 100000110 100001001 100001010 100001100 100010001100010010 100010100 100011000 100100001 100100010 100100100 100101000 100110000101000001 101000010 101000100 101001000 101010000 101100000 110000001 110000010110000100 110001000 110010000 110100000`

Those that differ by 1:

` 13           000001101      14           000001110 21           000010101      22           000010110 25           000011001      26           000011010 37           000100101      38           000100110 41           000101001      42           000101010 49           000110001      50           000110010 69           001000101      70           001000110 73           001001001      74           001001010 81           001010001      82           001010010 97           001100001      98           001100010 133          010000101      134          010000110 137          010001001      138          010001010 145          010010001      146          010010010 161          010100001      162          010100010 193          011000001      194          011000010 261          100000101      262          100000110 265          100001001      266          100001010 273          100010001      274          100010010 289          100100001      290          100100010 321          101000001      322          101000010 385          110000001      386          110000010`

The count of these:
21

For m=3, n=6, C(7,2) = 21:

All the combinations of 3 zeros and 6 1's:

`111111000 000111111 001011111 001101111 001110111 001111011 001111101 001111110010011111 010101111 010110111 010111011 010111101 010111110 011001111 011010111011011011 011011101 011011110 011100111 011101011 011101101 011101110 011110011011110101 011110110 011111001 011111010 011111100 100011111 100101111 100110111100111011 100111101 100111110 101001111 101010111 101011011 101011101 101011110101100111 101101011 101101101 101101110 101110011 101110101 101110110 101111001101111010 101111100 110001111 110010111 110011011 110011101 110011110 110100111110101011 110101101 110101110 110110011 110110101 110110110 110111001 110111010110111100 111000111 111001011 111001101 111001110 111010011 111010101 111010110111011001 111011010 111011100 111100011 111100101 111100110 111101001 111101010111101100 111110001 111110010 111110100`

Those that difffer by 1:

125          001111101      126          001111110
189          010111101      190          010111110
221          011011101      222          011011110
237          011101101      238          011101110
245          011110101      246          011110110
249          011111001      250          011111010
317          100111101      318          100111110
349          101011101      350          101011110
365          101101101      366          101101110
373          101110101      374          101110110
377          101111001      378          101111010
413          110011101      414          110011110
429          110101101      430          110101110
437          110110101      438          110110110
441          110111001      442          110111010
461          111001101      462          111001110
469          111010101      470          111010110
473          111011001      474          111011010
485          111100101      486          111100110
489          111101001      490          111101010
497          111110001      498          111110010

count of these:
21

The basic test program, in this case for 6 zeros and 3 1's:

DECLARE SUB permute (a\$)
CLS
a\$ = "111000000": h\$ = a\$
DIM used(512), bsave\$(512)
DO
PRINT a\$; " ";

v = 0
FOR i = 1 TO LEN(a\$)
v = v * 2 + VAL(MID\$(a\$, i, 1))
NEXT
used(v) = used(v) + 1: bsave\$(v) = a\$
IF used(v) > 1 THEN PRINT "error": STOP
permute a\$
LOOP UNTIL a\$ = h\$
PRINT
FOR i = 2 TO 512
IF used(i) = used(i - 1) AND used(i) = 1 THEN
tot = tot + 1
PRINT i - 1, bsave\$(i - 1), i, bsave\$(i)
END IF
NEXT

PRINT tot

Edited on April 15, 2013, 9:55 pm
 Posted by Charlie on 2013-04-15 16:28:18

 Search: Search body:
Forums (0)