Minimal Cover

Author

Eric W. Weisstein
May 11, 2018

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

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

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

Enumeration

<<DiscreteMath`Combinatorica`

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

MinimalCovers[1]

MinimalCovers[2]

MinimalCovers[3]

Table[Count[MinimalCovers[n],_?(Length[#]==k&)],{n,3},{k,n}]//ColumnForm

Timing[Length/@Table[MinimalCovers[n],{n,4}]]

Counts

mu[n_,k_]:=1/k! Sum[Binomial[2^k-k-1,m-k]m! StirlingS2[n,m],{m,k,Min[n,2^k-1]}]

Of length 1 to n

A046165

Table[Sum[mu[n,k],{k,0,n}],{n,10}]

Sum[Binomial[n,i]StirlingS2[i,k](2^k-k-1)^(n-i),{i,k,n}]

seq=Table[Sum[Sum[Binomial[n,i]StirlingS2[i,k](2^k-k-1)^(n-i),{i,k,n}],{k,2,n}]+1,{n,1,20}]

FindSequenceFunction[seq,n]//Head//Timing

FindLinearRecurrence[seq]//Head//Timing

FindGeneratingFunction[seq,x]//Head//Timing

As a function of k

Table[mu[n,k],{n,10},{k,7}]//TableForm

Table[mu[n,5],{n,15}]

Table[mu[n,6],{n,15}]

Table[mu[n,7],{n,15}]

Exponential generating function

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

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

With[{nmax=10},CoefficientList[Series[Sum[(((Exp[x]-1))^n)Exp[x((2^n)-n-1)]/n!,{n,0,100}],{x,0,nmax}],x]Range[0,nmax]!]