login
Number of integer partitions of n that can be partitioned into distinct pairs of distinct parts, i.e., into a set of edges.
25

%I #12 Dec 18 2020 07:58:59

%S 1,0,0,1,1,2,2,4,5,8,8,13,17,22,28,39,48,62,81,101,127,167,202,253,

%T 318,395,486,608,736,906,1113,1353,1637,2011,2409,2922,3510,4227,5060,

%U 6089,7242

%N Number of integer partitions of n that can be partitioned into distinct pairs of distinct parts, i.e., into a set of edges.

%C Naturally, such a partition must have an even number of parts. Its multiplicities form a graphical partition (A000569, A320922), and vice versa.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphicalPartition.html">Graphical partition.</a>

%F A027187(n) = a(n) + A339559(n).

%e The a(3) = 1 through a(11) = 13 partitions (A = 10):

%e (21) (31) (32) (42) (43) (53) (54) (64) (65)

%e (41) (51) (52) (62) (63) (73) (74)

%e (61) (71) (72) (82) (83)

%e (3211) (3221) (81) (91) (92)

%e (4211) (3321) (4321) (A1)

%e (4221) (5221) (4322)

%e (4311) (5311) (4331)

%e (5211) (6211) (4421)

%e (5321)

%e (5411)

%e (6221)

%e (6311)

%e (7211)

%e For example, the partition y = (4,3,3,2,1,1) can be partitioned into a set of edges in two ways:

%e {{1,2},{1,3},{3,4}}

%e {{1,3},{1,4},{2,3}},

%e so y is counted under a(14).

%t strs[n_]:=If[n<=1,{{}},Join@@Table[Map[Prepend[#,d]&,Select[strs[n/d],Min@@#>d&]],{d,Select[Rest[Divisors[n]],And[SquareFreeQ[#],PrimeOmega[#]==2]&]}]];

%t Table[Length[Select[IntegerPartitions[n],strs[Times@@Prime/@#]!={}&]],{n,0,15}]

%Y A338916 allows equal pairs (x,x).

%Y A339559 counts the complement in even-length partitions.

%Y A339561 gives the Heinz numbers of these partitions.

%Y A339619 counts factorizations of the same type.

%Y A000070 counts non-multigraphical partitions of 2n, ranked by A339620.

%Y A000569 counts graphical partitions, ranked by A320922.

%Y A001358 lists semiprimes, with squarefree case A006881.

%Y A002100 counts partitions into squarefree semiprimes.

%Y A058696 counts partitions of even numbers, ranked by A300061.

%Y A209816 counts multigraphical partitions, ranked by A320924.

%Y A320655 counts factorizations into semiprimes.

%Y A320656 counts factorizations into squarefree semiprimes.

%Y A339617 counts non-graphical partitions of 2n, ranked by A339618.

%Y A339655 counts non-loop-graphical partitions of 2n, ranked by A339657.

%Y A339656 counts loop-graphical partitions, ranked by A339658.

%Y A339659 counts graphical partitions of 2n into k parts.

%Y The following count partitions of even length and give their Heinz numbers:

%Y - A027187 has no additional conditions (A028260).

%Y - A096373 cannot be partitioned into strict pairs (A320891).

%Y - A338914 can be partitioned into strict pairs (A320911).

%Y - A338915 cannot be partitioned into distinct pairs (A320892).

%Y - A338916 can be partitioned into distinct pairs (A320912).

%Y - A339559 cannot be partitioned into distinct strict pairs (A320894).

%Y Cf. A001055, A001221, A005117, A007717, A025065, A030229, A320893, A338899, A338903, A339564.

%K nonn,more

%O 0,6

%A _Gus Wiseman_, Dec 10 2020