login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of nodes (partitions) in the largest component of the graph G'(n) obtained from the partition graph G(n) by deleting all partitions having repeated parts; G and G' are defined in Comments.
2

%I #4 May 06 2014 15:08:08

%S 1,1,2,2,2,2,3,4,5,6,7,8,9,10,12,15,18,22,26,30,35,40,45,51,57,63,73,

%T 86,101,118,136,156,178,202,228,256,286,319,354,391,431,476,546,624,

%U 710,804,907,1020,1143,1277,1422

%N Number of nodes (partitions) in the largest component of the graph G'(n) obtained from the partition graph G(n) by deleting all partitions having repeated parts; G and G' are defined in Comments.

%C The partition graph G(n) is defined at A241150 as follows: the nodes are the partitions of n, and nodes p and q have an edge if one of them can be obtained from the other by a substitution x -> x-1,1 for some part x. Let R be the set of partitions (nodes) of n that contain a repeated part and let E be the set of edges of G(n) that have a node in R. Removing R and E from G(n) leaves a graph G'(n) whose nodes are the strict partitions of n, as in A000009. (The 2nd Mathematica program at A241900 shows G'(n) for n up to 20.)

%e The 10 nodes and 7 edges of G'(10) are shown here: [10] - [9,1], [8,2] - [7,2,1], [7,3] - [6,3,1], [7,3] - [7,2,1], [6,4] - [5,4,1], [6,4] - [6,3,1], [5,3,2] - [4,3,2,1]; the three components are as follows: [8,2] - [7,2,1] - [7,3] - [6,3,1] - [6,4] - [5,4,1] (6 nodes); [4,3,2,1] - [5,3,2] (2 nodes); [9,1] - [10]] (2 nodes). The largest component has 6 nodes, so that a(10) = 6.

%t z = 30; spawn[part_] := Map[Reverse[Sort[Flatten[ReplacePart[part, {# - 1, 1}, Position[part, #, 1, 1][[1]][[1]]]]]] &, DeleteCases[DeleteDuplicates[part], 1]]; findComponent[start_] := Reap[BreadthFirstScan[g, start, {"DiscoverVertex" -> ((PropertyValue[{g, #1}, "Visited"] = True; Sow[#1]) &)}]][[2, 1]]; subGLengths = Join[{{1}}, Table[parts = Select[IntegerPartitions[k], DeleteDuplicates[#] == # &]; graph = Flatten[Table[part = parts[[n]]; Map[{part, #} &, Select[spawn[part], DeleteDuplicates[#] == # &]], {n, 1, Length[parts]}], 1]; isolated = Map[{#, #} &, Map[#[[1]] &, Cases[Map[{#, MemberQ[Flatten[graph, 1], #]} &, parts], {{___}, False}]]]; graph = Join[graph, isolated]; {graph, isolated} = Map[Map[FromDigits[#[[1]]] <-> FromDigits[#[[2]]] &, #] &, {graph, isolated}]; g = Graph[graph]; Do[PropertyValue[{g, v}, "Visited"] = False, {v, VertexList[g]}];

%t vlists = Reap[Do[If[! PropertyValue[{g, start}, "Visited"], Sow[findComponent[start]]], {start, VertexList[g]}]][[2, 1]]; Reverse[Sort[Map[Length, vlists]]], {k, 2, z}]];

%t Flatten[%] (* A241900 *)

%t Map[#[[1]] &, subGLengths] (* A241901 *)

%t (* _Peter J. C. Moses_, Apr 30 2014 *)

%Y Cf. A241900, A241150, A000041, A000009.

%K nonn,easy

%O 1,3

%A _Clark Kimberling_, May 01 2014