Thread: Counting

hello

I have a test in a few days.
Could you help me with these two counting problems:

1)
a) what is the number of series (length 19)in which there are 8 0's and 11
1's?
answer: easy C(11,8) the problem is with part b:

b) among the series above, what is the number of series in which in any prefix with length at least 3 the number of 1's is larger than the number of 0's by 3?

well I really dont know how to solve this thing..help would be appreciated.

2) what is the number of length 4 cycles in the complete bipartite graph K(6,6)?

thanks for your help guys

Originally Posted by parallel

1) a) what is the number of series (length 19)in which there are 8 0's and 11 1's?
answer: easy C(11,8) WRONG the answer is C(19,8).

b) among the series above, what is the number of series in which in any prefix with length at least 3 the number of 1's is larger than the number of 0's by 3?
I cannot decipher what that means. What does “any prefix with length at least 3” mean?

Please correct.

of course it's C(19,8)

I'll give you an example:

let's say the prefix is of length 3
so the only combination is: 111 (it's the only one)

let's look at the prefix of length 4: the way I see it ,there is no way to build this kind of prefix,becuase there can't be a combination in which the number of 1's is larger than the number of 0's by 3

for the prefix of length 5 the combinations are:
11110,10111...etc

we need to check each prefix, until we get to the prefix of length 19

is it clear now?