A238395 Number of partitions of n that sorted in increasing order contain a part k in position k for some k.

0, 1, 1, 2, 4, 5, 8, 12, 18, 25, 34, 47, 65, 88, 118, 154, 203, 263, 343, 442, 568, 721, 914, 1149, 1445, 1807, 2255, 2800, 3468, 4270, 5250, 6425, 7855, 9566, 11635, 14103, 17068, 20584, 24784, 29754, 35670, 42653, 50934, 60688, 72212, 85742, 101662, 120293

Offset: 0

Author

Giovanni Resta, Feb 26 2014

Keywords

• nonn

Comments

Note that considering partitions in standard decreasing order, we obtain A001522.

Examples

			a(6) = 11 - 3 = 8, because of the 11 partitions of 6 only 3 do not contain a 1 in position 1, a 2 in position 2, or a 3 in position 3, namely (3,3), (2,4) and (6).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from Giovanni Resta)

Crossrefs

Cf. A000041, A238394, A064428, A001522.

Programs

Maple

b:= proc(n, i) option remember; `if`(n=0, [0, 1],
      `if`(i<1, [0$2], b(n, i-1) +`if`(i>n, 0,
      (p->[p[1] +coeff(p[2], x, i-1), expand(x*(p[2]-
       coeff(p[2], x, i-1)*x^(i-1)))])(b(n-i, i)))))
    end:
a:= n-> b(n$2)[1]:
seq(a(n), n=0..70);  # Alois P. Heinz, Feb 26 2014

Mathematica

a[n_] := Length@ Select[IntegerPartitions@ n, MemberQ[ Reverse@# - Range@ Length@#, 0] &]; Array[a, 30]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n==0, {0, 1}, If[i<1, {0, 0}, b[n, i-1] + If[i>n, 0, Function[p, {p[[1]] + Coefficient[p[[2]], x, i-1], x*(p[[2]] - Coefficient[p[[2]], x, i-1]*x^(i-1))}][b[n-i, i]]]]]; a[n_] := b[n, n][[1]]; Table[a[n], {n, 0, 70}] (* Jean-François Alcover, Aug 29 2016, after Alois P. Heinz *)

Formula

a(n) + A238394(n) = p(n) = A000041(n).