A262671 -id:A262671 - cp's OEIS frontend

A276024 Number of positive subset sums of integer partitions of n.

1, 3, 7, 14, 27, 47, 81, 130, 210, 319, 492, 718, 1063, 1512, 2178, 3012, 4237, 5765, 7930, 10613, 14364, 18936, 25259, 32938, 43302, 55862, 72694, 92797, 119499, 151468, 193052, 242748, 307135, 383315, 481301, 597252, 744199, 918030, 1137607, 1395101, 1718237, 2098096, 2569047, 3121825, 3805722

Offset: 1

Gus Wiseman, Aug 16 2016

nonn

For a multiset p of positive integers summing to n, a pair (t,p) is defined to be a positive subset sum if there exists a nonempty submultiset of p summing to t. Positive integers with positive subset sums form a multiorder. This sequence is dominated by A122768 (submultisets of integer partitions of n).

			The a(4)=14 positive subset sums are: {(4,4), (1,31), (3,31), (4,31), (2,22), (4,22), (1,211), (2,211), (3,211), (4,211), (1,1111), (2,1111), (3,1111), (4,1111)}.

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..150
Konstantinos Koiliaris and Chao Xu, A Faster Pseudopolynomial Time Algorithm for Subset Sum, arXiv:1507.02318 [cs.DS], 2015-2016.
Gus Wiseman, Comcategories and Multiorders (pdf version)

Cf. A122768, A063834, A262671.

