OFFSET
0,2
COMMENTS
For the unlabeled case, the number of one-element transitions from the partitions of n to the partitions of n+1 is given by A000070. Example: There are A000070(4) = 12 transitions from n=4 to n=5: [1111] -> [11111], [1111] -> [1112], [112] -> [1112], [112] -> [113], [112] -> [122], [13] -> [113], [13] -> [14], [13] -> [23], [22] -> [23], [22] -> [122], [4] -> [14], [4] -> [5].
a(n) is also the total number of parts in all partitions of the integer n+1 which contain at least one part 1.
More generally, a(n) is also the total number of parts in all partitions of n+k that contain k as a part, if k >= 1. - Omar E. Pol, Sep 25 2013
Also partitions of n into 2 sorts of parts where all parts of the first sort precede all parts of the second sort; see example. [Joerg Arndt, Apr 28 2013]
Number of vertical elements in the structure of A225610. - Omar E. Pol, Aug 01 2013
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
FORMULA
a(n) = Sum_k=1^p(n) (nops(p(k, n)) + 1), where p(n) is the number of partitions of n and nops(p(k, n)) is the number of parts in the k-th partition p(n, k) of n.
a(n) = Sum_k=1^p(n) nops(p(k, n)[subject to: at least one p(l, k, n) = 1]; p(n) = number of partitions of n, p(k, n) = k-th partition, p(l, k, n) = l-th part in the k-th partition p(k, n) of integer n.
G.f.: sum(n>=0, (n+1) * x^n / prod(k=1..n, 1-x^k ) ). - Joerg Arndt, Apr 17 2011
a(n) ~ exp(Pi*sqrt(2*n/3))*(2*gamma + log(6*n/Pi^2))/(4*Pi*sqrt(2*n)), where gamma is the Euler-Mascheroni constant A001620. - Vaclav Kotesovec, Oct 24 2016
EXAMPLE
In the labeled case, we have 9 one-element transitions from all partitions of n=3 to the partitions of n+1=4: [1,1,1] -> [1,1,1,1]; [1,1,1] -> [1,1,2]; [1,1,1] -> [1,1,2]; [1,1,1] -> [1,1,2]; [1,2] -> [1,1,2]; [1,2] -> [1,3]; [1,2] -> [2,2]; [3] -> [1,3]; [3] -> [4].
For n = 3 we have the following partitions of 3+1 = 4 which contain at least one part 1: [1111], [112], [13] and these partitions contain 4 + 3 + 2 = 9 = a(3) parts.
There are a(4)=17 partitions of 4 into 2 sorts where all parts of the first sort precede all parts of the second sort. Here p:s stands for "part p of sort s":
01: [ 1:0 1:0 1:0 1:0 ]
02: [ 1:0 1:0 1:0 1:1 ]
03: [ 1:0 1:0 1:1 1:1 ]
04: [ 1:0 1:1 1:1 1:1 ]
05: [ 1:1 1:1 1:1 1:1 ]
06: [ 2:0 1:0 1:0 ]
07: [ 2:0 1:0 1:1 ]
08: [ 2:0 1:1 1:1 ]
09: [ 2:0 2:0 ]
10: [ 2:0 2:1 ]
11: [ 2:1 1:1 1:1 ]
12: [ 2:1 2:1 ]
13: [ 3:0 1:0 ]
14: [ 3:0 1:1 ]
15: [ 3:1 1:1 ]
16: [ 4:0 ]
17: [ 4:1 ]
- Joerg Arndt, Apr 28 2013
MAPLE
main := proc(n::integer) local a, ndxp, ListOfPartitions; with(combinat): with(ListTools): ListOfPartitions:=partition(n-1); a:=0; for ndxp from 1 to nops(ListOfPartitions) do if Occurrences(1, ListOfPartitions[ndxp]) > 0 then a:=a+nops(Flatten(ListOfPartitions[ndxp])); print("ndxp, Flatten(ListOfPartitions[ndxp]):", ndxp, Flatten(ListOfPartitions[ndxp])); print("ndxp, ListOfPartitions[ndxp], a:", ndxp, ListOfPartitions[ndxp], a); # End of if-clause *** Occurrences(1, ListOfPartitions[ndxp]) *** fi; end do; print("n, a(n):", n, a); end proc;
##
b:= proc(n, i) option remember; local x, y;
if n<=0 or i=0 then [0, 0]
elif i=1 then [1, n]
else x:= b(n, i-1);
y:= b(n-i, i);
[x[1]+y[1], x[2]+y[2]+y[1]]
fi
end:
a:= n-> b(n+1, n+1)[2]:
seq(a(n), n=0..100); # Alois P. Heinz, Apr 24, 2011
MATHEMATICA
f[n_] := Block[{l = Sort[ Flatten[ IntegerPartitions[n]]]}, Length[l] - Count[l, 1]]; g[n_] := (f[n] + Sum[PartitionsP[k], {k, 0, n}]); Table[ g[n], {n, 0, 40}] (* Robert G. Wilson v, Jul 13 2004 *)
b[n_, i_] := b[n, i] = Module[{x, y}, If[n <= 0 || i == 0, {0, 0}, If[i == 1, {1, n}, x = b[n, i-1]; y = b[n-i, i]; {x[[1]] + y[[1]], x[[2]] + y[[2]] + y[[1]]}]]]; a[n_] := b[n+1, n+1][[2]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 10 2015, after Alois P. Heinz *)
PROG
(PARI) a(n) = numbpart(n) + sum(m=1, n, numdiv(m)*numbpart(n - m)); \\ Indranil Ghosh, Apr 25 2017
(Python)
from sympy import divisor_count, npartitions
def a(n): return npartitions(n) + sum([divisor_count(m)*npartitions(n - m) for m in range(1, n + 1)]) # Indranil Ghosh, Apr 25 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Thomas Wieder, Apr 10 2004
EXTENSIONS
More terms from Robert G. Wilson v, Jul 13 2004
STATUS
approved