Function calculates wrong value

Hello,

the following function computes the number of binary words of length m and certain weight r (number of ones), which do not contain l consecutive zeros:

    if (r==0) 
        if (m<=l-1)
            numberOfStrings = 1;
            return
        else
            numberOfStrings = 0;
            return
        end  

    else

        tmp = 0;
        for j=0:min(m,l-1)
            for s=0:r-1
                bin1=0;
                bin2=0;
                if ((m-j)-1-s*l < r-1)
                    bin1 = 0;
                else
                    bin1 = nchoosek((m-j)-1-s*l,r-1);
                end
                if ((m-j)-1-(1+s)*l < r-1)
                    bin2 = 0;
                else
                    bin2 = nchoosek((m-j)-1-(1+s)*l,r-1);
                end

                tmp = tmp + (-1)^s * nchoosek(r-1,s) * (bin1-bin2);
            end
        end 
        numBin = tmp; 
    end

In the first If-case we consider r=0 (also no ones in the sequences), in the else case we consider weights r >= 1.

I have problems with the case, where no consecutive zeros are allowed in the words (variable l=1). For a certain length m there exists only one possible binary sequence. It is the word with the weight equal to the length (r=m).

For example: m=2 --> possible sequence is 11 (has weight r=2) or for m=8 --> possible sequence is 11111111 (has weight r=8). For all other weights r there don't exists possible sequences (the function should output 0).

Until the word length m = 48 the function seems to work well. With m=48, there exists one word (containing no consecutive zeros) with the weight r=48. For all other weights r it outputs 0.

When I use larger lengths m than 49, the function is not working well anymore. The function outputs the number 1 (for r=49). For all other weights r it should be zero. But if I use r=25, it outputs -2 instead of 0. It gets worser for larger lengths.

Can anyone help me with this problem?

[Adam]

Have you used the debugger to look at what is going on line-by-line? It's by far the best way for a function that you know better than anyone else (assuming you wrote it and if you didn't it is even better as a way to understand someone else's function!)

Answer 1

[Michal]

See ma answer here: link