sums[ptn_?OrderedQ]:=sums[ptn]=If[Length[ptn]===1,ptn,Module[{pri,sms},
pri=Union[Table[Delete[ptn,i],{i,Length[ptn]}]];
sms=Join[sums[#],sums[#]+Total[ptn]-Total[#]]&/@pri;
Union@@sms
]];
Table[Total[Length[sums[Sort[#]]]&/@IntegerPartitions[n]],{n,1,25}]
(* Second program: *)
b[n_, i_, s_] := b[n, i, s] = If[n == 0, Length[s], If[i < 1, 0, b[n, i - 1, s] + b[n - i, Min[n - i, i], {#, # + i}& /@ s // Flatten // Union]]];
a[n_] := b[n, n, {0}] - PartitionsP[n];
Array[a, 45] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz in A304792 *)

# uses A304792_T
from sympy import npartitions
def A276024(n): return A304792_T(n,n,(0,),1) - npartitions(n) # Chai Wah Wu, Sep 25 2023

A080108 a(n) = Sum_{k=1..n} k^(n-k)*binomial(n-1,k-1).

Original entry on oeis.org

1, 2, 6, 23, 104, 537, 3100, 19693, 136064, 1013345, 8076644, 68486013, 614797936, 5818490641, 57846681092, 602259154853, 6548439927680, 74180742421185, 873588590481988, 10674437936521069, 135097459659312176

Offset: 1

Vladeta Jovovic, Mar 15 2003

nonn

Row sums of triangle A154372. Example: a(3)=1+12+9+1=23. From A152818. - Paul Curtz, Jan 08 2009
Number of pointed set partitions of a pointed set k[1...k...n] with a prescribed point k. - Gus Wiseman, Sep 27 2015
With offset 0, a(n) is the number of partial functions (A000169) from [n]->[n] such that every element  in the domain of definition is mapped to a fixed point.  This implies a(n) is the number of idempotent partial functions Cf. A121337. - Geoffrey Critzer, Aug 07 2016

			G.f. = x + 2*x^2 + 6*x^3 + 23*x^4 + 104*x^5 + 537*x^6 + 3100*x^7 + 19693*x^8 + ...
The a(4) = 23 pointed set partitions of 1[1 2 3 4] are 1[1[1 2 3 4]], 1[1[1] 2[2 3 4]], 1[1[1] 3[2 3 4]], 1[1[1] 4[2 3 4]], 1[1[1 2] 3[3 4]], 1[1[1 2] 4[3 4]], 1[1[1 3] 2[2 4]], 1[1[1 3] 4[2 4]], 1[1[1 4] 2[2 3]], 1[1[1 4] 3[2 3]], 1[1[1 2 3] 4[4]], 1[1[1 2 4] 3[3]], 1[1[1 3 4] 2[2]], 1[1[1] 2[2] 3[3 4]], 1[1[1] 2[2] 4[3 4]], 1[1[1] 2[2 3] 4[4]], 1[1[1] 2[2 4] 3[3]], 1[1[1] 3[3] 4[2 4]], 1[1[1] 3[2 3] 4[4]], 1[1[1 2] 3[3] 4[4]], 1[1[1 3] 2[2] 4[4]], 1[1[1 4] 2[2] 3[3]], 1[1[1] 2[2] 3[3] 4[4]].

Vincenzo Librandi, Table of n, a(n) for n = 1..200

First column of array A098697.

Cf. A152818, A185298, A262671.

[(1/n)*(&+[Binomial(n,k)*k^(n-k+1): k in [0..n]]): n in [1..30]]; // G. C. Greubel, Jan 22 2023

Table[Sum[k^(n-k) Binomial[n-1,k-1],{k,n}],{n,30}] (* Harvey P. Dale, Aug 19 2012 *)
Table[SeriesCoefficient[Sum[x^k/(1-k*x)^k,{k,0,n}],{x,0,n}], {n,1,20}] (* Vaclav Kotesovec, Aug 06 2014 *)
CoefficientList[Series[E^(x*(1+E^x)), {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Aug 06 2014 *)

a(n)=sum(k=1,n, k^(n-k)*binomial(n-1,k-1)) \\ Anders Hellström, Sep 27 2015

def A080108(n): return (1/n)*sum(binomial(n,k)*k^(n-k+1) for k in range(n+1))
[A080108(n) for n in range(1,31)] # G. C. Greubel, Jan 22 2023

G.f.: Sum_{k>0} x^k/(1-k*x)^k.
E.g.f. (for offset 0): exp(x*(1+exp(x))). - Vladeta Jovovic, Aug 25 2003
a(n) = A185298(n)/n.

A255397 Number of multimin-partitions of normal multisets of weight n.

Original entry on oeis.org

1, 1, 4, 18, 92, 528, 3356, 23344, 175984, 1426520, 12352600, 113645488, 1105760224, 11333738336, 121957021744, 1373618201360, 16151326356192, 197796234588800, 2517603785738752, 33242912468993312, 454583512625280256, 6427749935432143072, 93847133530055987840

Offset: 0

Gus Wiseman, Feb 22 2015

nonn

A multiset is normal if its entries span an initial interval of positive integers. A multimin-partition is any sequence of multisets whose minima are weakly increasing. In a suitable category (see example) multimin-partitions m=(m_1,...,m_k) are morphisms m : U(m_1,...,m_k) -> {min(m_1),...,min(m_k)} where U denotes multiset union and min denotes minimum.

			For a(3) = 18
[[1][2][3]]:[123]->[123]
[[1][23]]:[123]->[12]
[[13][2]]:[123]->[12]
[[12][3]]:[123]->[13]
[[123]]:[123]->[1]
[[1][2][2]]:[122]->[122]
[[1][22]]:[122]->[12]
[[12][2]]:[122]->[12]
[[122]]:[122]->[1]
[[1][1][2]]:[112]->[112]
[[1][12]]:[112]->[11]
[[12][1]]:[112]->[11]
[[11][2]]:[112]->[12]
[[112]]:[112]->[1]
[[1][1][1]]:[111]->[111]
[[1][11]]:[111]->[11]
[[11][1]]:[111]->[11]
[[111]]:[111]->[1]

Andrew Howroyd, Table of n, a(n) for n = 0..200
Gus Wiseman, Comcategories and Multiorders

Cf. A262671.

mmcount[m_List] := mmcount[m] = If[Length[m] === 0, 0, 1 + Plus @@ mmcount /@ Union[Subsets[Rest[m]]]];
mmallnorm[n_Integer] := Function[s, Array[Count[s, y_ /; y <= #] + 1 &, n]] /@ Subsets[Range[n - 1] + 1];
Array[Plus @@ mmcount /@ mmallnorm[#] &, 13]

R(n,k)=Vec(prod(j=1, k, 1/(1 - x/(1-x + O(x^n))^j)) + O(x*x^n))
seq(n)={sum(k=0, n, R(n, k)*sum(r=k, n, binomial(r, k)*(-1)^(r-k)) )} \\ Andrew Howroyd, Feb 04 2021

a(14)-a(15) from Vaclav Kotesovec, Feb 22 2015

a(0)=1 prepended and terms a(16) and beyond from Andrew Howroyd, Feb 04 2021

A185298 Expansion of e.g.f. xexp(x)exp(x*exp(x)).

Original entry on oeis.org

0, 1, 4, 18, 92, 520, 3222, 21700, 157544, 1224576, 10133450, 88843084, 821832156, 7992373168, 81458868974, 867700216380, 9636146477648, 111323478770560, 1335253363581330, 16598183219157772, 213488758730421380, 2837046652845555696, 38899888173340835894

Offset: 0

Geoffrey Critzer, Feb 20 2011

nonn

a(n) is the number of ways to designate an element in each block of the set partitions of {1,2,...,n} and then designate a block.
Inverse binomial transform: b(n) = Sum (-1)^(n-k)*C(n,k)*a(k), k=0..n of A052512. - Alexander R. Povolotsky, Oct 01 2011
Number of pointed set partitions of pointed sets k[1...k...n] for any point k. - Gus Wiseman, Sep 27 2015
Exponential series reversal gives A207833 with alternating signs: 1, -4, 30, -332, 4880, ... . - Vladimir Reshetnikov, Aug 04 2019

			The a(2) = 4 pointed set partitions are 1[1[12]], 1[1[1]2[2]], 2[1[1]2[2]], 2[2[12]].
The a(3) = 18 pointed set partitions are 1[1[123]], 1[1[1]2[23]], 1[1[1]3[23]], 1[1[12]3[3]], 1[1[13]2[2]], 1[1[1]2[2]3[3]], 2[2[123]], 2[1[1]2[23]], 2[1[13]2[2]], 2[2[2]3[13]], 2[2[12]3[3]], 2[1[1]2[2]3[3]], 3[3[123]], 3[1[1]3[23]], 3[1[12]3[3]], 3[2[2]3[13]], 3[2[12]3[3]], 3[1[1]2[2]3[3]].

G. C. Greubel, Table of n, a(n) for n = 0..535
Vaclav Kotesovec, Graph - the asymptotic ratio (10000 terms)

Cf. A052512, A080108, A207833, A262671.

nn=30; a=x Exp[x]; Range[0,nn]! CoefficientList[Series[a Exp[a], {x,0,nn}],x]

x='x+O('x^33); concat([0],Vec(serlaplace(x*exp(x)*exp(x*exp(x))))) \\ Joerg Arndt, Oct 04 2015

E.g.f.: A(A(x)) where A(x) = x*exp(x).
a(n) = Sum_{k=1..n} binomial(n,k)*k^(n-k+1). - Vladimir Kruchinin, Sep 23 2011
O.g.f.: Sum_{k>=1} k*x^k/(1 - k*x)^(k+1). - Ilya Gutkovskiy, Oct 09 2018
a(n) ~ exp(r*exp(r) + r - n) * n^(n + 1/2) / (r^(n - 1/2) * sqrt(1 + exp(r)*(1 + 3*r + r^2))), where r = 2*LambertW(exp(1/4)*sqrt(n)/2) - 1/2 + 1/(16*LambertW(exp(1/4)*sqrt(n)/2)^2 + LambertW(exp(1/4)*sqrt(n)/2) - 1). - Vaclav Kotesovec, Mar 21 2023

A262673 Number of pointed trees on normal pointed multisets of weight n.

Original entry on oeis.org

1, 3, 34, 615, 15410, 494018

Offset: 1

Gus Wiseman, Sep 26 2015

A pointed multiset is normal if its entries span an initial interval of positive integers.

			The a(2) = 3 pointed trees are 1[1 1], 1[1 2], 2[1 2].
The a(3) = 34 pointed trees of the form rootpoint[pointedbranch ... pointedbranch] are:
1[1 1[1 1]], 1[1[1 1] 1], 1[1 1 1],
1[1 2[2 2]], 1[1[1 2] 2], 1[1 2 2],
2[1 2[2 2]], 2[1[1 2] 2], 2[2 2[1 2]], 2[2[1 2] 2], 2[1 2 2],
1[1 1[1 2]], 1[1 2[1 2]], 1[1[1 1] 2], 1[1[1 2] 1], 1[1 1 2],
2[1 2[1 2]], 2[1[1 1] 2], 2[1 1 2],
1[1 2[2 3]], 1[1 3[2 3]], 1[1[1 2] 3], 1[1[1 3] 2], 1[1 2 3],
2[1 2[2 3]], 2[1[1 3] 2], 2[2 3[1 3]], 2[2[1 2] 3], 2[1 2 3],
3[1 3[2 3]], 3[1[1 2] 3], 3[2 3[1 3]], 3[2[1 2] 3], 3[1 2 3].

Cf. A053492, A052894, A262671.

A301935 Number of positive subset-sum trees whose composite a positive subset-sum of the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 2, 1, 3, 1, 10, 2, 3, 1, 21, 1, 3, 3, 58, 1, 21, 1, 21, 3, 3, 1, 164, 2, 3, 10, 21, 1, 34, 1, 373, 3, 3, 3, 218, 1, 3, 3, 161, 1, 7, 1, 5, 5, 3, 1, 1320, 2, 5, 3, 5, 1, 7, 3, 7, 3, 3, 1, 7, 1, 3, 4, 2558, 3, 7, 1, 5, 3, 6, 1, 7

Offset: 1

Gus Wiseman, Mar 28 2018

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k). A positive subset-sum tree with root x is either the symbol x itself, or is obtained by first choosing a positive subset-sum x <= (y_1,...,y_k) with k > 1 and then choosing a positive subset-sum tree with root y_i for each i = 1...k. The composite of a positive subset-sum tree is the positive subset-sum x <= g where x is the root sum and g is the multiset of leaves. We write positive subset-sum trees in the form rootsum(branch,...,branch). For example, 4(1(1,3),2,2(1,1)) is a positive subset-sum tree with composite 4(1,1,1,2,3) and weight 8.

Gus Wiseman, The a(12) = 21 positive subset-sum trees.

Cf. A000108, A000712, A108917, A122768, A262671, A262673, A275972, A276024, A284640, A299701, A301854, A301855, A301856, A301934.

A316223 Number of subset-sum triangles with composite a subset-sum of the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 4, 1, 6, 1, 13, 4, 6, 1, 25, 1, 6, 6, 38, 1, 26, 1, 26, 6, 6

Offset: 1

Gus Wiseman, Jun 27 2018

A positive subset-sum is a pair (h,g), where h is a positive integer and g is an integer partition, such that some submultiset of g sums to h. A triangle consists of a root sum r and a sequence of positive subset-sums ((h_1,g_1),...,(h_k,g_k)) such that the sequence (h_1,...,h_k) is weakly decreasing and has a submultiset summing to r. The composite of a triangle is (r, g_1 + ... + g_k) where + is multiset union.

			We write positive subset-sum triangles in the form rootsum(branch,...,branch). The a(8) = 13 triangles:
  1(1(1,1,1))
  2(2(1,1,1))
  3(3(1,1,1))
  1(1(1),1(1,1))
  2(1(1),1(1,1))
  1(1(1),2(1,1))
  2(1(1),2(1,1))
  3(1(1),2(1,1))
  1(1(1,1),1(1))
  2(1(1,1),1(1))
  1(1(1),1(1),1(1))
  2(1(1),1(1),1(1))
  3(1(1),1(1),1(1))

Cf. A063834, A262671, A269134, A276024, A281113, A299701, A301934, A301935, A316219, A316220, A316222.

A301934 Number of positive subset-sum trees of weight n.

Original entry on oeis.org

1, 3, 14, 85, 586, 4331, 33545, 268521, 2204249

Offset: 1

Gus Wiseman, Mar 28 2018

A positive subset-sum tree with root x is either the symbol x itself, or is obtained by first choosing a positive subset-sum x <= (y_1,...,y_k) with k > 1 and then choosing a positive subset-sum tree with root y_i for each i = 1...k. The weight is the sum of the leaves. We write positive subset-sum trees in the form rootsum(branch,...,branch). For example, 4(1(1,3),2,2(1,1)) is a positive subset-sum tree with composite 4(1,1,1,2,3) and weight 8.

			The a(3) = 14 positive subset-sum trees:
3           3(1,2)       3(1,1,1)     3(1,2(1,1))
2(1,2)      2(1,1,1)     2(1,1(1,1))  2(1(1,1),1)  2(1,2(1,1))
1(1,2)      1(1,1,1)     1(1,1(1,1))  1(1(1,1),1)  1(1,2(1,1))

Cf. A000108, A000712, A108917, A122768, A262671, A262673, A275972, A276024, A284640, A299701, A301854, A301855, A301856, A301935.

A316222 Number of positive subset-sum triangles whose composite is a positive subset-sum of an integer partition of n.

Original entry on oeis.org

1, 5, 20, 74, 258, 855, 2736, 8447

Offset: 1

Gus Wiseman, Jun 27 2018

A positive subset-sum is a pair (h,g), where h is a positive integer and g is an integer partition, such that some submultiset of g sums to h. A triangle consists of a root sum r and a sequence of positive subset-sums ((h_1,g_1),...,(h_k,g_k)) such that the sequence (h_1,...,h_k) is weakly decreasing and has a submultiset summing to r.

			We write positive subset-sum triangles in the form rootsum(branch,...,branch). The a(2) = 5 positive subset-sum triangles:
  2(2(2))
  1(1(1,1))
  2(2(1,1))
  1(1(1),1(1))
  2(1(1),1(1))

Cf. A063834, A262671, A269134, A276024, A281113, A301934, A301935, A316219, A316220.

cp's OEIS Frontend

A276024 Number of positive subset sums of integer partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

A080108 a(n) = Sum_{k=1..n} k^(n-k)*binomial(n-1,k-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

A255397 Number of multimin-partitions of normal multisets of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A185298 Expansion of e.g.f. x*exp(x)*exp(x*exp(x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A262673 Number of pointed trees on normal pointed multisets of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A301935 Number of positive subset-sum trees whose composite a positive subset-sum of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Links

Crossrefs

A316223 Number of subset-sum triangles with composite a subset-sum of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A301934 Number of positive subset-sum trees of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

A316222 Number of positive subset-sum triangles whose composite is a positive subset-sum of an integer partition of n.

Views

A185298 Expansion of e.g.f. xexp(x)exp(x*exp(x)).