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,4

Comments

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

Links

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

Formula

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

Example

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).

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 *)

Crossrefs

Cf. A000041, A238394, A064428, A001522.

Sequence in context: A102186 A039842 A188216 * A116901 A350846 A244487

Adjacent sequences: A238392 A238393 A238394 * A238396 A238397 A238398

Keyword

nonn

Author

Giovanni Resta, Feb 26 2014

Status

approved