[Math] How many bit strings of length 8 have a weight of 5 start with 101 OR end with 11.

combinatoricsdiscrete mathematics

I'm very close to solving this problem but finding the final answer is proving problematic.

A: 101x xxxx = 32 strings starting with 101
B: xxxx xx11 = 64 strings ending with 11
C: 101x xx11 = 8 strings with both of these.

The number of strings with weight five is equal to 56.

It is also important to note the number of strings starting with 101 with weight five is equal to 10
and the number of strings ending in 11 with weight five is equal to 20.

Therefore I thought the answer would've been 22 i.e. sum of 10 + 20 minus the strings common to both given this is an or problem.

Best Answer

Yes, you can use inclusion-exclusion, but the intersection should include the weight five condition. The correct count is: $$\binom{5}{3}+\binom{6}{3}-\binom{3}{1}=10+20-3=27$$

Related Solutions

Combinatorics – How Many Bit Strings of Length 8 Start with 00 or End with 1?

Yes, you are correct about each separate case, but to find the number of bit strings of length $8$ that either start with two zeros or end in a one (or both), we cannot simply *add* the two counts and say "we're done." We can use the sum rule, but with modifications:

If we add the counts $2^6 + 2^7$, we need to also account for having double counted those bit strings which both start with two zeros and end in a one: Subtract that number of strings from the sum, and you'll have your answer.

Clarification: The number of bit strings of length 8 of the form 0 0 x x x x x 1 will have been counted $(1)$ in the first total of all strings of the form 0 0 x x x x x x, and $(2)$ it will have been counted in the second total of all strings of the form x x x x x x x 1. So we need to subtract the number of strings of the form 0 0 x x x x x 1 from the combination of the first count and second count, so that they are only counted once.

So, we count the number of bit strings of the form: 0 0 x x x x x 1,

and just as you computed the first two counts, we see that there are $2^5$ such strings which have been counted twice, so we will subtract that from the sum of the first two counts.

Total number of bit strings that start with two zeros $(2^6)$ or end in a one $(2^7)$ or both ($2^5$):

$$ 2^6 + 2^7 - 2^5$$

[Math] Using generating functions to answer how many bit strings of length N have no 000

First of all your approach is fine and the generating function $G(z)$ is correct. As verification we consider a slightly different approach in the same spirit as it can be found in chapter $5$ in Analysis of Algorithms. Then we look at the coefficients of $G(z)$

Generating function $G(z)$:

We can find in section Bitstrings of chapter $5$ a representation of all bitstrings as \begin{align*} B=\varepsilon+(Z_0+Z_1)\times B \end{align*} which means that each bitstring is either empty or a string starting with $0$ or $1$ followed by a bitstring. A combinatorial construction is \begin{align*} B=SEQ(Z_0+Z_1) \end{align*} meaning a bitstring is a sequence of zero or more occurrences of $0$ or $1$ respectively.

We can characterise general bitstrings also by grouping them into blocks starting with $1$. A bitstring consists of zero or more blocks starting with $1$ and followed by zero or more $0$'s. The bitstring may be preceded by zero or more $0$'s. A combinatorial representation is \begin{align*} B=SEQ(Z_0)SEQ(Z_1\,SEQ(Z_0))\tag{1} \end{align*} The generating function describing the number of bitstrings according to (1) is \begin{align*} B(z)=\frac{1}{1-z}\frac{1}{1-z\frac{1}{1-z}}=\frac{1}{1-2z}=\sum_{n\geq 0}(2z)^n \end{align*} showing us, that we have $2^n$ different bitstrings of length $n$. We can now derive from (1) a representation for all strings which do not contain the substring $000$.

