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

%I #17 May 20 2021 04:25:13

%S 1,1,2,5,9,17,41,71,138,270,518,938,1863,3323,6163,11436,20883,37413,

%T 69257,122784,221873,397258,708142,1249955,2236499,3917628,6909676,

%U 12130972,21251742,36973609,64788378,112103360,194628113,336713377,581527210,1000153063

%N Number of ways to choose a strict composition of each part of an 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="/A336141/b336141.txt">Table of n, a(n) for n = 0..5623</a>

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

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

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

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

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

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

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

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

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

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

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

%e (2,1),(2)

%e (3,1),(1)

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

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

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

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

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

%e (1),(1),(1),(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`(n=0 or i=1, 1,

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

%p end:

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

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

%t Table[Length[Join@@Table[Tuples[Join@@Permutations/@Select[IntegerPartitions[#],UnsameQ@@#&]&/@ctn],{ctn,IntegerPartitions[n]}]],{n,0,10}]

%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[n==0 || i==1, 1, g[n, i-1] +

%t b[i, i, 0] g[n-i, Min[n-i, i]]];

%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, A011782, A304786, 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,3

%A _Gus Wiseman_, Jul 18 2020