login
Number of orderless same-trees of weight n with all leaves equal to 1.
20

%I #18 Jun 20 2020 13:28:22

%S 1,1,1,2,1,3,1,5,2,3,1,13,1,3,3,22,1,16,1,15,3,3,1,151,2,3,6,17,1,41,

%T 1,334,3,3,3,637,1,3,3,275,1,56,1,21,19,3,1,15591,2,27,3,23,1,902,3,

%U 516,3,3,1,7858,1,3,21,69109,3,98,1,27,3,67,1,811756,1

%N Number of orderless same-trees of weight n with all leaves equal to 1.

%C a(n) is also the number of orderless same-trees of weight n with all leaves greater than 1.

%H Alois P. Heinz, <a href="/A289079/b289079.txt">Table of n, a(n) for n = 1..10000</a>

%F a(1) = 1, a(n>1) = Sum_{d|n, d>1} binomial(a(n/d)+d-1, d).

%e The a(12)=13 orderless same-trees with all leaves greater than 1 are: ((33)(33)), ((33)(222)), ((33)6), ((222)(222)), ((222)6), (66), ((22)(22)(22)), ((22)(22)4), ((22)44), (444), (3333), (222222), 12.

%p with(numtheory):

%p a:= proc(n) option remember; `if`(n=1, 1, add(

%p binomial(a(n/d)+d-1, d), d=divisors(n) minus {1}))

%p end:

%p seq(a(n), n=1..80); # _Alois P. Heinz_, Jul 05 2017

%t a[n_]:=If[n===1,1,Sum[Binomial[a[n/d]+d-1,d],{d,Rest[Divisors[n]]}]];

%t Array[a,100]

%o (PARI) seq(n)={my(v=vector(n)); v[1]=1; for(n=2, n, v[n] = sumdiv(n, d, binomial(v[n/d]+d-1, d))); v} \\ _Andrew Howroyd_, Aug 20 2018

%o (Python)

%o from sympy import divisors, binomial

%o l=[0, 1]

%o for n in range(2, 101): l+=[sum([binomial(l[n//d] + d - 1, d) for d in divisors(n)[1:]]), ]

%o l[1:] # _Indranil Ghosh_, Jul 06 2017

%Y Cf. A196545, A273873, A275870, A281145, A281146, A289078.

%K nonn

%O 1,4

%A _Gus Wiseman_, Jun 23 2017