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,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) = 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

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

Cf. A000070, A093695, A089378.

Sequence in context: A308998 A326473 A326598 * A366738 A068006 A000097

Adjacent sequences: A093691 A093692 A093693 * A093695 A093696 A093697

Keyword

nonn

Author

Thomas Wieder, Apr 10 2004

Extensions

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

Status

approved