A179822 Maximally refined partitions into distinct parts (of any natural number) with largest part n.

1, 1, 2, 3, 5, 7, 12, 16, 26, 37, 58, 79, 128, 171, 271, 376, 576, 783, 1239, 1654, 2567, 3505, 5382, 7245, 11247, 15036, 23187, 31370, 47672, 64146, 98887, 131784, 201340, 271350, 412828, 551744, 843285, 1125417, 1715207, 2299452, 3479341, 4654468, 7090529

Offset

0,3

Comments

For the definition, see sequence A179009. This sequence counts the same objects using a different statistic, the largest part rather than the sum of the parts.

a(n) is the number of subsets of {1..n-1} containing the sum of any two distinct elements whose sum is <= n. This differs from A326080 in that the set may not contain n itself. These sets are the complements of the set of parts in the first definition. - Andrew Howroyd, Apr 13 2021

Links

Table of n, a(n) for n=0..42.

Example

The partitions counted by n=4 are:
  4+1, 4+2+1, 4+3+1, 4+3+2, 4+3+2+1.
The partitions counted by n=5 are:
  5+2+1, 5+3+1, 5+3+2+1, 5+4+2+1, 5+4+3+1, 5+4+3+2, 5+4+3+2+1.

Prog

(PARI)
a(n)={
  my(ok(k, b)=for(i=1, (k-1)\2, if(bittest(b, i) && bittest(b, k-i), return(0))); 1);
  my(recurse(k, b)=if(k==n, ok(k, b), self()(k+1, bitor(b, 1<<k)) + if(ok(k, b), self()(k+1, b))));
  if(n<1, n==0, recurse(1, 0))
} \\ Andrew Howroyd, Apr 13 2021

Crossrefs

Cf. A179009, A179817, A326080.

Sequence in context: A360622 A275592 A319635 * A319769 A326083 A027959

Adjacent sequences: A179819 A179820 A179821 * A179823 A179824 A179825

Keyword

nonn

Author

Moshe Shmuel Newman, Jan 10 2011

Extensions

a(19)-a(42) from Andrew Howroyd, Apr 13 2021

Status

approved