Dedekind Number

Author

Eric W. Weisstein
June 27, 2023

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Logic/DedekindNumber.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/DedekindNumber.html.

©2023 Wolfram Research, Inc. except for portions noted otherwise

Counts

OEIS

A000372

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366

Count of BooleanFunction

Table[2^(2^n)-1,{n,0,5}]

Do[
Print[{n,Count[Table[BooleanFunction[k,n],{k,0,2^(2^n)-1}],_?UnateQ]//Timing}],
{n,0,5}]

Do[
Print[{n,Total[Boole[Table[UnateQ[BooleanFunction[k,n]],{k,0,2^(2^n)-1}]]]//Timing}],
{n,0,5}]

...ran overnight...

Table[Total[Boole[Table[UnateQ[BooleanFunction[k,n]],{k,0,2^(2^n)-1}]]],{n,0,4}]

Stable sets

stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
Table[Length[stableSets[Subsets[Range[n]],SubsetQ]],{n,0,5}]

Do[Print[{n,Length[stableSets[Subsets[Range[n]],SubsetQ]]//Timing}],{n,0,6}]