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 000010110
000011001 000011010 000011100 000100011 000100101 000100110 000101001 000101010
000101100 000110001 000110010 000110100 000111000 001000011 001000101 001000110
001001001 001001010 001001100 001010001 001010010 001010100 001011000 001100001
001100010 001100100 001101000 001110000 010000011 010000101 010000110 010001001
010001010 010001100 010010001 010010010 010010100 010011000 010100001 010100010
010100100 010101000 010110000 011000001 011000010 011000100 011001000 011010000
011100000 100000011 100000101 100000110 100001001 100001010 100001100 100010001
100010010 100010100 100011000 100100001 100100010 100100100 100101000 100110000
101000001 101000010 101000100 101001000 101010000 101100000 110000001 110000010
110000100 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 001111110
010011111 010101111 010110111 010111011 010111101 010111110 011001111 011010111
011011011 011011101 011011110 011100111 011101011 011101101 011101110 011110011
011110101 011110110 011111001 011111010 011111100 100011111 100101111 100110111
100111011 100111101 100111110 101001111 101010111 101011011 101011101 101011110
101100111 101101011 101101101 101101110 101110011 101110101 101110110 101111001
101111010 101111100 110001111 110010111 110011011 110011101 110011110 110100111
110101011 110101101 110101110 110110011 110110101 110110110 110111001 110111010
110111100 111000111 111001011 111001101 111001110 111010011 111010101 111010110
111011001 111011010 111011100 111100011 111100101 111100110 111101001 111101010
111101100 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 |
solution
