# Find the number of Binary Sequences

Given a number n, find the number of all binary sequences of length 2n such that sum of first n bits is same as sum of last n bits.

Example:
Input:
2
Output:
6

Explanation:
n = 2
We have to find the number of binary sequences of length 2xn = 4 such that sum of first n first bits is same as sum of last n bits.

All binary sequences of length 4:
0000    0001    0010    0011    0100    0101    0110    0111
1000    1001    1010    1011    1100    1101    1110    1111

Of these only following binary sequences of length 4 have same sum of bits for first n and last n bits:
0000    0101    0110    1001    1010    1111

## Algorithm/Insights

Binomial Coefficient: Number of ways in which k elements can be selected from n elements. This is denoted as C(n, k) and is given by-
C(n, k) = n!/((n-k)!*k!)

Number of binary sequences of length n, having no  1s
= 1 = (having all 0 bits)

Number of binary sequences of length n, having one 1
= Number of ways in which we can set 1 bit in n bits
= C(n, 1) = n!/((n-1)!*1!) = n

Number of binary sequences of length n, having two 1s
= C(n, 2) = n!/((n-2)!*2!) = n*(n-1)/2

Hence to generalize,
Number of binary sequences of length n, having k 1s
= C(n, k) = n!/((n-k)!*k!)

Number of sequences of length 2n having k 1s in both first half and second half:
= Number of sequences of length n having k 1s * Number of sequences of length n having k 1s
= C(n, k) * C(n, k)

Therefore, number of sequences of size 2n having same number 1's (and hence same sum of bits) in both first half and second half:
= Sum of number of sequences of length 2n having k 1s in both first half and second half for all k = 0 to n
= 1 + Σ C(n, k) * C(n, k)    for k = 1 to n

## Code Snippet

```
package com.ideserve.questions.saurabh;

/**
* <b>IDeserve <br>
* Find number of binary sequences</b><br>
* Given a number n, find the number of all binary sequences of length 2n
* such that sum of first n bits is same as sum of last n bits.
* Example:
* For n = 3  Output: 20
*
* @author Saurabh
*/
public class CountBinarySequences {

public static int countBinarySequences(int n) {
if(n <= 0) {
return 0;
}
int noOfBinarySequences = 1;
int binomialCoefficient = 1;
for(int i = 1; i <= n; i++) {
binomialCoefficient = binomialCoefficient * (n-i+1)/i;
noOfBinarySequences += binomialCoefficient*binomialCoefficient;
}
return noOfBinarySequences;
}

public static void main(String[] args) {
for(int i = 0; i < 11; i++)
System.out.println("No of binary sequences for n = " + i + " = " + countBinarySequences(i));
}
}
```

## Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)