from collections import Counter from math import factorial from time import time start = time # Generates all partitions of n into k parts, i.e. weakly increasing tuples # of k positive integers whose sum is n. def partitions(n,k): if n >= k >= 1: if k == 1: yield (n,) else: for p in partitions(n-1,k-1): yield (1,) + p for p in partitions(n-k,k): yield tuple(x+1 for x in p) # Given a partition p of n, calculate the number of unordered partitions of # {1,2,...,n} into subsets of size p[0], p[1], p[2], etc. # # For example, perms((1,2,2)) = 15, because the possible partitions are # {1,{2,3},{4,5}}, {1,{2,4},{3,5}}, {1,{2,5},{3,4}}, # {2,{1,3},{4,5}}, {2,{1,4},{3,5}}, {2,{1,5},{3,4}}, etc. def perms(p): prod = factorial(sum(p)) for x in p: prod = prod/factorial(x) f = Counter(p) for x in f: prod = prod/factorial(f[x]) return prod # Number of expressions involving exactly n variables which can be decomposed as the sum # and/or difference of two or more terms. We treat two expressions as equivalent if they # differ only in the order of the terms, or if they differ by changing all of the signs. # # For example, A+B-C is considered to be equivalent to both A-C+B and -B+C-A. def sums(n): if n == 1: return 1 result = 0 for k in range(2,n+1): s = 0 for p in partitions(n,k): prod = perms(p) for x in p: prod = prod * P[x] s += prod result += s * 2**(k-1) S[n] = result return result # Number of expressions involving exactly n variables which can be decomposed as the product # and/or quotient of two or more factors. We treat two expressions as equivalent if they # differ only in the order of the terms, or if they differ only in sign. # # For example, A, B, and C can be combined in 7 ways: # A*B*C, A*B/C, A*C/B, B*C/A, A/(B*C), B/(A*C), and C/(A*B) [but not 1/(A*B*C)] def products(n): if n == 1: return 1 result = 0 for k in range(2,n+1): s = 0 for p in partitions(n,k): prod = perms(p) for x in p: prod = prod * S[x] s += prod result += s * (2**k - 1) P[n] = result return result # Number of expressions involving exactly n variables which can be formed using addition, # subtraction, unary minus, multiplication, and division. Expressions that differ only in sign # or the order of their terms are considered equivalent. If this is not desired, then multiply # the result by 2. def exprs(n): if n == 1: return 1 return sums(n) + products(n) S = [0]*51 P = [0]*51 S[1] = 1 P[1] = 1 for n in range(1,51): print n, exprs(n)