# Number of bit string interpretations correct?

Suppose you are given a bit string $$B[1 ... n]$$. Now, suppose that some bits are just padding bits conveying no information, the rest of the bits may be permuted and some meaningful (that is, non-padding) bits should be inverted from $$0$$ to $$1$$ and vice versa.

According to my intuition, the total number of interpretations is $$I(B) = \sum_{i = 0}^n \binom{n}{i} i! 2^i.$$ The idea is that we choose all bit combinations, one by one. Then, we permute each combination. Finally, we multiply by $$2^i$$ in order to take the bit inversions into account.

Is this formula correct?

Example

$$p$$ as padding, meaningless bit. $$b$$ as non-padding, meaningful bit. $$\bar{b}$$ as meaningful, inverted bit.

1. $$pp$$
2. $$pb$$
3. $$p\bar{b}$$
4. $$bp$$
5. $$\bar{b}p$$
6. $$bb^\prime$$
7. $$b\bar{b^\prime}$$
8. $$\bar{b}b^\prime$$
9. $$\bar{b}\bar{b^\prime}$$
10. $$b^\prime b$$
11. $$b^\prime \bar{b}$$
12. $$\bar{b^\prime}b$$
13. $$\bar{b^\prime}\bar{b}$$

Note that $$I(B[1 … 2]) = 13$$.

• What do you call an interpretation ? And why should the bits be inverted ?? Can you show a small example such as 2.2 or 3.2 ?
– user16034
Oct 12, 2022 at 7:16
• to me it looks like you are ultimately counting all possible n-bit strings, I may be wrong. Your idea resembles hamming codes. Oct 12, 2022 at 7:25
• @YvesDaoust Added an example $n = 2$. Oct 12, 2022 at 8:01

When there are $$i$$ significant bits, you can form $$2^i$$ arrangements that can be permuted in $$i!$$ ways, and interspersed each with the remaining $$n-i$$ bits. Hence in total
$$\sum_{i=0}^n2^ii!\binom ni.$$
E.g., for $$n=2$$,
$$1\cdot1\cdot1+2\cdot1\cdot2+4\cdot2\cdot1=13.$$