A373306 Sum over all complete compositions of n of the element multiset size.

0, 1, 2, 7, 13, 30, 73, 157, 345, 743, 1650, 3517, 7593, 16120, 34294, 72683, 153475, 323293, 679231, 1423721, 2977692, 6218395, 12959249, 26970243, 56037071, 116280086, 240953162, 498719275, 1031029386, 2129266321, 4392871427, 9054428894, 18645998093

Offset: 0

Author

Alois P. Heinz, May 31 2024

Keywords

• nonn

Comments

A complete composition of n has element set [k] with k<=n (without gaps).

Examples

			a(1) = 1: 1.
a(2) = 2: 11.
a(3) = 7 = 2 + 2 + 3: 12, 21, 111.
a(4) = 13 = 3 + 3 + 3 + 4: 112, 121, 211, 1111.
a(5) = 30 = 3*3 + 4*4 + 5: 122, 212, 221, 1112, 1121, 1211, 2111, 11111.
		

Links

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

Crossrefs

Cf. A107429, A373118, A373305.

Programs

Maple

b:= proc(n, i, t) option remember; `if`(n=0, `if`(i=0, [t!, 0], 0),
     `if`(i<1 or n p+[0, p[1]]*j)(
        b(n-i*j, i-1, t+j)/j!), j=1..n/i)))
    end:
a:= n-> add(b(n, k, 0)[2], k=0..floor((sqrt(1+8*n)-1)/2)):
seq(a(n), n=0..32);

Mathematica

b[n_, i_, t_] := b[n, i, t] = If[n == 0, If[i == 0, {t!, 0}, {0, 0}], If[i < 1 || n < i*(i + 1)/2, {0, 0}, Sum[Function[p, p + {0, p[[1]]}*j][b[n - i*j, i - 1, t + j]/j!], {j, 1, n/i}]]];
a[n_] := Sum[b[n, k, 0][[2]], {k, 0, Floor[(Sqrt[1 + 8*n] - 1)/2]}];
Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Jun 08 2024, after Alois P. Heinz *)

Formula

G.f.: Sum_{k>0} d/dy C({1..k},x,y)|y = 1 where C({s},x,y) = Sum_{i in {s}} (C({s}-{i},x,y)*y*x^i)/(1 - Sum_{i in {s}} (y*x^i)) with C({},x,y) = 1. - John Tyler Rascoe, Jun 18 2024