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?


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

  • $\begingroup$ 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 ? $\endgroup$
    – user16034
    Commented Oct 12, 2022 at 7:16
  • $\begingroup$ to me it looks like you are ultimately counting all possible n-bit strings, I may be wrong. Your idea resembles hamming codes. $\endgroup$
    – Rinkesh P
    Commented Oct 12, 2022 at 7:25
  • $\begingroup$ @YvesDaoust Added an example $n = 2$. $\endgroup$
    – coderodde
    Commented Oct 12, 2022 at 8:01

1 Answer 1


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$,


This just confirms your findings.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.