A179009 Number of maximally refined partitions of n into distinct parts.

1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 2, 2, 3, 5, 1, 3, 2, 3, 5, 7, 2, 5, 3, 4, 6, 7, 11, 3, 8, 5, 6, 6, 8, 11, 15, 7, 13, 9, 9, 9, 10, 12, 16, 22, 11, 20, 15, 17, 14, 15, 16, 18, 24, 30, 18, 30, 26, 28, 22, 27, 21, 25, 27, 33, 42, 36, 45, 43, 46, 38, 44, 33, 43, 36, 44, 47, 60, 46, 66, 64, 70, 63, 72, 61, 69, 60, 63, 58, 69, 80

Offset: 0

Author

David S. Newman, Jan 03 2011

Keywords

• nonn

Comments

Let a_1,a_2,...,a_k be a partition of n into distinct parts. We say that this partition can be refined if one of the summands, say a_i can be replaced with two numbers whose sum is a_i and the resulting partition is a partition into distinct parts. For example, the partition 5+2 can be refined because 5 can be replaced by 4+1 to give 4+2+1. If a partition into distinct parts cannot be refined we say that it is maximally refined.

The value of a(0) is taken to be 1 as is often done when considering partitions (also, the empty partition cannot be refined).

This sequence was suggested by Moshe Shmuel Newman.

From Gus Wiseman, Jun 07 2025: (Start)

Given any strict partition, the following are equivalent:

1) The parts are maximally refined.

2) Every strict partition of a part contains a part. In other words, if y is the set of parts and z is any strict partition of any element of y, then z must contain at least one element from y.

3) No part is a sum of distinct non-parts.

(End)

Examples

			a(11)=2 because there are two partitions of 11 which are maximally refined, namely 6+4+1 and 5+3+2+1.
From _Joerg Arndt_, Apr 23 2023: (Start)
The 15 maximally refined partitions of 35 are:
   1:    [ 1 2 3 4 5 6 14 ]
   2:    [ 1 2 3 4 5 7 13 ]
   3:    [ 1 2 3 4 5 8 12 ]
   4:    [ 1 2 3 4 5 9 11 ]
   5:    [ 1 2 3 4 6 7 12 ]
   6:    [ 1 2 3 4 6 8 11 ]
   7:    [ 1 2 3 4 6 9 10 ]
   8:    [ 1 2 3 4 7 8 10 ]
   9:    [ 1 2 3 5 6 7 11 ]
  10:    [ 1 2 3 5 6 8 10 ]
  11:    [ 1 2 3 5 7 8 9 ]
  12:    [ 1 2 4 5 6 7 10 ]
  13:    [ 1 2 4 5 6 8 9 ]
  14:    [ 1 3 4 5 6 7 9 ]
  15:    [ 2 3 4 5 6 7 8 ]
(End)
		

Links

• Massimo Lauria, Table of n, a(n) for n = 0..1500 (first 1000 terms by Fausto A. C. Cariboni)
• Riccardo Aragona, Lorenzo Campioni, Roberto Civino, and Massimo Lauria, On the maximal part in unrefinable partitions of triangular numbers, arXiv:2111.11084 [math.CO], 2021.
• Riccardo Aragona, Roberto Civino, and Norberto Gavioli, A modular idealizer chain and unrefinability of partitions with repeated parts, arXiv:2301.06347 [math.RA], 2023.
• Riccardo Aragona, Roberto Civino, Norberto Gavioli and Carlo Maria Scoppola, Unrefinable partitions into distinct parts in a normalizer chain, arXiv:2107.04666 [math.CO], 2021.
• Riccardo Aragona, Lorenzo Campioni, Roberto Civino and Massimo Lauria, Verification and generation of unrefinable partitions, arXiv:2112.15096 [math.CO], 2021.
• Joerg Arndt, C++ program to compute such partitions.

Crossrefs

For subsets instead of partitions we have A326080, complement A384350.

These partitions are ranked by A383707, apparently positions of 1 in A383706.

The strict complement is A384318 (strict partitions that can be refined).

This is the strict version of A384392, ranks A384320, complement apparently A384321.

Cf. A048767, A098859, A179822, A239455, A317142, A326083, A351293, A357982, A381454, A382525, A383708, A383710, A384317.

Programs

Mathematica

nonsets[y_]:=If[Length[y]==0,{},Rest[Subsets[Complement[Range[Max@@y],y]]]];
Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&Intersection[#,Total/@nonsets[#]]=={}&]],{n,0,15}] (* Gus Wiseman, Jun 09 2025 *)

Extensions

More terms from Joerg Arndt, Jan 04 2011