We describe the bitstrings not containing a substring $000$ as a general bitstring with the restriction that each group of $0$'s has maximum length $2$. This implies that we have to exchange in (1) \begin{align*} SEQ(Z_0)=\varepsilon+Z_0+Z_0Z_0+\cdots\qquad\text{with}\qquad \varepsilon+Z_0+Z_0Z_0 \end{align*} We obtain \begin{align*} G=(\varepsilon+Z_0+Z_0Z_0)SEQ(Z_1\,(\varepsilon+Z_0+Z_0Z_0))\tag{2} \end{align*} From (2) we obtain the generating function $G(z)$ as \begin{align*} G(z)&=(1+z+z^2)\frac{1}{1-z(1+z+z^2)}\\ &=\frac{1+z+z^2}{1-z-z^2-z^3}\\ &=1+2z+4z^2+7z^4+13z^5+\cdots \end{align*} which is the same as yours.

$$ $$

Coefficients of $G(z)$:

It's convenient to use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ in a generating series.

In this case it is not necessary to derive the coefficients $[z^n]$ in $G(z)$ by finding the roots of the equation $1-z-z^2-z^3$. We instead use a geometric series representation of $G(z)$. Since $1+z+z^2=\frac{1-z^3}{1-z}$ we obtain \begin{align*} G(z)&=\frac{1+z+z^2}{1-z-z^2-z^3}\\ &=\frac{1+z+z^2}{1-z(1+z+z^2)}\\ &=\frac{\frac{1-z^3}{1-z}}{1-z\frac{1-z^3}{1-z}}\\ &=\frac{1-z^3}{1-2z+z^4}\\ &=\frac{1-z^3}{1-(2z-z^4)}\\ &=(1-z^3)\sum_{k\geq 0}(2z-z^4)^k\\ &=(1-z^3)\sum_{k\geq 0}z^k(2-z^3)^k\\ &=(1-z^3)\sum_{k\geq 0}z^k\sum_{l=0}^k\binom{k}{l}(-x^3)^l2^{k-l}\tag{3} \end{align*}

We calculate from (3) the coefficient of $z^n$ of $G(z)$ as

\begin{align*} [z^n]G(z)&=[z^n](1-z^3)\sum_{k\geq 0}z^k\sum_{l=0}^k\binom{k}{l}(-z^3)^l2^{k-l}\\ &=\left([z^n]-[z^{n-3}]\right)\sum_{k\geq 0}z^k\sum_{l=0}^k\binom{k}{l}(-z^3)^l2^{k-l}\tag{4}\\ &=\sum_{k\geq 0}\left([z^{n-k}]-[z^{n-3-k}]\right)\sum_{l=0}^k\binom{k}{l}(-z^3)^l2^{k-l}\\ &=\sum_{{k= 0}\atop{n\equiv k(\text{mod} 3)}}^n\binom{k}{\frac{n-k}{3}}(-z^3)^\frac{n-k}{3}2^{k-\frac{n-k}{3}}\tag{5}\\ &\qquad-\sum_{{k= 0}\atop{n\equiv k(\text{mod} 3)}}^{n}\binom{k}{\frac{n-k}{3}-1}(-1)^{\frac{n-k}{3}-1}2^{k-\frac{n-k}{3}+1}\\ &=\sum_{{k= 0}\atop{n\equiv k(\text{mod} 3)}}^n\left(\binom{k}{\frac{n-k}{3}}+2\binom{k}{\frac{n-k}{3}-1}\right) (-1)^\frac{n-k}{3}2^{k-\frac{n-k}{3}}\tag{6} \end{align*}

Comment:

In (4) we use the linearity of the coefficient of operator and the rule $[z^{n+k}]=[z^n]x^{-k}$
In (5) we select the coefficient $l=n-k$ which are congruent $0$ modulo $3$ due to the third power of $z$. We also set the upper limit of the sum to $n$ since we only need coefficients up to $z^n$.

With the formula in (6) we can explicitly calculate the coefficients of $G(z)$.

Best Answer

Related Solutions

Combinatorics – How Many Bit Strings of Length 8 Start with 00 or End with 1?

[Math] Using generating functions to answer how many bit strings of length N have no 000

Related Question