login
Number of integer partitions of n that are the vertex-degrees of some set system with no singletons.
3

%I #14 Aug 01 2019 00:29:22

%S 1,0,1,1,2,3,5,7,10,15,21,28

%N Number of integer partitions of n that are the vertex-degrees of some set system with no singletons.

%C A set system is a finite set of finite nonempty sets.

%e The a(2) = 1 through a(9) = 15 partitions:

%e (11) (111) (211) (221) (222) (322) (2222) (333)

%e (1111) (2111) (2211) (2221) (3221) (3222)

%e (11111) (3111) (3211) (3311) (3321)

%e (21111) (22111) (22211) (4221)

%e (111111) (31111) (32111) (22221)

%e (211111) (41111) (32211)

%e (1111111) (221111) (33111)

%e (311111) (42111)

%e (2111111) (222111)

%e (11111111) (321111)

%e (411111)

%e (2211111)

%e (3111111)

%e (21111111)

%e (111111111)

%e The a(8) = 10 integer partitions together with a realizing set system for each (the parts of the partition count the appearances of each vertex in the set system):

%e (41111): {{1,2},{1,3},{1,4},{1,5}}

%e (3311): {{1,2},{1,2,3},{1,2,4}}

%e (3221): {{1,2},{1,3},{1,2,3,4}}

%e (32111): {{1,2},{1,3},{1,2,4,5}}

%e (311111): {{1,2},{1,3},{1,4,5,6}}

%e (2222): {{1,2},{3,4},{1,2,3,4}}

%e (22211): {{1,2,3},{1,2,3,4,5}}

%e (221111): {{1,2},{1,2,3,4,5,6}}

%e (2111111): {{1,2},{1,3,4,5,6,7}}

%e (11111111): {{1,2,3,4,5,6,7,8}}

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

%t hyp[m_]:=Select[mps[m],And[And@@UnsameQ@@@#,UnsameQ@@#,Min@@Length/@#>1]&];

%t strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n];

%t Table[Length[Select[strnorm[n],hyp[#]!={}&]],{n,8}]

%Y Cf. A000070, A000569, A147878, A209816, A283877, A306005, A318361, A320922, A320923, A320924, A321177.

%K nonn,more

%O 0,5

%A _Gus Wiseman_, Oct 29 2018