login
Number of partitions of n that sorted in increasing order do not contain a part k in position k.
33

%I #29 Oct 27 2023 20:51:06

%S 1,0,1,1,1,2,3,3,4,5,8,9,12,13,17,22,28,34,42,48,59,71,88,106,130,151,

%T 181,210,250,295,354,417,494,577,675,780,909,1053,1231,1431,1668,1930,

%U 2240,2573,2963,3392,3896,4461,5129,5873,6742,7710,8816,10043,11439

%N Number of partitions of n that sorted in increasing order do not contain a part k in position k.

%C The definition forbids partitions with a part equal to 1, so the smallest possible part is 2, which however can appear at most once.

%C Note that considering partitions in standard decreasing order, we obtain A064428.

%H Alois P. Heinz, <a href="/A238394/b238394.txt">Table of n, a(n) for n = 0..1000</a> (first 201 terms from Giovanni Resta)

%F a(n) + A238395(n) = p(n) = A000041(n).

%F a(n) = Sum_{k>=0} A238406(n,k). - _Alois P. Heinz_, Feb 26 2014

%F a(n) = A238352(n,0). - _Alois P. Heinz_, Jun 08 2014

%e a(6) = 3, 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).

%e From _Joerg Arndt_, Mar 23 2014: (Start)

%e There are a(15) = 22 such partitions of 15:

%e 01: [ 2 3 4 6 ]

%e 02: [ 2 3 5 5 ]

%e 03: [ 2 3 10 ]

%e 04: [ 2 4 4 5 ]

%e 05: [ 2 4 9 ]

%e 06: [ 2 5 8 ]

%e 07: [ 2 6 7 ]

%e 08: [ 2 13 ]

%e 09: [ 3 3 4 5 ]

%e 10: [ 3 3 9 ]

%e 11: [ 3 4 8 ]

%e 12: [ 3 5 7 ]

%e 13: [ 3 6 6 ]

%e 14: [ 3 12 ]

%e 15: [ 4 4 7 ]

%e 16: [ 4 5 6 ]

%e 17: [ 4 11 ]

%e 18: [ 5 5 5 ]

%e 19: [ 5 10 ]

%e 20: [ 6 9 ]

%e 21: [ 7 8 ]

%e 22: [ 15 ]

%e (End)

%p b:= proc(n, i) option remember; `if`(n=0, 1,

%p `if`(i<1, 0, b(n, i-1)+`if`(i>n, 0, (p-> expand(

%p x*(p-coeff(p, x, i-1)*x^(i-1))))(b(n-i, i)))))

%p end:

%p a:= n-> (p-> add(coeff(p, x, i), i=0..degree(p)))(b(n$2)):

%p seq(a(n), n=0..70); # _Alois P. Heinz_, Feb 26 2014

%t a[n_] := Length@ Select[ IntegerPartitions@n, 0 < Min@ Abs[ Reverse@# - Range@ Length@#] &]; Array[a, 30]

%t b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i>n, 0, Function[p, Expand[x*(p-Coefficient[p, x, i-1]*x^(i-1))]][b[n-i, i]]]]]; a[n_] := Function[p, Sum[Coefficient[p, x, i], {i, 0, Exponent[p, x]} ] ][b[n, n]]; Table[a[n], {n, 0, 70}] (* _Jean-François Alcover_, Nov 02 2015, after _Alois P. Heinz_ *)

%Y Cf. A000041, A238395, A064428, A001522, A238352.

%K nonn

%O 0,6

%A _Giovanni Resta_, Feb 26 2014