6
$\begingroup$

I thought there were n-1 places between the first and last digit.
In these places I hypothesized there are switches that change (from 0->1 or 1->0)

For {First,Last}={00,01,10,11} -> 4 ways

I ask an answer for the first case mostly (I think the rest will be similar)

Since there are m patterns of 01 how many switches are there?
And how many ways are there to pick out of n-1?

$\endgroup$
2
  • $\begingroup$ I deleted my answer because I don't think it is helpful for this problem. Sorry for the confusion. $\endgroup$ Oct 20, 2014 at 22:21
  • $\begingroup$ @EricStucky its ok but anyway thank you for your trouble $\endgroup$
    – solid.py
    Oct 20, 2014 at 22:22

2 Answers 2

5
$\begingroup$

Method I

$\require{enclose} \newcommand{\bitP}[1]{\enclose{box}{#1}} $Consider following encoding of $n$-bit binary strings $$\bitP{a_0 a_1 a_2 \ldots a_{n-1}} \mapsto \bitP{b_0 b_1 b_2\ldots b_{n-1}}$$ defined by $$b_k = \begin{cases} a_k, &k = 0\\ a_k \oplus a_{k-1}, & 1 \le k \le n-1\end{cases}$$

where $\oplus$ stands for logical exclusive or between two bits.

In order for $\bitP{a_0 a_1 a_2 \ldots a_{n-1}}$ to have exactly $m$ copies of $\bitP{01}$, there are four possibilities.
Let $N_m$ be the numbers of $\bitP{1}$ among the $n-1$-bit binary string $\bitP{b_1b_2\ldots b_{n-1}}$, the four possibilities can be summarized by following table.

$$\begin{array}{cl:l} b_0 & N_m & \text{e.g.} (n=6, m=2) \\ \hline 0 & 2m - 1 & \bitP{010111} \mapsto \bitP{011100}\\ 0 & 2m & \bitP{010100} \mapsto \bitP{011110}\\ 1 & 2m & \bitP{101011} \mapsto \bitP{111110}\\ 1 & 2m + 1 & \bitP{101010} \mapsto \bitP{111111}\\ \end{array}$$

Base on this, we find the number of $n$-bit binary strings with exactly $m$ copies of $\bitP{01}$ is give by $$ \binom{n-1}{2m-1} + \binom{n-1}{2m} + \binom{n-1}{2m} + \binom{n-1}{2m+1}\\ = \binom{n}{2m} + \binom{n}{2m+1} = \binom{n+1}{2m+1} $$

Method II - generating function.

Instead of looking at the collection of $n$-bit binary strings and ask how many of them has exactly $m$ copies of $\bitP{01}$. We look at the collection of binary strings with exactly $m$ copies of $\bitP{01}$ and ask how many of them has length $n$.

The collection of binary strings with exactly $m$ copies of $\bitP{01}$ can be described by following regular expression

$$1\verb/*/\;(\;0\verb/+/\;1\verb/+/\;)\{m\}\;0\verb/*/\tag{*1}$$

where

  • $X\verb/*/\;$ means the pattern $X$ is repeated zero to any number of times.
  • $X\verb/+/\;$ means the pattern $X$ is repeated one to any number of times.
  • $X\{m\}\;$ means the pattern $X$ is repeated exactly $m$ times.

To count the number of bit strings with length $n$, we assign to each piece in the regular expression $(*1)$ by a power series in some indeterminate $t$.

$$\begin{array}{ccl} 1\verb/*/\; & \leftrightarrow & \frac{1}{1-t} = 1 + t + t^2 + \ldots\\ 0\verb/+/\; & \leftrightarrow & \frac{t}{1-t} = t + t^2 + \ldots\\ 1\verb/+/\; & \leftrightarrow & \frac{t}{1-t} = t + t^2 + \ldots\\ 0\verb/*/\; & \leftrightarrow & \frac{1}{1-t} = 1 + t + t^2 + \ldots \end{array}$$ In general, if a pattern allows a bit to repeat $r$ times, we attach a term $t^r$ to it.

Combine these, we obtain following generating function corresponds to $(*1)$.

$$\frac{1}{1-t}\left(\frac{t}{1-t} \frac{t}{1-t}\right)^m\frac{1}{1-t} = \frac{t^{2m}}{(1-t)^{2m+2}} = \sum_{k=0}^\infty \binom{2m+1+k}{k} t^{k+2m} \tag{*2}$$

If one expand the RHS as a power series of $t$, one will find the terms with power $t^n$ are in an one to one correspondence with those $n$-bit binary strings matching the regular expression $(*1)$. This means the number we want is the coefficient of $t^n$ in $(*2)$. i.e.

$$\binom{2m+1+(n-2m)}{n-2m} = \binom{n+1}{n-2m} = \binom{n+1}{2m+1}$$

which matches what we get by another method.

$\endgroup$
1
  • $\begingroup$ Hi i like your answer alot @achille hui especially in generating could u kindly send me references on it thanks $\endgroup$
    – Will
    Jun 27, 2023 at 13:28
1
$\begingroup$

Your idea is good. One case is that the string starts with $0$ and ends with $0$; in this case it'll have to go up $m$ times and down $m$ times, starting with an up, then alternating between down and up, ending with a down. So you just get to (have to) choose the $2m$ switching points, and there are $\binom{n-1}{2m}$ ways to do that. I leave the other cases for you, as you requested.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .