from itertools import permutations import sys ''' Calculates the number of left-right-balanced permutations of [1, ..., n]. A permutation of [1, .., n] is left-right-balanced if the sum of the left half is equal to the sum of the right half. For example, [1, 4, 2, 3] is a left-right-balanced permutation of [1, 2, 3, 4] because sum( [1, 4] ) is equal to sum( [2, 3] ). And [1, 5, 3, 2, 4] is a left-right-balanced permutation of [1, 2, 3, 4, 5] because sum( [1, 5] ) is equal to sum( [2, 4] ). Author: Robert C. Lyons ''' def is_left_right_balanced_permutation( permutation ): """Return True if the permutation is left-right-balanced; otherwise, return False. >>> is_left_right_balanced_permutation( (1, 4, 2, 3) ) True >>> is_left_right_balanced_permutation( (1, 2, 5, 4, 3) ) False """ permutation_as_list = list( permutation ) length = len( permutation_as_list ) half_length = length / 2 left_half = permutation_as_list[0:half_length] if ( length % 2 == 0 ): start_index_of_right_half = half_length else: start_index_of_right_half = half_length + 1 right_half = permutation_as_list[start_index_of_right_half:] return ( sum( left_half ) == sum( right_half ) ) def get_term( n ): """Calculate the nth term of the sequence, which is the number of left-right-balanced permutations of [1, ..., n]. >>> get_term( 4 ) 8 """ list_1_to_n = range( 1, n+1 ) left_right_balanced_permutation_count = 0 for permutation in permutations( list_1_to_n ): if ( is_left_right_balanced_permutation( permutation ) ): left_right_balanced_permutation_count += 1 return left_right_balanced_permutation_count if __name__ == "__main__": import doctest doctest.testmod() terms = [] min_n = int( sys.argv[1] ) max_n = int( sys.argv[2] ) for n in xrange( min_n, max_n+1 ): terms.append( get_term( n ) ) print terms