Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have $N$ binary strings of length $L$. If a string has more than one $1$ bit, these bits must be adjacent to one-another. For example, for a length $L = 4$ string, the possible string states (of which there are $11$) would be: $\{"0000", "0001", "0010", "0100", "1000","0011","0110","1100","0111","1110","1111"\}$.

What function, $f(N,L,M,B)$, gives the number of "system" states where there are exactly $M \leq N$ strings with any $1$ bits, and the count of $1$ bits in all of the strings is $B$? What if we drop the constraint that $1$ bits need to be adjacent?

share|improve this question
    
To make sure that I understand: is $B$ the total number of $1$ bits in all $N$ strings? And are there $N-M$ copies of the $L$-bit zero string? –  Brian M. Scott Jan 2 '13 at 19:01
    
@Brian M. Scott Yes and yes. $B$ is the total number of $1$ bits in all of the $N$ strings. And there are $N-M$ strings with only $0$ bits. –  Egami Jan 2 '13 at 19:09
add comment

2 Answers

up vote 0 down vote accepted

There are $\binom{N}{M}$ ways to select a subset of $M$ strings to populate. After that, we can attach the generating function $\sum_{n=1}^L (L-n+1) x^n = \frac{x}{(1-x)^2} (L - (L+1)x + x^{L+1})$ to each of the $M$ chosen strings, where the power of $x$ encodes the number of bits used in that string. The function you are looking for is then $\binom{N}{M}$ times the coefficient of $x^{B-M}$ in the Taylor series for $$\left[\frac{(L - (L+1)x + x^{L+1})}{(1-x)^2} \right]^M.$$ I don't see a good way to extract a general explicit formula, but for small fixed values of $L$ or $M$ it should be possible.

share|improve this answer
1  
For L=4 and M=4, using Series[((L - (L + 1) x + x^(L + 1))/(1 - x)^2)^M, {x, 0, 12}] in Mathematica, I get: 256 + 768 x + 1376 x^2 + 1840 x^3 + 1905 x^4 + 1608 x^5 + 1124 x^6 + 648 x^7 + 310 x^8 + 120 x^9 + 36 x^10 + 8 x^11 + x^12 + O[x]^13 –  Egami Jan 2 '13 at 22:08
    
How do I interpret the coefficient 256 for x^0, for example? I don't quite understand how this could make sense? –  Egami Jan 2 '13 at 22:11
    
@Egami The coefficient $x^0$ would be the number of ways to have $B=M=4$. In this case each of the 4 chosen strings can only get a single $1$, but there are $4$ places to put it. Therefore there are $4^4 = 256$ combinations. –  Erick Wong Jan 3 '13 at 0:04
    
Playing around in Mathematica and Maple, it looks like, for fixed $L$ or $M$, that you can get closed formed solutions for the coefficients, but they're a mess. –  Egami Jan 3 '13 at 3:32
add comment

For a string of length $L$, you can have any number of $1$ bits from $0$ to $L$. Given that there are $n \ \ 1$ bits, there are $L-n+1$ valid strings, as you can have from $0$ to $L-n \ \ 0$ bits at the start and the rest must be at the end. The one failure of this is having $0 \ \ 1$ bit, where there is only one string instead of $L+1$. So $$f(n,L)=\begin {cases}1 & n=0 \\ L-n+1 & n \gt 0 \end {cases}$$

If you drop the requirement that the $1$'s be adjacent, you just select the positions of the $1$ bits, so $f(n,L)={L \choose n}$

Added: The first step for what you want is to look for the number of partitions of $B$ things into parts of at most $N$. If order matters, if a set of strings $(0011, 0001,1111)$ is different from $(1111,0001,0011)$ you want compositions instead. Given the partition or composition, each element corresponds to a single string. For each element in it, you have the $f(n,L)$ above ways to select the bit string, so you multiply them together to see the number of possibilities for that partition. Unfortunately, for partitions you will overcount in case there are two strings with the same number of bits on because swapping them gets you back to the same place.

share|improve this answer
    
Your answer makes perfect sense, though it wasn't exactly what I was asking? –  Egami Jan 2 '13 at 19:02
    
$N$ is the number of binary strings, and with the constraints, I'm trying to count the total number of ways we can have both exactly $M \leq N$ strings with no $1$ bits, and also exactly $B$ total $1$ bits. –  Egami Jan 2 '13 at 19:04
    
We can write the number of states for any given string as just: $(\sum_{i=1}^{L} i)+1$. –  Egami Jan 2 '13 at 19:05
    
@Egami: I didn't understand fully what you were asking and hoped it would help. The number of strings with no $1$ bits is $1$ of each length. My $n$ may be your $B$, but I am not sure. Your last comment is correct, and can be simplified to $1+\frac 12L(L+1)$ –  Ross Millikan Jan 2 '13 at 20:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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