A000724 Invertible Boolean functions of n variables.

1, 3, 196, 3406687200, 2141364232858913975435172249600, 43025354066936633335853878219659247776604712057098163541301459387254457761792000000

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Equivalence classes of invertible maps from {0,1}^n to {0,1}^n, under action of (C_2)^n on domain and F_n=[S_2]^(S_n) on range. - Sean A. Irvine, Mar 16 2011

Technical report version of Harrison's paper contains incorrect value for a(4). - Sean A. Irvine, Mar 16 2011

References

• M. A. Harrison, The number of classes of invertible Boolean functions, J. ACM 10 (1963), 25-28.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• M. A. Harrison, The number of classes of invertible Boolean functions, J. ACM 10 (1963), 25-28. [Annotated scan of page 27 only]
• Index entries for sequences related to Boolean functions

Programs

Mathematica

Table[((2^n)! + (2^n - 1) (2^(n - 1))! 2^(2^(n - 1)) * (n! * Sum[ (2^(n - 2 k) - 1)/((n - 2 k)!*k!), {k, 0, Floor[(n - 1)/2]}]))/(n! 2^(2 n)), {n, 6}] (* Michael De Vlieger, Aug 20 2017 *)

Formula

a(n) = ((2^n)! + (2^n-1) * (2^(n-1))! * 2^(2^(n-1)) * b(n)) / (n! * 2^(2*n)) where b(n) = n! * Sum_{k=0..floor((n-1)/2)} (2^(n-2*k)-1) / ((n - 2*k)! * k!). - Sean A. Irvine, Aug 20 2017

Extensions

More terms from Sean A. Irvine, Mar 15 2011