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

%I #56 Aug 27 2024 21:51:53

%S 1,2,5,9,17,27,46,69,108,158,234,331,476,657,915,1244,1694,2262,3029,

%T 3988,5257,6844,8901,11461,14749,18809,23958,30304,38263,48018,60167,

%U 74977,93276,115509,142772,175759,215991,264449,323216,393772,478884

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

%C 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].

%C a(n) is also the total number of parts in all partitions of the integer n+1 which contain at least one part 1.

%C 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

%C 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]

%C Number of vertical elements in the structure of A225610. - _Omar E. Pol_, Aug 01 2013

%H Alois P. Heinz, <a href="/A093694/b093694.txt">Table of n, a(n) for n = 0..1000</a>

%F 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.

%F 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.

%F G.f.: sum(n>=0, (n+1) * x^n / prod(k=1..n, 1-x^k ) ). - _Joerg Arndt_, Apr 17 2011

%F a(n) = A000041(n) + A006128(n). - _Omar E. Pol_, Aug 01 2013

%F 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

%e 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].

%e 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.

%e 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":

%e 01: [ 1:0 1:0 1:0 1:0 ]

%e 02: [ 1:0 1:0 1:0 1:1 ]

%e 03: [ 1:0 1:0 1:1 1:1 ]

%e 04: [ 1:0 1:1 1:1 1:1 ]

%e 05: [ 1:1 1:1 1:1 1:1 ]

%e 06: [ 2:0 1:0 1:0 ]

%e 07: [ 2:0 1:0 1:1 ]

%e 08: [ 2:0 1:1 1:1 ]

%e 09: [ 2:0 2:0 ]

%e 10: [ 2:0 2:1 ]

%e 11: [ 2:1 1:1 1:1 ]

%e 12: [ 2:1 2:1 ]

%e 13: [ 3:0 1:0 ]

%e 14: [ 3:0 1:1 ]

%e 15: [ 3:1 1:1 ]

%e 16: [ 4:0 ]

%e 17: [ 4:1 ]

%e - _Joerg Arndt_, Apr 28 2013

%p 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;

%p ##

%p b:= proc(n,i) option remember; local x, y;

%p if n<=0 or i=0 then [0, 0]

%p elif i=1 then [1, n]

%p else x:= b(n, i-1);

%p y:= b(n-i, i);

%p [x[1]+y[1], x[2]+y[2]+y[1]]

%p fi

%p end:

%p a:= n-> b(n+1, n+1)[2]:

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Apr 24, 2011

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

%t 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_ *)

%o (PARI) a(n) = numbpart(n) + sum(m=1, n, numdiv(m)*numbpart(n - m)); \\ _Indranil Ghosh_, Apr 25 2017

%o (Python)

%o from sympy import divisor_count, npartitions

%o 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

%Y Cf. A000070, A093695, A089378.

%K nonn

%O 0,2

%A _Thomas Wieder_, Apr 10 2004

%E More terms from _Robert G. Wilson v_, Jul 13 2004