A222656 Number T(n,k) of partitions of n using exactly k primes; triangle T(n,k), n>=0, 0<=k<=floor(n/2), read by rows.
1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 3, 2, 3, 4, 3, 1, 3, 6, 4, 2, 5, 7, 6, 3, 1, 6, 9, 8, 5, 2, 8, 11, 12, 7, 3, 1, 8, 17, 14, 10, 5, 2, 12, 20, 19, 14, 8, 3, 1, 13, 26, 25, 19, 11, 5, 2, 17, 31, 35, 24, 16, 8, 3, 1, 19, 41, 42, 34, 21, 12, 5, 2, 26, 47, 56, 44, 29
Offset: 0
Examples
T(6,0) = 3: [6], [4,1,1], [1,1,1,1,1,1]. T(6,1) = 4: [5,1], [4,2], [3,1,1,1], [2,1,1,1,1]. T(6,2) = 3: [3,3], [3,2,1], [2,2,1,1]. T(6,3) = 1: [2,2,2]. Triangle T(n,k) begins: 1; 1; 1, 1; 1, 2; 2, 2, 1; 2, 3, 2; 3, 4, 3, 1; 3, 6, 4, 2; 5, 7, 6, 3, 1; 6, 9, 8, 5, 2; 8, 11, 12, 7, 3, 1; 8, 17, 14, 10, 5, 2; ...
Links
- Alois P. Heinz, Rows n = 0..200, flattened
Programs
-
Maple
b:= proc(n, i) option remember; local j; if n=0 then 1 elif i<1 then 0 else []; for j from 0 to n/i do zip((x, y)->x+y, %, [`if`(isprime(i), 0$j, NULL), b(n-i*j, i-1)], 0) od; %[] fi end: T:= n-> b(n$2): seq(T(n), n=0..16); -
Mathematica
zip[f_, x_List, y_List, z_] := With[{m = Max[Length[x], Length[y]]}, Thread[f[PadRight[x, m, z], PadRight[y, m, z]]]]; b[n_, i_] := b[n, i] = Module[{j, pc}, Which[n == 0, {1}, i<1, {0}, True, pc = {}; For[j = 0, j <= n/i, j++, pc = zip[Plus, pc, Join[If[PrimeQ[i], Array[0&, j], {}], b[n-i*j, i-1]], 0]]; pc]]; T[n_] := b[n, n]; Table[T[n], {n, 0, 16}] // Flatten (* Jean-François Alcover, Jan 29 2014, after Alois P. Heinz *)
Formula
Sum_{k=1..floor(n/2)} k * T(n,k) = A037032(n).
G.f.: G(t,x) = Product_{i>=1} (1 - x^prime(i))/((1 - x^i)*(1 - t*x^prime(i))). - Emeric Deutsch, Nov 11 2015