Problem solving with programming: Number of ways of arranging 0, 1

Problem solving with programming: Number of ways of arranging 0, 1

Given 'N' zeros and 'M' ones, In how many ways can we arrange them to form a string of length (N+M)?

For example if we have 2 zeros and 2 ones, we can arrange them in 6 ways

0011, 1100, 0101, 1010, 1001, 0110

If there are N symbols to arrange, The number of ways to arrange them in a sequence is called a permutation problem. This number is simply N! (N factorial).

We have (N+M) symbols in total and N symbols are one type and M symbols are another type, So the number of permutations become (N+M)!/ N!*M!

Another way to look at the problem is using combinations. We have (N+M) places either

• We have to choose N spaces to fill zeros, in the remaining places, we fill one
• Or We have to choose M spaces to fill ones, in the remaining places, we fill zero

The number of ways to choose R objects from N objects is called a combination problem. This is represented by C(N,R) = N!/(N-R)!*R!

So for our problem there are (N+M) symbols and we need to either choose N zeros or M ones. So it becomes C(N+M,N) or C(N+M,M)

Both reduce to (N+M)!/N!*M!.

We have another formula to calculate C(N,R) using recursive definition.

C(N, R) = C(N-1, R-1) + C(N-1, R)

You can easily understand this by using Pascal triangle.

   public static void initTable()


    {


        for( int n = 1; n < 2000; n++ )


        {


            for(int r = 0; r <= 1000; r++ )


            {


                perm_table[n][r] = permutations(n,r);


            }


        }


    }


    public static long permutations(int n, int r)


    {


        long MOD = 1000000007;


        if( r == 0)


            return 1;


        else if( r == 1)


            return n;


        return (perm_table[n-1][r-1] + perm_table[n-1][r])%MOD;


 


    }

Read full article from Problem solving with programming: Number of ways of arranging 0, 1