Find the number of Binary Sequences

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>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * 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)