A093694 Number of one-element transitions from the partitions of n to the partitions of n+1 for labeled parts.

1, 2, 5, 9, 17, 27, 46, 69, 108, 158, 234, 331, 476, 657, 915, 1244, 1694, 2262, 3029, 3988, 5257, 6844, 8901, 11461, 14749, 18809, 23958, 30304, 38263, 48018, 60167, 74977, 93276, 115509, 142772, 175759, 215991, 264449, 323216, 393772, 478884

Offset: 0

Author

Thomas Wieder, Apr 10 2004

Keywords

• nonn

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

Examples

			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
		

Links

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

Crossrefs

Cf. A000070, A093695, A089378.

Programs

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

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

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) = A000041(n) + A006128(n). - Omar E. Pol, Aug 01 2013

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

Extensions

More terms from Robert G. Wilson v, Jul 13 2004