|
| |
|
|
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.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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}]];
Map[#[[1]] &, subGLengths] (* A241901 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
