login
Number of ways to choose a strict composition of each part of a strict integer partition of n.
5

%I #19 Feb 13 2024 20:26:53

%S 1,1,1,4,6,11,22,41,72,142,260,454,769,1416,2472,4465,7708,13314,

%T 23630,40406,68196,119646,203237,343242,586508,993764,1677187,2824072,

%U 4753066,7934268,13355658,22229194,36945828,61555136,102019156,168474033,279181966

%N Number of ways to choose a strict composition of each part of a strict integer partition of n.

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

%H Alois P. Heinz, <a href="/A336142/b336142.txt">Table of n, a(n) for n = 0..7725</a>

%F G.f.: Product_{k >= 1} (1 + A032020(k)*x^k).

%e The a(1) = 1 through a(5) = 11 ways:

%e (1) (2) (3) (4) (5)

%e (1,2) (1,3) (1,4)

%e (2,1) (3,1) (2,3)

%e (2),(1) (3),(1) (3,2)

%e (1,2),(1) (4,1)

%e (2,1),(1) (3),(2)

%e (4),(1)

%e (1,2),(2)

%e (1,3),(1)

%e (2,1),(2)

%e (3,1),(1)

%p b:= proc(n, i, p) option remember; `if`(i*(i+1)/2<n, 0,

%p `if`(n=0, p!, b(n, i-1, p)+b(n-i, min(n-i, i-1), p+1)))

%p end:

%p g:= proc(n, i) option remember; `if`(i*(i+1)/2<n, 0,

%p `if`(n=0, 1, g(n, i-1)+b(i$2, 0)*g(n-i, min(n-i, i-1))))

%p end:

%p a:= n-> g(n$2):

%p seq(a(n), n=0..38); # _Alois P. Heinz_, Jul 31 2020

%t strptn[n_]:=Select[IntegerPartitions[n],UnsameQ@@#&];

%t Table[Length[Join@@Table[Tuples[Join@@Permutations/@strptn[#]&/@ctn],{ctn,strptn[n]}]],{n,0,20}]

%t (* Second program: *)

%t b[n_, i_, p_] := b[n, i, p] = If[i(i+1)/2 < n, 0,

%t If[n == 0, p!, b[n, i-1, p] + b[n-i, Min[n-i, i-1], p+1]]];

%t g[n_, i_] := g[n, i] = If[i(i+1)/2 < n, 0,

%t If[n == 0, 1, g[n, i-1] + b[i, i, 0]*g[n-i, Min[n-i, i-1]]]];

%t a[n_] := g[n, n];

%t a /@ Range[0, 38] (* _Jean-François Alcover_, May 20 2021, after _Alois P. Heinz_ *)

%Y Multiset partitions of partitions are A001970.

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

%Y Splittings of partitions are A323583.

%Y Splittings of partitions with distinct sums are A336131.

%Y Cf. A008289, A316245, A318684, A319794, A336128, A336130, A336132, A336135.

%Y Partitions:

%Y - Partitions of each part of a partition are A063834.

%Y - Compositions of each part of a partition are A075900.

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

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

%Y Strict partitions:

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

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

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

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

%Y Compositions:

%Y - Partitions of each part of a composition are A055887.

%Y - Compositions of each part of a composition are A133494.

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

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

%Y Strict compositions:

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

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

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

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

%K nonn

%O 0,4

%A _Gus Wiseman_, Jul 18 2020