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
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.
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.
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.