How many unique counting functions there are for strings of N bits? Let a counting function inc for inputs of N bits be defined as:

inc(b0 | b1 ... | bN) = F0(b0) | F1(b0,b1) ... | FN(b0,b1,...bN)


Where FN is a function from N bits to a bit, and such that the period of inc is 2^N. Notice that, here, we have a special restriction: the nth bit of the output of inc must only depend on bits that come before the n+1th bit of the input. This is obviously the case for the traditional counting function. How many unique inc functions there are for a given N? 

Example

For n = 3, there are at least two unique functions:

# Example 0

F(b0 | b1 | b2) 
   = not(b0)
   | xor(b0, b1) 
   | if b2 then and(b0,b1) else or(b0,b1)

Produces the usual counting: 000, 100, 010, 110, 001, 101, 011, 111, 000...

# Example 1

F(b0 | b1 | b2)
    = not b0
    | xnor(b0,b1)
    | if b2 then and(b0,b1) else or(b0,b1)

Produces the sequence: 000, 110, 011, 101, 001, 111, 010, 100, 000...
Suppose that a set of functions $F_0,\ldots,F_{N-1}$ satisfies the constraints, generating the sequence $x_0 = 0^N, x_1, \ldots, x_{2^{N-1}-1}$. When does a function $F_N$ satisfy the constraints?

If $F_N$ works, then it generates a sequence of the form
$$ x_0\alpha_0, \ldots, x_{2^N-1}\alpha_{2^N-1}, \\x_0\alpha_{2^N}, \ldots, x_{2^N-1} \alpha_{2^{N+1}-1}. $$
The $\alpha_i$'s are given by the following rules: $\alpha_0 = 0$, and for $0 \leq i \leq 2^N-1$,
$$
\alpha_{i+1} = F_N(x_i\alpha_i), \\
\alpha_{2^N+i+1} = F_N(x_i\alpha_{2^N+i}).
$$
In order for the period to be $2^{N+1}$, we must have $\alpha_{i+1} \neq \alpha_{2^N+i+1}$. This means that there is a function $G_N\colon \{0,1\}^{N-1} \to \{0,1\}$ such that
$$ F_N(x\alpha) = G_N(x) \oplus \alpha. $$
It follows that for $0 \leq i \leq 2^N-1$, we have
$$
\alpha_{i+1} = F_N(x_i \alpha_i) = G_N(x_i) \oplus \alpha_i, \\
\alpha_{2^N+i+1} = F_N(x_i \alpha_{2^N+i}) = G_N(x_i) \oplus \alpha_{2^N+i}.
$$
In particular, this implies that
$$
\alpha_{2^N} = G_N(x_0) \oplus \cdots \oplus G_N(x_{2^N-1}).
$$
We must have $\alpha_{2^N} = 1$ in order to have a period of $2^{N+1}$, and this gives one constraint on $G_N$.
One can check that there are no other constraints, and so the number of possibilities for $F_N$ is $2^{2^N-1}$. In total, the number of possibilities is
$$
2^{2^0-1 + \cdots + 2^N-1} = 2^{2^{N+1}-N-2}.
$$
When $N=0,1,2$, this works out to be $2^0,2^1,2^4$. The corresponding sequences are:

For $N=0$, we have one sequence, $0, 1$.

For $N=1$, we have two sequences, $00, 10, 01, 11$ and $00, 11, 01, 10$.

For $N=2$, we have 16 sequences:
$$
000, 100, 010, 110, 001, 101, 011, 111 \\
000, 100, 010, 111, 001, 101, 011, 110 \\
000, 100, 011, 110, 001, 101, 010, 111 \\
000, 100, 011, 111, 001, 101, 010, 110 \\
000, 101, 010, 110, 001, 100, 011, 111 \\
000, 101, 010, 111, 001, 100, 011, 110 \\
000, 101, 011, 110, 001, 100, 010, 111 \\
000, 101, 011, 111, 001, 100, 010, 110 \\
000, 110, 010, 100, 001, 111, 011, 101 \\
000, 110, 010, 101, 001, 111, 011, 100 \\
000, 110, 011, 100, 001, 111, 010, 101 \\
000, 110, 011, 101, 001, 111, 010, 100 \\
000, 111, 010, 100, 001, 110, 011, 101 \\
000, 111, 010, 101, 001, 110, 011, 100 \\
000, 111, 011, 100, 001, 110, 010, 101 \\
000, 111, 011, 101, 001, 110, 010, 100 
$$