How many bit strings of length 15 have:

Question

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.

Answer 1

Isn't this just binomial coefficient stuff? Consider an length-$n$ bit string, and suppose it starts out all zeroes, and you want to put exactly $k\le n$ ones in it. Then there are $n$ positions in which you can put the first one, $n-1$ remaining positions for the second one, etc. So in the end there are $n\times(n-1)\times\ldots\times(n-k+1)=\frac{n!}{(n-k)!}$ ways. But that includes "duplicates" when you just change the order. That is, e.g., place the first $1$ in position $5$ and the second $1$ in position $7$, or vice versa. And that's just the number of permutations of $k$ things, or $k!$. So divide by that to get the ususal binomial coefficient $\frac{n!}{k!(n-k)!}=\left(n\atop k\right)$.

So that would be for >>exactly<< $k$ ones in a length-$n$ bit string (or conversely $k$ zeroes, by similar reasoning). For, say $k$-or-less, just add up all the corresponding binomial coefficients $\displaystyle\sum^k_{i=0}\left(n\atop i\right)$. And note that $\displaystyle\sum^n_{i=0}\left(n\atop i\right)=2^n$, exactly the number of different binary strings of length $n$, as expected.

Answer 2

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.

Answer 3

Your result is correct. The first thing that came to my mind was that a bitstring of length $15$ with $5$ zeros is the same as the bitstrings having a hamming weight of $10$. I wrote a short program that bruteforces all $2^{15}$ bitstrings, a counter and outputs the valid strings where hamming weight $=10$:

#define HammingWeight(a) __popcnt(a)
std::bitset<15> bin15;

int countInstances = 0, leastTen = 0, moreOnes = 0;
FILE *fp = fopen("bitstrings.txt", "wb");
fprintf(fp, "\n");

for (int i = 0; i < 32768; i++)
{
    if (HammingWeight(i) == 10)
    {
        bin15 = i;
        fprintf(fp, "%s\n", bin15.to_string().c_str());
        countInstances++;
    }
    if (HammingWeight(i) >= 10) leastTen++;
    if (HammingWeight(i) >= (15 - HammingWeight(i))) moreOnes++;

}
fprintf(fp, "\nNumber of instances = %i\n", countInstances);
fprintf(fp, "Least ten ones = %i\n", leastTen);
fprintf(fp, "More ones than zeros = %i\n", moreOnes);
fclose(fp);

Number of instances = $3003$

Least ten ones = $4944$

More ones than zeros = $16384$

Answer 4

For Question 3: There are $2^{15}$ bitstrings of length $15$. None of them has equally many zeros and ones. By symmetry exactly half of them, i.e., $16\,384$, have more ones than zeros.