unique names

gistfile1.txt

def num_partitions(l, k):
    if k == 1:
        return 1
    else:
        total = 0
        for i in range(1, len(l)):
            total += num_partitions(l[i:], k - 1)
        return total

B = 8 # 8 bytes for the fixed name length
total = 0 # accumulator for the number of names
for b in range(1, B + 1):
    # Compute the number of unique partitions for all possible values of k
    l = [0] * b
    partition_total = 0
    for k in range(1, b):
        partition_total += num_partitions(l, k)

    # Multiply the partition total by the number of possible names of length b
    num_unique = 2 ** (8 * b)
    total += (partition_total * num_unique)

print "Total 1: %d" % (total)

def fact(x):
    prod = 1
    for i in range(1, x + 1):
        prod *= i
    return prod

# binom(n, k) = n! / (k! (n - k)!)
def binom(n, k):
    num = fact(n)
    denom = fact(k) * fact(n - k)
    return num / denom

#\sum_{b=1}^B 2^{8b}\left(1 + \sum_{k=1}^{b - 1} \binom {b - 1} {k - 1}\right)
total = 0
for b in range(1, B + 1):
    partition_total = 0
    for k in range(1, b):
        partition_total += binom(b - 1, k - 1)
    num_unique = 2 ** (8 * b)
    total += (partition_total * num_unique)

print "Total 2: %d" % (total)