|
|
A054724
|
|
Triangle of numbers of inequivalent Boolean functions of n variables with exactly k nonzero values (atoms) under action of complementing group.
|
|
5
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,8
|
|
REFERENCES
|
M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 143.
|
|
LINKS
|
|
|
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:
|
|
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
|
|
|
KEYWORD
|
easy,nonn,nice,tabf
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|