Cover

Author

Eric W. Weisstein
January 16, 2009

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Combinatorics/Cover.nb.

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

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

Initialization

SetOfSubsets[n_]:=Rest[Subsets[Rest[Subsets[Range[n]]]]]

Covers[n_]:=Select[SetOfSubsets[n],Union@@#==Range[n]&]

ProperCovers[n_]:=Select[Covers[n],!MemberQ[#,Range[n]]&]

MinimalQ[l_]:=Module[{k,range=Range[Max[Flatten[l]]]},
If[Length[l]==1,True,
Union@@#≠range&/@And@@Table[Drop[l,{k}],{k,Length[l]}]
]
]

MinimalCovers[n_]:=Select[Covers[n],MinimalQ]

UnlabeledCovers[n_]:=Union[Sort/@Select[Rest[Subsets[Rest[Subsets[Table[1,{n}]]]]],Length[Flatten[#]]>=n&]]

UnlabeledProperCovers[n_]:=Select[UnlabeledCovers[n],!MemberQ[#,Table[1,{n}]]&]

(*
UnlabeledCovers[n_]:=Union[Sort/@(Covers[3]//.k_Integer:>1)]
*)

Enumeration

Length/@Table[Covers[n],{n,4}]

Table[Covers[n],{n,3}]//ColumnForm

Sums

Table[(1/2)Sum[(((-1))^k)Binomial[n,k](2^(2^(n-k))),{k,0,n}],{n,5}]

(1/2) (∑_(k=0)^n)(((-1))^k) (2^(2^(n-k))) (Binomial[n, k])

V5

(1/2)Sum[(((-1))^k)Binomial[n,k](2^(2^(n-k))),{k,0,n}]

V7

(1/2)Sum[(((-1))^k)Binomial[n,k](2^(2^(n-k))),{k,0,n}]

EGF

V7

Sum[Exp[x((2^n)-1)](((Log[2])^n)/(n!)),{n,0,∞}]//Timing

Unlabeled Covers

UnlabeledCovers[2]

Length/@Table[UnlabeledCovers[n],{n,4}]

Unlabeled Proper Covers

UnlabeledCovers[2]

UnlabeledProperCovers[2]

Length/@Table[UnlabeledProperCovers[n],{n,4}]