How many strings of length 13 can be formed from 9 1's, two ('s and two )'s such that the substring () never occurs, and for k=1,2, we see k('s before k)'s?
To find the total number of strings that satisfy the given conditions, we can approach this problem using permutations.
Let's break down the problem into three parts:
1. Decide the positions of the 1's.
2. Arrange the '(' and ')' symbols.
3. Arrange the remaining symbols.
1. For the first part, we need to decide the positions of the 9 1's in the string. Since we have 13 positions in total and need to place 9 1's, we can use combinations formula.
The number of ways to choose 9 positions from 13 is given by:
C(13, 9) = 13! / (9! * (13-9)!) = 13! / (9! * 4!) = 715.
So, we have 715 ways to decide the positions of the 9 1's.
2. For the second part, we need to arrange the '(' and ')' symbols. We are given that the substring "()" should never occur. We can achieve this by counting arrangements of '(' and ')' using catalan numbers.
The number of ways to arrange '(' and ')' is the (2n)th Catalan number, where n is the number of pairs. In our case, n is 2, so the 4th Catalan number is relevant.
Catalan(4) = (2*4)! / ((4+1)! * 4!) = 24! / (5! * 4!) = 24.
Therefore, we have 24 arrangements of '(' and ')' symbols.
3. Finally, we need to arrange the remaining symbols, which are the 9 1's. The remaining 13 - 9 - 2 - 2 = 0 positions are left for the 9 remaining symbols.
Therefore, we have only 1 way to arrange the remaining symbols.
Now we can find the total number of strings by multiplying the results from each part:
Total number of strings = Number of ways to decide the positions of 1's * Number of arrangements of '(' and ')' * Number of ways to arrange the remaining symbols
= 715 * 24 * 1
= 17,160.
So, there are 17,160 strings of length 13 that can be formed satisfying the given conditions.