login
A068598
Number of maximal sets of partitions of n with property that all parts in all partitions in the set are distinct.
1
1, 1, 1, 1, 1, 1, 2, 2, 3, 4, 6, 8, 13, 18, 31, 47, 75, 115, 199, 312, 533, 888, 1536, 2535, 4608, 7694, 13894, 24491, 44278, 78040, 147863, 260376, 489921, 906783, 1701068, 3139340, 6130726, 11328526, 22059386, 42281301, 82180670, 157539076, 317031631, 606850891, 1217662195, 2413169272
OFFSET
0,7
COMMENTS
Also number of cliques in following graph: each strict partition of n represents a vertex, the relation "having no common integer" defines the edges connecting these. - Wouter Meeussen, May 27 2002
Conjecture: a(n) asymptotically grows as a*exp(bx^c), where a≈0.57, b≈0.062, c≈1.54. - Elijah Beregovsky, Nov 12 2022
LINKS
Naohiro Nomoto, a(0)-a(13) [Broken link]
EXAMPLE
a(8) = 3: {8=1+7=2+6=3+5, 8=1+2+5, 8=1+3+4=2+6}.
a(11) = 8: {11=1+10=2+9=3+8=4+7=5+6, 11=1+2+8=4+7=5+6, 11=1+3+7=2+9=5+6, 11=1+4+6=3+8=2+9, 11=2+3+6=4+7=1+10, 11=2+4+5=1+10=3+8, 11=1+2+3+5=4+7, 11=2+4+5=1+3+7}.
MATHEMATICA
maximal[hit_List, candi_List] := Not[Or@@(UnsameQ@@Flatten[{candi, #}]&/@hit)]; (* write 'ListQPartitions[n]' to list all distinct partitions of n *) Table[it=ListQPartitions[n]; Length@DeleteCases[Backtrack[{#, {}}&/@it, UnsameQ@@Flatten[{#}]&, maximal[it, DeleteCases[ #, {}]]&, All], {}, -1], {n, 3, 14}]
Length[FindClique[RelationGraph[DisjointQ, Select[IntegerPartitions[#], DuplicateFreeQ]], Infinity, All]] & /@ Range[25] (* Elijah Beregovsky, Nov 12 2022 *)
PROG
(Python)
from itertools import combinations
from sympy.utilities.iterables import partitions
from networkx import empty_graph, find_cliques
def A068598(n):
if n == 0: return 1
v = tuple(tuple(p.keys()) for p in partitions(n) if max(p.values(), default=0)==1)
G = empty_graph(v)
G.add_edges_from((a, b) for a, b in combinations(v, 2) if set(a).isdisjoint(set(b)))
return sum(1 for c in find_cliques(G)) # Chai Wah Wu, Jan 11 2024
CROSSREFS
Cf. A000009.
Sequence in context: A316076 A368746 A325832 * A293165 A321969 A163770
KEYWORD
hard,nonn,nice
AUTHOR
Naohiro Nomoto, Mar 28 2002
EXTENSIONS
More terms from Wouter Meeussen, May 27 2002
a(25) from Robert G. Wilson v, May 29 2002
a(26)-a(39) from Elijah Beregovsky, Nov 12 2022
a(40)-a(45) from Chai Wah Wu, Jan 11 2024
STATUS
approved