A336141 Number of ways to choose a strict composition of each part of an integer partition of n.

1, 1, 2, 5, 9, 17, 41, 71, 138, 270, 518, 938, 1863, 3323, 6163, 11436, 20883, 37413, 69257, 122784, 221873, 397258, 708142, 1249955, 2236499, 3917628, 6909676, 12130972, 21251742, 36973609, 64788378, 112103360, 194628113, 336713377, 581527210, 1000153063

Offset

0,3

Comments

A strict composition of n is a finite sequence of distinct positive integers summing to n.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5623

Formula

G.f.: Product_{k >= 1} 1/(1 - A032020(k)*x^k).

Example

The a(1) = 1 through a(5) = 17 ways:
  (1)  (2)      (3)          (4)              (5)
       (1),(1)  (1,2)        (1,3)            (1,4)
                (2,1)        (3,1)            (2,3)
                (2),(1)      (2),(2)          (3,2)
                (1),(1),(1)  (3),(1)          (4,1)
                             (1,2),(1)        (3),(2)
                             (2,1),(1)        (4),(1)
                             (2),(1),(1)      (1,2),(2)
                             (1),(1),(1),(1)  (1,3),(1)
                                              (2,1),(2)
                                              (3,1),(1)
                                              (2),(2),(1)
                                              (3),(1),(1)
                                              (1,2),(1),(1)
                                              (2,1),(1),(1)
                                              (2),(1),(1),(1)
                                              (1),(1),(1),(1),(1)

Maple

b:= proc(n, i, p) option remember; `if`(i*(i+1)/2<n, 0,
     `if`(n=0, p!, b(n, i-1, p)+b(n-i, min(n-i, i-1), p+1)))
    end:
g:= proc(n, i) option remember; `if`(n=0 or i=1, 1,
      g(n, i-1)+b(i$2, 0)*g(n-i, min(n-i, i)))
    end:
a:= n-> g(n$2):
seq(a(n), n=0..38);  # Alois P. Heinz, Jul 31 2020

Mathematica

Table[Length[Join@@Table[Tuples[Join@@Permutations/@Select[IntegerPartitions[#], UnsameQ@@#&]&/@ctn], {ctn, IntegerPartitions[n]}]], {n, 0, 10}]
(* Second program: *)
b[n_, i_, p_] := b[n, i, p] = If[i(i+1)/2 < n, 0,
     If[n==0, p!, b[n, i-1, p] + b[n-i, Min[n-i, i-1], p+1]]];
g[n_, i_] := g[n, i] = If[n==0 || i==1, 1, g[n, i-1] +
     b[i, i, 0] g[n-i, Min[n-i, i]]];
a[n_] := g[n, n];
a /@ Range[0, 38] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

Crossrefs

Multiset partitions of partitions are A001970.

Strict compositions are counted by A032020, A072574, and A072575.

Splittings of partitions are A323583.

Splittings of partitions with distinct sums are A336131.

Cf. A008289, A011782, A304786, A316245, A318684, A319794, A336128, A336130, A336132, A336135.

Partitions:

- Partitions of each part of a partition are A063834.

- Compositions of each part of a partition are A075900.

- Strict partitions of each part of a partition are A270995.

- Strict compositions of each part of a partition are A336141.

Strict partitions:

- Partitions of each part of a strict partition are A271619.

- Compositions of each part of a strict partition are A304961.

- Strict partitions of each part of a strict partition are A279785.

- Strict compositions of each part of a strict partition are A336142.

Compositions:

- Partitions of each part of a composition are A055887.

- Compositions of each part of a composition are A133494.

- Strict partitions of each part of a composition are A304969.

- Strict compositions of each part of a composition are A307068.

Strict compositions:

- Partitions of each part of a strict composition are A336342.

- Compositions of each part of a strict composition are A336127.

- Strict partitions of each part of a strict composition are A336343.

- Strict compositions of each part of a strict composition are A336139.

Sequence in context: A182992 A115851 A163734 * A184353 A019135 A069957

Adjacent sequences: A336138 A336139 A336140 * A336142 A336143 A336144

Keyword

nonn

Author

Gus Wiseman, Jul 18 2020

Status

approved