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, 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

Chai Wah Wu, Table of n, a(n) for n = 0..46

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

Adjacent sequences: A068595 A068596 A068597 * A068599 A068600 A068601

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