cp's OEIS Frontend

A241901 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.

%I A241901 #4 May 06 2014 15:08:08
%S A241901 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 A241901 86,101,118,136,156,178,202,228,256,286,319,354,391,431,476,546,624,
%U A241901 710,804,907,1020,1143,1277,1422
%N A241901 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 A241901 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 A241901 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 A241901 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 A241901 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 A241901 Flatten[%]  (* A241900 *)
%t A241901 Map[#[[1]] &, subGLengths] (* A241901 *)
%t A241901 (* _Peter J. C. Moses_, Apr 30 2014 *)
%Y A241901 Cf. A241900, A241150, A000041, A000009.
%K A241901 nonn,easy
%O A241901 1,3
%A A241901 _Clark Kimberling_, May 01 2014