# Counting

• Dec 13th 2006, 06:36 AM
Bloden
Counting
1.) Suppose we have a string that consists of 0's and 1's, & that it is broken up after every 1 & after every 0. Then, the resulting fragments (note that they are NOT necessarily in order) will be the following:

1-fragments: 0, 001, 01, 01
0-fragments: 0, 10, 0, 10, 10.

a.) How many strings exist with the 1-fragments
b.) (Same as above but with 0-fragments)
c.) Determine ALL strings that have the 1-fragments and the 0-fragments.

2.) Is it possible for a string to be ambigiuous if its broken up in to its 0-fragments and 1-fragments? Give an example if it can be, or else explain why it cannot be.

My work:

For #1a, I said that the answer is 3, and I got it by:

3!/(2!*1!) = 3;

#1b, I said it was 5! = 5*4*3*2*1 = 120

and #1c, which I think I did incorrectly:

001010100,
010010100
010100100

#2...no idea.
• Dec 19th 2006, 07:50 AM
F.A.P
Quote:

Originally Posted by Bloden
1.) Suppose we have a string that consists of 0's and 1's, & that it is broken up after every 1 & after every 0. Then, the resulting fragments (note that they are NOT necessarily in order) will be the following:

1-fragments: 0, 001, 01, 01
0-fragments: 0, 10, 0, 10, 10.

(a) We have four "letters" for the 1-fragments. The zero must be the last value. The number of distinct "words" we can write with these letters is

$\displaystyle \frac{3!}{1!2!} = 3$

(b) We have that only two of the 5 fragments being distinct, appearing 2 and 3 times each.

$\displaystyle \frac{5!}{2!3!} = 10$

(c) We have three strings to evaluate from (a)

00101010 with 0-fragments 0, 0, 10, 10, 10

01001010 with 0-fragments 0, 100, 10, 10

01010010 with 0-fragments 0, 10, 100, 10

Only one, the first string, has the given 1-fragments and the 0-fragments.