[Math] How many bit strings of length 15 have:

bit-stringscombinatoricsdiscrete mathematicspermutations

If your are not sure what a bit string is here are some examples for this question:
000100000000000

111000000000000

011000000000000

101000000000000

001000000000000

110000000000000

010000000000000

100000000000000

000000000000000

Basically, it's $15$ characters long and each string is a permutation of the set $\{1, 0\}$.

How many bit strings of length $15$ have:

question 1: exactly five 0s?

I came up with this:

$\frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11}{3} = 120,120$

My reasoning behind this is if you were to create a $15$ length bit string from scratch, at first you have $15$ places to place a 0. Then since you have one 0 in the string, for your next 0 you have $14$ places to place another 0 and so on. Then you divide by the number of times you can fit $5$ 0's in the string.

I wrote a program to calculate all possible permutations and count the occurrences of how many bit strings have five o's and it came up with:

3003

so I am not sure if my math \ logic is wrong or my program is wrong.

Edit: Based on the comments by Lord Shark the Unknown, I came up with
$$\frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11}{5!} = 3003$$

Question 2: at least ten 1's?

Program came up with: 4944

Question 3 more 1's than 0's?

program came up with: 16384




   import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;

public class MyClass {
    static ArrayList<String> arrr = new ArrayList<String>();


     static void convert_To_Len_th_base(int n, int arr[],  
                                        int len, int L) 
     { 
         String hold = "";
         // Sequence is of length L 
         for (int i = 0; i < L; i++)  
         { 
             // Print the ith element 
             // of sequence 
             hold += arr[n % len] +"";
             n /= len; 
         } 
         //System.out.println(hold);
         arrr.add(hold);
     } 

     static void print(int arr[], int len, int L) 
     { 
         // There can be (len)^l 
         // permutations 
         for (int i = 0;  
                  i < (int)Math.pow(len, L); i++)  
         { 
             // Convert i to len th base 
             convert_To_Len_th_base(i, arr, len, L); 
         } 
     } 




        // Driver Code 
        public static void main(String[] args) 
        { 
            int arr[] = {1, 0}; 
            int len = arr.length; 
            int L = 15; 
            // function call 
            print(arr, len, L); 
           int counter1 = 0;
            int counter2 = 0;
            int counter3 = 0;


            for (int i = 0; i < arrr.size(); i++) {
                 if(arrr.get(i).length() - arrr.get(i).replaceAll("0", "").length() == 5) {
                     counter1++;
                 }

                 if(arrr.get(i).length() - arrr.get(i).replaceAll("1", "").length() >= 10) {
                     counter2++;
                 }

                 if(arrr.get(i).length() - arrr.get(i).replaceAll("1", "").length() < arrr.get(i).length() - arrr.get(i).replaceAll("0", "").length()) {
                     counter3++;
                 }
            }
            System.out.println("answer 1: " + counter1);
            System.out.println("answer 2: " + counter2);
            System.out.println("answer 3: " + counter3);
     }
}

paste this into: https://www.jdoodle.com/online-java-compiler/

Any insight will be much appreciated.

Best Answer

How many bit strings of length $15$ have exactly five 0's?

Your answer is correct.

Choose five of the $15$ positions in the bit string for the zeros, then fill each of the remaining ten positions in the bit string with ones. This can be done in $$\binom{15}{5} = \frac{15!}{5!10!} = \frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10!}{5!10!} = \frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11}{5!} = 3003$$ ways.

How many bit strings of length $15$ have at least ten 1's?

A bit string of length $15$ that has at least ten 1's must have exactly ten 1's or exactly eleven 1's or exactly twelve 1's or exactly thirteen 1's or exactly fourteen 1's or exactly fifteen 1's. In each of these six cases, choose the positions for the 1's, then fill each of the remaining positions with zeros. Add up.

$$\binom{15}{10} + \binom{15}{11} + \binom{15}{12} + \binom{15}{13} + \binom{15}{14} + \binom{15}{15} = 3003 + 1365 + 455 + 105 + 15 + 1 = 4944$$

The third question is similar to the second one. Just note that if there are more ones than zeros, then there must be at least eight ones.

Related Question