A294019 - OEIS

A294019

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

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,12

COMMENTS

By convention a(1) = 0.

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

LINKS

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

FORMULA

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

EXAMPLE

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)

MATHEMATICA

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

PROG

(PARI)

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

CROSSREFS

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

Sequence in context: A280586 A112344 A294080 * A123721 A077618 A356859

Adjacent sequences: A294016 A294017 A294018 * A294020 A294021 A294022

KEYWORD

nonn

AUTHOR

Gus Wiseman, Feb 07 2018

STATUS

approved