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,8

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

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.

Example

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
...

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 *)

Crossrefs

Row sums give A000231. Cf. A052265.

Sequence in context: A119329 A334549 A333901 * A360440 A349350 A061494

Adjacent sequences: A054721 A054722 A054723 * A054725 A054726 A054727

Keyword

easy,nonn,nice,tabf

Author

Vladeta Jovovic, Apr 20 2000

Extensions

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

Status

approved