A196545 -id:A196545 - cp's OEIS frontend

A301470 Signed recurrence over enriched r-trees: a(n) = (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.

1, 0, 1, 0, 1, 1, 2, 3, 5, 9, 15, 27, 47, 87, 155, 288, 524, 983, 1813, 3434, 6396, 12174, 22891, 43810, 82925, 159432, 303559, 585966, 1121446, 2171341, 4172932, 8106485, 15635332, 30445899, 58925280, 115014681, 223210718, 436603718, 849480835, 1664740873

Offset: 0

Gus Wiseman, Mar 21 2018

nonn

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

Cf. A032305, A055277, A093637, A127524, A196545, A220418, A273866, A273873, A289501, A290261, A290971, A301342-A301345, A301364-A301368, A301422, A301462, A301467, A301469.

b:= proc(n, i) option remember; `if`(n=0, 1,
     `if`(i<1, 0, b(n, i-1)+a(i)*b(n-i, min(n-i, i))))
    end:
a:= n-> `if`(n<2, 1-n, b(n-2$2)+b(n-1, n-2)):
seq(a(n), n=0..45);  # Alois P. Heinz, Jun 23 2018

a[n_]:=a[n]=(-1)^n+Sum[Times@@a/@y,{y,IntegerPartitions[n-1]}];
Array[a,30]
(* Second program: *)
b[n_, i_] := b[n, i] = If[n == 0, 1,
     If[i < 1, 0, b[n, i - 1] + a[i] b[n - i, Min[n - i, i]]]];
a[n_] := If[n < 2, 1 - n, b[n - 2, n - 2] + b[n - 1, n - 2]];
a /@ Range[0, 45] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

O.g.f.: 1/(1 + x) + x Product_{i > 0} 1/(1 - a(i) x^i).

a(n) = Sum_t (-1)^w(t) where the sum is over all enriched r-trees of size n and w(t) is the sum of leaves of t.

A302094 Number of relatively prime or monic twice-partitions of n.

Original entry on oeis.org

1, 3, 6, 10, 27, 35, 113, 170, 396, 641, 1649, 2318, 5905, 9112, 18678, 32529, 69094, 106210, 227480, 363433, 705210, 1196190, 2325023, 3724233, 7192245, 11915884, 21857887, 36597843, 67406158, 109594872, 201747847, 333400746, 591125465, 987069077, 1743223350

Offset: 1

Gus Wiseman, Apr 15 2018

nonn

A relatively prime or monic partition of n is an integer partition of n that is either of length 1 (monic) or whose parts have no common divisor other than 1 (relatively prime). Then a relatively prime or monic twice-partition of n is a choice of a relatively prime or monic partition of each part in a relatively prime or monic partition of n.

			The a(4) = 10 relatively prime or monic twice-partitions:
(4), (31), (211), (1111),
(3)(1), (21)(1), (111)(1),
(2)(1)(1), (11)(1)(1),
(1)(1)(1)(1).

A. David Christopher and M. Davamani Christober, Relatively Prime Uniform Partitions, Gen. Math. Notes, Vol. 13, No. 2, December, 2012, pp. 1-12.

Cf. A000837, A001383, A063834, A093637, A196545, A281113, A289501, A300383, A300486, A301462, A301467, A301480, A302915, A302916, A302917.

ip[n_]:=ip[n]=Select[IntegerPartitions[n],Or[Length[#]===1,GCD@@#===1]&];
Table[Sum[Times@@Length/@ip/@ptn,{ptn,ip[n]}],{n,10}]

A302915 Number of relatively prime enriched p-trees of weight n.

Original entry on oeis.org

1, 2, 4, 8, 28, 56, 256, 656, 2480, 6688, 30736, 73984, 366560, 1006720, 3966976, 12738560, 58427648, 148069632, 764473600, 2133585664, 8939502080, 28705390592, 136987259648, 356634376704, 1780025034240, 5455065263104, 23215437079552, 73123382895616

Offset: 1

Gus Wiseman, Apr 15 2018

nonn

A relatively prime enriched p-tree of weight n is either a single node of weight n, or a finite sequence of two or more relatively prime enriched p-trees whose weights are weakly decreasing, relatively prime, and sum to n.

			The a(4) = 8 relatively prime enriched p-trees are 4, (31), ((21)1), (((11)1)1), ((111)1), (211), ((11)11), (1111). Missing from this list are the enriched p-trees ((11)(11)), ((11)2), (2(11)), (22).

Cf. A000081, A000837, A003238, A004111, A055277, A093637, A196545, A289501, A290689, A300486, A301462, A301467, A302094, A302916, A302917.

a[n_]:=a[n]=1+Sum[Times@@a/@y,{y,Rest[Select[IntegerPartitions[n],Or[Length[#]===1,GCD@@#===1]&]]}];
Array[a,20]

A302916 Number of relatively prime p-trees of weight n.

Original entry on oeis.org

1, 1, 2, 4, 11, 22, 74, 174, 530, 1302, 4713, 10639, 40877, 101795, 325609, 925733, 3432819, 8078511, 32542036, 82226383, 279096823, 795532677, 3066505569, 7374764180, 28946183035, 79313174765, 275507514909, 772692247626, 3049937788372, 7071057261148

Offset: 1

Gus Wiseman, Apr 15 2018

nonn

A relatively prime p-tree of weight n is either a single node, or a finite sequence of two or more relatively prime p-trees whose weights are weakly decreasing, relatively prime, and sum to n.

			The a(4) = 4 relatively prime p-trees are (((oo)o)o), ((ooo)o), ((oo)oo), (oooo). Missing from this list is the p-tree ((oo)(oo)).

Cf. A000081, A000837, A003238, A004111, A055277, A093637, A196545, A289501, A290689, A300486, A301462, A301467, A302094, A302915, A302917.

a[n_]:=a[n]=If[n===1,1,Sum[Times@@a/@y,{y,Rest[Select[IntegerPartitions[n],Or[Length[#]===1,GCD@@#===1]&]]}]];
Array[a,20]

A302917 Solution to a(1) = 1 and Sum_y Product_i a(y_i) = 0 for each n > 1, where the sum is over all relatively prime or monic partitions of n.

Original entry on oeis.org

1, -1, 0, 0, -1, 0, 0, 0, 0, 0, -1, 1, -1, -1, 1, 1, -1, -1, 0, 1, 1, -3, 1, 4, -5, -3, 3, 4, 2, -6, -6, 19, -8, -25, 25, 20, -12, -34, 2, 30, 38, -117, 54, 159, -173, -123, 55, 229, 32, -250, -148, 753, -365, -1022, 840, 1121, -847, -1482, -390, 2099

Offset: 1

Gus Wiseman, Apr 15 2018

sign

A relatively prime or monic partition of n is an integer partition of n that is either of length 1 (monic) or whose parts have no common divisor other than 1 (relatively prime).

Cf. A000837, A036987, A047966, A063834, A093637, A196545, A220418, A289501, A290261, A300486, A300863-A300866, A301462, A302094, A302915, A302916.

a[n_]:=a[n]=If[n===1,1,0]-Sum[Times@@a/@y,{y,Rest[Select[IntegerPartitions[n],Or[Length[#]===1,GCD@@#===1]&]]}];
Array[a,20]

A318847 Number of tree-partitions of a multiset whose multiplicities are the prime indices of n.

Original entry on oeis.org

1, 1, 2, 2, 4, 6, 12, 8, 28, 20, 32, 38, 112, 76, 116, 58, 352, 236, 1296, 176, 540, 288, 4448, 374, 612, 1144, 1812, 824, 16640, 1316, 59968, 612, 2336, 4528, 3208, 2924, 231168, 18320, 10632, 2168, 856960, 7132, 3334400, 3776, 11684, 74080, 12679424, 4919, 19192

Offset: 1

Gus Wiseman, Sep 04 2018

nonn

This multiset is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.

A tree-partition of m is either m itself or a sequence of tree-partitions, one of each part of a multiset partition of m with at least two parts.

			The a(6) = 6 tree-partitions of {1,1,2}:
  (112)
  ((1)(12))
  ((2)(11))
  ((1)(1)(2))
  ((1)((1)(2)))
  ((2)((1)(1)))

Cf. A000311, A001055, A196545, A281118, A281119, A305936, A318762, A318812, A318813, A318846, A318848.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
allmsptrees[m_]:=Prepend[Join@@Table[Tuples[allmsptrees/@p],{p,Select[mps[m],Length[#]>1&]}],m];
Table[Length[allmsptrees[nrmptn[n]]],{n,20}]

a(n) = A281118(A181821(n)).
a(prime(n)) = A289501(n).
a(2^n) = A005804(n).

More terms from Jinyuan Wang, Jun 26 2020

A276687 Number of prime plane trees of weight prime(n).

Original entry on oeis.org

1, 1, 2, 4, 11, 30, 122, 336, 1412, 15129, 44561, 417542, 2479120, 7540843, 35983502, 451454834, 5313515136, 16809858904, 190077477328, 1124302066470, 3521811953565, 38563707677633, 240966297786218, 3192420711942298, 95433674596402663, 567734580765228356

Offset: 1

Gus Wiseman, Sep 13 2016

nonn

A prime plane tree is either (case 1) a prime number, or (case 2) a sequence of prime plane trees whose weights are an integer partition of a prime number, where the weight of a tree is the sum of weights of its branches. Prime plane trees are "multichains" in the multiorder of integer partitions of prime numbers into prime parts (A056768).

			The a(5) = 11 prime plane trees of weight A000040(5) = 11 are: {11, (3,3,5), (3,3,(2,3)), (2,2,7), (2,2,(2,5)), (2,2,(2,(2,3))), (2,2,(2,2,3)), (2,3,3,3), (2,2,2,5), (2,2,2,(2,3)), (2,2,2,2,3)}.

Alois P. Heinz, Table of n, a(n) for n = 1..681
Gus Wiseman, Comcategories and Multiorders, (pdf version)

Cf. A000040, A056768, A000607, A100118, A196545, A273873.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i=2, 0,
       b(n, prevprime(i)))+`if`(i>n, 0, b(n-i, i)*(1+
      `if`(i>2, b(i, prevprime(i)), 0))))
    end:
a:= n-> `if`(n<3, 1, 1+b(ithprime(n), ithprime(n-1))):
seq(a(n), n=1..40);  # Alois P. Heinz, Sep 15 2016

n=20;
ser=Product[1/(1-c[Prime[i]]*x^Prime[i]),{i,1,n}];
sys=Table[c[Prime[i]]==Expand[SeriesCoefficient[ser,{x,0,Prime[i]}]-c[Prime[i]]+1],{i,1,n}];
Block[{c},Set@@@sys]

A294019 Number of same-trees whose leaves are the parts of the integer partition with Heinz number n.

Original entry on oeis.org

0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 0, 0, 2, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 3, 1, 0, 0, 2, 1, 0, 1, 0, 0, 0, 1, 3, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 2, 3, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 2, 0, 1, 4, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 8

Offset: 1

Gus Wiseman, Feb 07 2018

nonn

By convention a(1) = 0.

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			The a(108) = 8 same-trees: ((22)(2(11))), ((22)((11)2)), ((2(11))(22)), (((11)2)(22)), (222(11)), (22(11)2), (2(11)22), ((11)222).
From _Antti Karttunen_, Sep 22 2018: (Start)
For 12 = prime(1)^2 * prime(2)^1, we have the following two cases: 2(11) and (11)2, thus a(12) = 2.
For 36 = prime(1)^2 * prime(2)^2, we have the following cases: (11)22, 2(11)2, 22(11), thus a(36) = 3.
For 144  = prime(1)^4 * prime(2)^2, we have the following 14 cases: (1111)(22), (22)(1111); ((11)(11))(22), (22)((11)(11)); (11)(11)22, (11)2(11)2, (11)22(11), 2(11)2(11), 2(11)(11)2, 22(11)(11); ((11)2)(11(2)), ((11)2)(2(11)), (2(11))((11)2), (2(11))(2(11)), thus a(144) = 14.
For n = 8775 = 3^3 * 5^2 * 13^1 = prime(2)^3 * prime(3)^2 * prime(6)^1, we have the following six cases: (222)(33)6, (222)6(33), (33)(222)6, (33)6(222), 6(222)(33), 6(33)(222), thus a(8775) = 6.
(End)

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000005, A000041, A000720, A001222, A006241, A056239, A063834, A196545, A215366, A273873, A281145, A289501, A296150, A299200, A299201, A299202, A299203, A294018, A294080.

nn=120;
ptns=Table[If[n===1,{},Join@@Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]],{n,nn}];
tris=Join@@Map[Tuples[IntegerPartitions/@#]&,ptns];
qci[y_]:=qci[y]=If[Length[y]===1,1,Sum[Times@@qci/@t,{t,Select[tris,And[Length[#]>1,Sort[Join@@#,Greater]===y,SameQ@@Total/@#]&]}]];
qci/@ptns

A056239(n) = { my(f); if(1==n, 0, f=factor(n); sum(i=1, #f~, f[i,2] * primepi(f[i,1]))); }
productifbalancedfactorization(v) = if(!#v, 1, my(pw=A056239(v[1]), m=1); for(i=1,#v,if(A056239(v[i])!=pw,return(0), m *= A294019(v[i]))); (m));
A294019aux(n, m, facs) = if(1==n, productifbalancedfactorization(Vec(facs)), my(s=0, newfacs); fordiv(n, d, if((d>1)&&(d<=m), newfacs = List(facs); listput(newfacs,d); s += A294019aux(n/d, m, newfacs))); (s));
A294019(n) = if(1==n,0,if(isprime(n),1,A294019aux(n, n-1, List([]))));
\\ A memoized implementation:
map294019 = Map();
A294019(n) = if(1==n,0,if(isprime(n),1,if(mapisdefined(map294019,n), mapget(map294019,n), my(v=A294019aux(n, n-1, List([]))); mapput(map294019,n,v); (v)))); \\ Antti Karttunen, Sep 22 2018

A281145(n) = Sum_{i=1..A000041(n)} a(A215366(n,i)).

a(p^n) = A006241(n) for any prime p and exponent n >= 1. - Antti Karttunen, Sep 22 2018

A300652 Number of enriched p-trees of weight 2n + 1 in which all outdegrees and all leaves are odd.

Original entry on oeis.org

1, 2, 4, 12, 40, 136, 496, 1952, 7488, 30368, 123456, 512384, 2129664, 9068672, 38391552, 165642752, 713405952, 3109135872, 13528865792, 59591322624, 261549260800, 1159547047936, 5131968999424, 22883893137408, 101851069587456, 456703499042816, 2042949493276672

Offset: 0

Gus Wiseman, Mar 10 2018

nonn

An enriched p-tree of weight n > 0 is either a single node of weight n, or a finite sequence of at least two enriched p-trees whose weights are weakly decreasing and sum to n.

			The a(3) = 12 trees:
7,
(511), (331),
((111)31), (3(111)1), ((311)11), (31111),
((111)(111)1), (((111)11)11), ((11111)11), ((111)1111), (1111111).

Andrew Howroyd, Table of n, a(n) for n = 0..500

Cf. A000009, A000041, A063834, A196545, A273873, A281145, A289501, A298118, A300352, A300353, A300354, A300436, A300439, A300442, A300443, A300574, A300797.

r[n_]:=r[n]=If[OddQ[n],1,0]+Sum[Times@@r/@y,{y,Select[IntegerPartitions[n],Length[#]>1&&OddQ[Length[#]]&]}];
Table[r[n],{n,1,40,2}]

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + polcoef(1/prod(k=1, n-1, 1 - v[k]*x^(2*k-1) + O(x^(2*n))) - 1/prod(k=1, n-1, 1 + v[k]*x^(2*k-1) + O(x^(2*n))), 2*n-1)/2); v} \\ Andrew Howroyd, Aug 26 2018

a(n) = (1 - (-1)^n)/2 + Sum_y Product_{i in y} a(i) where the sum is over all non-singleton integer partitions of n with an odd number of parts.

A300797 Number of strict trees of weight 2n + 1 in which all outdegrees and all leaves are odd.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 11, 17, 34, 59, 118, 213, 424, 799, 1606, 3072, 6216, 12172, 24650, 48710, 99333, 198237, 405526, 815267, 1673127, 3387165, 6974702, 14179418, 29285048, 59841630, 123848399, 253927322, 526936694, 1084022437, 2253778793, 4649778115

Offset: 0

Gus Wiseman, Mar 13 2018

nonn

A strict tree of weight n > 0 is either a single node of weight n, or a sequence of two or more strict trees with strictly decreasing weights summing to n.

			The a(7) = 6 strict trees: 15, (11 3 1), (9 5 1), (7 5 3), ((7 3 1) 3 1), ((5 3 1) 5 1).

Andrew Howroyd, Table of n, a(n) for n = 0..500

Cf. A000009, A000992, A032305, A063834, A078408, A089259, A196545, A273873, A279785, A289501, A298118, A300301, A300352, A300353, A300436, A300439, A300440, A300652.

a[n_]:=a[n]=If[OddQ[n],1,0]+Sum[Times@@a/@ptn,{ptn,Select[IntegerPartitions[n],Length[#]>1&&OddQ[Length[#]]&&UnsameQ@@#&]}];
Table[a[n],{n,1,60,2}]

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + polcoef(prod(k=1, n-1, 1 + v[k]*x^(2*k-1) + O(x^(2*n))) - prod(k=1, n-1, 1 - v[k]*x^(2*k-1) + O(x^(2*n))), 2*n-1)/2); v} \\ Andrew Howroyd, Aug 26 2018

a(30)-a(37) from Alois P. Heinz, Mar 13 2018

cp's OEIS Frontend

A301470 Signed recurrence over enriched r-trees: a(n) = (-1)^n + Sum_y Product_{i in y} a(y) where the sum is over all integer partitions of n - 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A302094 Number of relatively prime or monic twice-partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A302915 Number of relatively prime enriched p-trees of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A302916 Number of relatively prime p-trees of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A302917 Solution to a(1) = 1 and Sum_y Product_i a(y_i) = 0 for each n > 1, where the sum is over all relatively prime or monic partitions of n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A318847 Number of tree-partitions of a multiset whose multiplicities are the prime indices of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

Extensions

A276687 Number of prime plane trees of weight prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A294019 Number of same-trees whose leaves are the parts of the integer partition with Heinz number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI