Number of non-increasing boolean functions of $n$ booleans, up to permutations.

Question

How many non-increasing boolean functions of $n$ boolean variables are there? I don't want to count functions that ignore some of their inputs. If two or more functions differ only by permuting their inputs, I only want to count one of them.

For $n=0$, there are two: the constants 0 and 1.

For $n=1$, there is one: the NOT gate.

For $n=2$, there are two: the NOR and NAND gates.

For $n=3$, I think there are five: three-input NOR and NAND gates, the gate that takes the NOT of the majority vote, and two less symmetrical gates.

Can you continue the sequence?

Answer 1

This is https://oeis.org/A006602 . The sequence goes 2, 1, 2, 5, 20, 180, 16143 and the next term is not listed, so perhaps unknown?

I wrote an exhaustive search program to compute the first few terms (up to n=5), then searched OEIS for the sequence. The program is still computing the answer for n=6, which will take an hour or so, I think. The program is written in Python and I include the source code in this answer.

def has_bit(x, bit):
    return x ^ bit < x

def generate_octaves(n):
    '''
    Yields all powers of two up to and including `n`.
    '''
    octave = 1
    while octave <= n:
        yield octave
        octave <<= 1

# For debugging only; not actually used.
def is_non_increasing(table):
    '''
    Tests whether the truth table `table` represents a non-increasing function.
     - table - List of `0` or `1`, representing the output column of a truth
    table.
    '''
    for pos in range(len(table)):
        if table[pos] and not can_append_1(table[:pos]):
            return False
    return True

def can_append_1(table):
    '''
    Assuming `table` represents a prefix of a truth table of a non-increasing
    function, tests whether it would still be non-increasing if you appended
    another `1`.

     - table - List of `0` or `1`, representing a prefix of the output column
    of a truth table.
    '''
    pos = len(table)
    for octave in generate_octaves(pos):
        if has_bit(pos, octave):
            if not table[pos ^ octave]:
                return False
    return True

def generate_truth_tables(n):
    if n == 0:
        yield []
        return
    for prefix in generate_truth_tables(n-1):
        yield prefix + [0]
        if can_append_1(prefix):
            yield prefix +  [1]

def uses_all_inputs(table):
    '''
    Tests whether the truth table `table` represents a function that uses all
    of its inputs.
     - table - List of `0` or `1`, representing the output column of a truth
    table.
    '''
    for octave in generate_octaves(len(table)-1):
        for pos, value in enumerate(table):
            if value != table[pos^octave]:
                break
        else:
            return False
    else:
        return True

def generate_permutations(items):
    if not items:
        yield []
    else:
        for pos, value in enumerate(items):
            for prefix in generate_permutations(items[:pos] + items[pos+1:]):
                yield prefix + [value]

def generate_subsets(items):
    if not items:
        yield []
    else:
        for prefix in generate_subsets(items[:-1]):
            yield prefix
            yield prefix + [items[-1]]

def is_canonical_input_order(table):
    octaves = list(generate_octaves(len(table)-1))
    for permuted_octaves in generate_permutations(octaves):
        permuted_table = [None] * len(table) # Fill in later.
        # Loop through `table` by generating all subsets of `octaves`.
        # Generate also the corresponding subset of `permuted_octaves`.
        # Map that one item into `permuted_table`.
        for pair_list in generate_subsets(zip(octaves, permuted_octaves)):
            old_index = sum(pair[0] for pair in pair_list)
            new_index = sum(pair[1] for pair in pair_list)
            permuted_table[new_index] = table[old_index]
        assert None not in permuted_table
        # `table` should be "better" than `permuted_table`.
        if table > permuted_table:
            return False
    else:
        return True

for n in range(7):
    print
    print "%d input gates" % n
    count1 = 0 # All non-increasing functions.
    count3 = 0 # Non-increasing functions that use all inputs.
    count2 = 0 # Non-increasing fns that use all inputs, ignoring permuations.
    for table in generate_truth_tables(1<<n):
        count1 += 1
        if uses_all_inputs(table):
            count2 += 1
            if is_canonical_input_order(table):
                count3 += 1
                print table
    print "%d non-increasing functions." % count1
    print "%d non-increasing functions that use all inputs." % count2
    print (
        "%d non-increasing functions that use all inputs, up to permutations."
        % count3)

Update 2014-04-01: It correctly computed 16143, but it took rather more than an hour.