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.

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, 86, 101, 118, 136, 156, 178, 202, 228, 256, 286, 319, 354, 391, 431, 476, 546, 624, 710, 804, 907, 1020, 1143, 1277, 1422

Offset

1,3

Comments

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

Links

Table of n, a(n) for n=1..51.

Example

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.

Mathematica

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]}];
vlists = Reap[Do[If[! PropertyValue[{g, start}, "Visited"], Sow[findComponent[start]]], {start, VertexList[g]}]][[2, 1]]; Reverse[Sort[Map[Length, vlists]]], {k, 2, z}]];
Flatten[%]  (* A241900 *)
Map[#[[1]] &, subGLengths] (* A241901 *)
(* Peter J. C. Moses, Apr 30 2014 *)

Crossrefs

Cf. A241900, A241150, A000041, A000009.

Sequence in context: A029080 A147652 A058360 * A238213 A193942 A098527

Adjacent sequences: A241898 A241899 A241900 * A241902 A241903 A241904

Keyword

nonn,easy

Author

Clark Kimberling, May 01 2014

Status

approved