A054724 Triangle of numbers of inequivalent Boolean functions of n variables with exactly k nonzero values (atoms) under action of complementing group.

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 7, 7, 14, 7, 7, 1, 1, 1, 1, 15, 35, 140, 273, 553, 715, 870, 715, 553, 273, 140, 35, 15, 1, 1, 1, 1, 31, 155, 1240, 6293, 28861, 105183, 330460, 876525, 2020239, 4032015, 7063784, 10855425, 14743445, 17678835, 18796230

Offset: 0

Author

Vladeta Jovovic, Apr 20 2000

Keywords

• easy
• nonn
• nice
• tabf

Examples

			Triangle begins:
  k    0  1  2  3   4   5   6   7   8   9  10  11  12 13 14 15 16      sums
n
0      1  1                                                              2
1      1  1  1                                                           3
2      1  1  3  1   1                                                    7
3      1  1  7  7  14   7   7   1   1                                   46
4      1  1 15 35 140 273 553 715 870 715 553 273 140 35 15  1  1     4336
...
		

References

• M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 143.

Links

• G. C. Greubel, Rows n = 0..10, flattened
• Index entries for sequences related to Boolean functions

Crossrefs

Row sums give A000231. Cf. A052265.

Programs

Maple

T:= (n, k)-> (binomial(2^n, k)+`if`(k::odd, 0,
             (2^n-1)*binomial(2^(n-1), k/2)))/2^n:
seq(seq(T(n, k), k=0..2^n), n=0..5);  # Alois P. Heinz, Jan 27 2023

Mathematica

rows = 5; t[n_, k_?OddQ] := 2^-n*Binomial[2^n, k]; t[n_, k_?EvenQ] := 2^-n*(Binomial[2^n, k] + (2^n-1)*Binomial[2^(n-1), k/2]); Flatten[ Table[ t[n, k], {n, 1, rows}, {k, 0, 2^n}]] (* Jean-François Alcover, Nov 21 2011, after Vladeta Jovovic *)
T[n_, k_]:= If[OddQ[k], Binomial[2^n, k]/2^n, 2^(-n)*(Binomial[2^n, k] + (2^n - 1)*Binomial[2^(n - 1), k/2])]; Table[T[n,k], {n,1,5}, {k,0,2^n}] //Flatten  (* G. C. Greubel, Feb 15 2018 *)

Formula

T(n,k) = 2^(-n)*C(2^n, k) if k is odd and 2^(-n)*(C(2^n, k) + (2^n-1)*C(2^(n-1), k/2)) if k is even.

Extensions

Two terms for row n=0 prepended by Alois P. Heinz, Jan 27 2023