A015739 Number of 4's in all the partitions of n into distinct parts.

0, 0, 0, 1, 1, 1, 2, 1, 2, 3, 3, 5, 6, 7, 9, 10, 12, 15, 18, 22, 26, 31, 36, 42, 50, 58, 68, 80, 92, 107, 124, 142, 164, 189, 216, 248, 284, 323, 369, 420, 476, 541, 613, 693, 784, 885, 997, 1123, 1264, 1419, 1593, 1787, 2000, 2239, 2504, 2795, 3120, 3479

Offset: 1

Author

Clark Kimberling

Keywords

• nonn

Examples

			a(9) = 2 because in the 8 (=A000009(9)) partitions of 9 into distinct parts, namely [9], [8,1], [7,2], [6,3], [6,2,1], [5,4], [5,3,1] and [4,3,2] we have altogether two parts equal to 4.
		

Links

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

Programs

Maple

g:=x^4*product(1+x^j,j=1..60)/(1+x^4): gser:=series(g,x=0,57): seq(coeff(gser,x,n),n=1..54);
# Emeric Deutsch, Apr 17 2006
b:= proc(n, i) option remember; local g;
      if n=0 then [1, 0]
    elif i<1 then [0, 0]
    else g:= `if`(i>n, [0$2], b(n-i, i-1));
         b(n, i-1) +g +[0, `if`(i=4, g[1], 0)]
      fi
    end:
a:= n-> b(n, n)[2]:
seq (a(n), n=1..100);
# Alois P. Heinz, Oct 27 2012

Mathematica

$RecursionLimit = 1000; b[n_, i_] := b[n, i] = Module[{g}, If[n==0, {1, 0},  If[i<1 , {0, 0}, g = If[i>n, {0, 0}, b[n-i, i-1]]; b[n, i-1] + g + {0, If[i == 4, g[[1]], 0]}]]]; a[n_] := b[n, n][[2]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Apr 01 2015, after Alois P. Heinz *)
Table[Count[Flatten@Select[IntegerPartitions[n], DeleteDuplicates[#] == # &], 4], {n, 58}] (* Robert Price, May 16 2020 *)

Formula

G.f.: x^4*prod(j>=1, 1+x^j)/(1+x^4). - Emeric Deutsch, Apr 17 2006

Corresponding g.f. for "number of k's" is x^k/(1+x^k)*prod(n>=1, 1+x^n ). [Joerg Arndt, Feb 20 2014]