10
$\begingroup$

The Problem

Suppose I have a bit string of length $n$ consisting of all zeros. I want to flip some of the zeros to ones, but I am only able to flip at most $k$ bits (i.e., I can flip any number of bits I want, as long as it is not more than $k$). How many ways can I do this?

What I Tried

I believe this is analogous to finding the number of ways to choose at most $k$ things out of a group of $n$, which it seems could be expressed as

\begin{align*} \sum_{r=0}^k {n \choose r} &= {n \choose 0} + {n \choose 1} + \dots + {n \choose k} \\ &= \frac{n!}{0!n!} + \frac{n!}{1!(n-1)!} + \frac{n!}{2!(n-2)!} + \dots + \frac{n!}{k!(n-k)!} \\ \end{align*}

but this is still not very neat, and I don't see where to go from here algebraically. I also see that this is also the same as adding a partial row of Pascal's triangle, but that didn't get me much further. I tried searching for various things both on this site and google involving various combinations of the terms n choose k, at most, summing a row of pascal's triangle, etc., which did not give many applicable results.

The Question

Assuming I translated the problem correctly, is there a cleaner solution than taking the sum over the different choices of $k$? If one exists, I would love to see a combinatorial explanation for it, but an algebraic one would still be sufficient.

$\endgroup$
  • 4
    $\begingroup$ The expression is correct. There is no nice closed form. $\endgroup$ – André Nicolas Oct 4 '13 at 5:07
  • $\begingroup$ what's that "begin{align*}" stuff you have in your $\LaTeX$? $\endgroup$ – Shine On You Crazy Diamond Oct 4 '13 at 5:11
  • $\begingroup$ @EnjoysMath It makes the equations line up at the equals sign. See here for more info. The * is so that the equations don't get numbered. It might not be necessary with MathJax, I'm not sure how it handles environments (for all I know, there's an easier way of lining up equations, too). $\endgroup$ – Apis Utilis Oct 4 '13 at 5:20
  • $\begingroup$ @AndréNicolas If $\displaystyle{\large k > n/2}$ use $\large\displaystyle{2^{n} - \sum_{r = k + 1}{n \choose r}}$ as a "correct" one. $\endgroup$ – Felix Marin Oct 4 '13 at 6:26
  • 1
    $\begingroup$ There is a more detailed answer here math.stackexchange.com/questions/180341/… $\endgroup$ – DanielV Oct 4 '13 at 7:04
1
$\begingroup$

For completeness and convenience I have taken the information in the comments and put it here as an answer. Thus, my answer is essentially taken from the accepted answer to this very similar question.

#

Yes, there are various closed form expressions for this summation. However, they are all relatively complex and so in practice using them to calculate the summation may actually me more complicated than just calculating the summation term by term!

If $S= \sum_{k\le K}{n\choose k} $, then in terms of hypergeometric ${}_2F_1 (a,b,c,d)$ functions, $$ S = 2^n - 1 - \binom{n}{1+K} \; {}_2F_1 (1, 1+K-n, 2+K,-1) $$

Denote the fractional part of $z$ as $\lfloor z \rfloor = z - [z]$.

Now , if for any positive integer $j>1$, we let $x = j^{-n}$, then there are the two following intriguing expressions (which are a result of generating functions):

$$ S =\left\lfloor\frac{(j^{K+1}\cdot(1+x))^{n}}{j^{n}-1}-j^{n}\cdot\left\lfloor\frac{(j^{K}\cdot(1+x))^{n}}{j^{n}-1} \right\rfloor\right\rfloor$$

And, $$S=\left\lfloor\frac{(1+x)^n}{x^{K}(1-x)}\right\rfloor \; (\mod 4^n).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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