Bit Strings in Discrete Mathematics

---

---

A bit string is a sequence made up of binary digits. They are commonly referred to as bits. These bits can take either of the two values, 0 or 1, which makes them the fundamental building blocks of many computational and theoretical concepts.

In this chapter, we will explore bit strings in discrete mathematics. We will present their properties and go through some examples to understand how they function in counting problems.

What are Bit Strings?

A bit string, simply put, is a sequence of binary digits, i.e., 0s or 1s. For example, 1001, 0, 1111, 101010, etc. Each of these is a bit string.

The length of a bit string is determined by the number of binary digits (bits) it contains. For example, the string "1001" has a length of 4, "0" has a length of 1, "1111" also has a length of 4, and "101010" has a length of 6. These strings can vary in length, but they always consist of just two possible symbols: 0 and 1.

Length and Weight of Bit Strings

Let us understand the idea of lengths and weights associated with bit strings. The length of a bit shows the total number of bits it contains. This is beyond length. There is another property of bit strings which is known as weight. The weight is simple. It is the total number of 1s present in the string. Let us see this with example for a better understanding −

• For the bit string "1001," the weight is 2 because there are two 1s in the string.
• The string "0" has a weight of 0 since there are no 1s.
• The string "1111" has a weight of 4 because all the digits are 1s.

So, the weight provides a count of how many 1s are in the bit string.

Sets of Bit Strings

When we are working on discrete maths we often look at sets of bit strings based on their length and weight. We use specific notations to describe these sets:

• Bⁿ is the set of all bit strings of length n.
• Bⁿ_k is the set of all bit strings of length n that have a weight of k (They contain exactly k 1s).

Example of Bit String Sets

Let us consider the set B³, which includes all the bit strings of length 3. These would be −

• 000
• 001
• 010
• 011
• 100
• 101
• 110
• 111

Now, if we want to find the subset of B³ where the weight is 2 (i.e., B³₂), we only need the strings that have exactly two 1s. This subset would be −

• 011
• 101
• 110

These are the only bit strings in B3 that meet the criteria of having a length of 3 and a weight of 2.

Counting Bit Strings

After knowing these notations, let us see counting mechanisms with bit strings. One of the primary tasks when dealing with bit strings is counting how many bit strings satisfy certain conditions. Like as having a specific length or weight. Let us look at some common counting problems involving bit strings.

Counting Bit Strings of a Given Length

If we want to count how many bit strings have a specific length, say length 5, we can use a simple method. Since each position in the string can either be a 0 or a 1, for a string of length 5, we have two choices (0 or 1) for each of the five positions. By the multiplicative principle, the total number of possible bit strings of length 5 is −

$$\mathrm{2 \:\times\: 2 \:\times\: 2 \:\times\: 2 \:\times\: 2 \:=\: 25 \:=\: 32}$$

So, there are 32 different bit strings of length 5.

Counting Bit Strings of a Given Weight

Let us now consider a slightly more challenging problem: counting bit strings of a given length and weight. For example, how many bit strings of length 5 have a weight of 3?

In other words, how many 5-bit strings contain exactly three 1s?

To get the answer, we can think about it in parts. A bit string of length 5 with a weight of 3 must have exactly three 1s and two 0s. There are two cases to consider:

• The bit string starts with a 0.
• The bit string starts with a 1.

In the first case (the bit string starts with a 0), we need to select three 1s from the remaining four positions. This is equivalent to finding all 4-bit strings with a weight of 3.

In the second case (the bit string starts with a 1), we need to select two 1s from the remaining four bits, so we look at 4-bit strings with a weight of 2.

Solving this problem is easy. We can sum up the results using a recurrence relation −

$$\mathrm{|B^{5}_3| \:=\: |B^{4}_2| \:+\: |B^{4}_3|}$$

Bit Strings and Subsets

Here interestingly, the bit strings are also related to subsets of sets. Now consider a set A with five elements: {1, 2, 3, 4, 5}. Each element of this set can either be in a subset or not. This is very much like deciding whether to put a 0 or 1 in each position of a bit string. We can represent each subset of A as a bit string of length 5. For example −

• The bit string "11001" represents the subset {1, 2, 5}.
• The bit string "00101" represents the subset {3, 5}.

In this way, the number of bit strings of a particular length and weight corresponds to the number of subsets with a particular number of elements.

For example, if we consider 5-bit strings with weight 3 is the same as counting how many subsets of {1, 2, 3, 4, 5} have exactly three elements. These two problems are identical in terms of their solutions.

Recurrence Relations and Counting

As we saw earlier, counting bit strings of a given length and weight sometimes can be explainable by the problem into smaller parts. This leads to the concept of a recurrence relation. A recurrence relation expresses the count of bit strings of a certain length and weight in terms of bit strings of shorter lengths and different weights.

For example, the number of bit strings of length 5 with a weight of 3 can be expressed as −

$$\mathrm{|B^{5}_3| \:=\: |B^{4}_2| \:+\: |B^{4}_3|}$$

This relation shows how we can count more complex bit strings.

Conclusion

In this chapter, we explained what bit strings are and how they are useful in discrete mathematics. We also covered the concepts of bit string length and weight. We understood how to define sets of bit strings, and explored how to count bit strings of various lengths and weights.

We also discussed the connection between bit strings and subsets of sets, showing how similar counting problems arise in different contexts. Finally, we highlighted the concept of recurrence relations and how they help in breaking down more complicated counting problems into manageable ones.