A038046 -id:A038046 - cp's OEIS frontend

A007557 Shifts left when inverse Moebius transform applied twice.

1, 1, 3, 5, 10, 12, 24, 26, 43, 52, 78, 80, 133, 135, 189, 219, 295, 297, 428, 430, 584, 642, 804, 806, 1100, 1123, 1395, 1494, 1856, 1858, 2428, 2430, 2977, 3143, 3739, 3811, 4790, 4792, 5654, 5930, 7072, 7074, 8656

Offset: 1

N. J. A. Sloane

Equals eigensequence of triangle A127170 (the square of the inverse Mobius transform). - Gary W. Adamson, Apr 27 2009

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, arXiv:math/0205301 [math.CO], 2002; Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to arXiv version]
M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, Linear Alg. Applications, 226-228 (1995), 57-72; erratum 320 (2000), 210. [Link to Lin. Alg. Applic. version together with omitted figures]
N. J. A. Sloane, Transforms

Cf. A000005, A007554, A038045, A038046, A003238, A070965.

Cf. A127170. - Gary W. Adamson, Apr 27 2009

a[n_] := a[n] = Sum[ DivisorSigma[0, (n - 1)/d]*a[d], {d, Divisors[n - 1]}]; a[1] = 1; Table[a[n], {n, 1, 43}] (* Jean-François Alcover, Dec 12 2011, after Vladeta Jovovic *)

a(n+1) = Sum_{d divides n} tau(n/d)*a(d). - Vladeta Jovovic, Jan 24 2003
From Ilya Gutkovskiy, Apr 30 2019: (Start)
G.f. A(x) satisfies: A(x) = x * (1 + Sum_{i>=1} Sum_{j>=1} A(x^(i*j))).
G.f.: A(x) = Sum_{n>=1} a(n)*x^n = x * (1 + Sum_{i>=1} Sum_{j>=1} a(i)*x^(i*j)/(1 - x^(i*j))). (End)

More terms from Vladeta Jovovic, Jan 24 2003

A003227 Endpoints (leaves) in rooted trees with n nodes.

Original entry on oeis.org

1, 1, 3, 8, 22, 58, 160, 434, 1204, 3341, 9363, 26308, 74376, 210823, 599832, 1710803, 4891876, 14015505, 40231632, 115669419, 333052242, 960219982, 2771707332, 8009222307, 23166563032, 67069289457, 194332834601

Offset: 1

N. J. A. Sloane

nonn

Number of unlabeled rooted trees with n nodes and a distinguished leaf. - Gus Wiseman, Jul 31 2018

			The a(4) = 8 rooted trees with a distinguished leaf are (((O))), ((Oo)), ((oO)), (O(o)), (o(O)), (Ooo), (oOo), (ooO). - _Gus Wiseman_, Jul 31 2018

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. W. Robinson and A. J. Schwenk, The distribution of trees in a large random tree, Discr. Math., 12 (1975), 359-372.
Eric Weisstein's World of Mathematics, Tree Leaf.
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Cf. A000081, A003228, A004111, A038046, A055277, A317580.

urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
Table[Sum[Length[Flatten[{t/.{}->1}]],{t,urt[n]}],{n,15}] (* Gus Wiseman, Jul 31 2018 *)

a(n) = Sum_{k=1..n} k*A055277(n, k).

Corrected and extended with formula by Christian G. Bower, May 25 2000

A214575 Triangle read by rows: T(n,k) is the number of partitions of n in which each part is divisible by the next and have first part equal to k (1 <= k <= n).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 3, 2, 2, 1, 1, 1, 3, 2, 2, 1, 1, 1, 1, 4, 2, 4, 1, 2, 1, 1, 1, 4, 3, 4, 1, 3, 1, 1, 1, 1, 5, 3, 6, 2, 4, 1, 2, 1, 1, 1, 5, 3, 6, 2, 4, 1, 2, 1, 1, 1, 1, 6, 4, 9, 2, 7, 1, 4, 2, 2, 1, 1, 1, 6, 4, 9, 2, 7, 1, 4, 2, 2, 1, 1, 1, 1, 7, 4, 12, 2, 9, 2, 6, 2, 3, 1, 2, 1, 1

Offset: 1

Emeric Deutsch, Aug 18 2012

T(n,k) is also the number of generalized Bethe trees with n edges and k leaves.
A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree; they are called uniform trees in the Goldberg and Livshits reference.
There is a simple bijection between generalized Bethe trees with n edges and partitions of n in which each part is divisible by the next (the parts are given by the number of edges at the successive levels). We have the correspondences: number of edges --- sum of parts; root degree --- last part; number of leaves --- first part; height --- number of parts.
Sum of entries in row n is A003238(n+1).
Apparently, Sum(k*T(n,k), k>=1) = A038046(n+1).

			T(7,4)=2 because we have (4,2,1) and (4,1,1,1).
Triangle starts:
  1;
  1, 1;
  1, 1, 1;
  1, 2, 1, 1;
  1, 2, 1, 1, 1;
  1, 3, 2, 2, 1, 1;

Seiichi Manyama, Rows n = 1..50, flattened
M. K. Goldberg and E. M. Livshits, On minimal universal trees, Mathematical Notes of the Acad. of Sciences of the USSR, 4, 1968, 713-717 (translation from the Russian Mat. Zametki 4 1968 371-379).
O. Rojo, Spectra of weighted generalized Bethe trees joined at the root, Linear Algebra and its Appl., 428, 2008, 2961-2979.

An augmented version is A301343.

Cf. A122934, A214576.

with(numtheory): T := proc (n, k) if k = 1 then 1 elif n < k then 0 else add(T(n-k, divisors(k)[j]), j = 1 .. tau(k)) end if end proc: for n to 18 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form

T(n,1)=1; T(n,k) = Sum_{j|k}T(n-k,j); T(n,k)=0 if k>n.

A318372 a(1) = 1; a(n+1) = Sum_{d|n} d*a(d).

Original entry on oeis.org

1, 1, 3, 10, 43, 216, 1308, 9157, 73299, 659701, 6597228, 72569509, 870835456, 11320860929, 158492062165, 2377380932700, 38038094996499, 646647614940484, 11639657069589711, 221153484322204510, 4423069686450687468, 92884463415464445994, 2043458195140290381379, 46999538488226678771718

Offset: 1

Ilya Gutkovskiy, Aug 24 2018

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..450

Cf. A003238, A038046, A197953.

f:= proc(n) option remember;
add(d*procname(d),d=numtheory:-divisors(n-1))
end proc:
f(1):= 1:
map(f, [$1..30]); # Robert Israel, Aug 24 2018

a[n_] := a[n] = Sum[d a[d], {d, Divisors[n - 1]}]; a[1] = 1; Table[a[n], {n, 24}]

a(n) = if (n==1, 1, sumdiv(n-1, d, d*a(d))); \\ Michel Marcus, Aug 25 2018

L.g.f.: -log(Product_{n>=1} (1 - x^n)^a(n)) = Sum_{n>=1} a(n+1)*x^n/n.

a(n) ~ c * (n-1)!, where c = 1.818022128135673369551657167939033389270758547856526032865616543756614556559... - Vaclav Kotesovec, Aug 25 2018

A317580 Number of unlabeled rooted identity trees with n nodes and a distinguished leaf.

Original entry on oeis.org

1, 1, 1, 3, 5, 12, 28, 66, 153, 367, 880, 2121, 5127, 12441, 30248, 73746, 180077, 440571, 1079438, 2648511, 6506170, 16001256, 39393173, 97074140, 239419963, 590972968, 1459808862, 3608483107, 8925476591, 22090139751, 54702648393, 135533335933, 335967782916

Offset: 1

Gus Wiseman, Jul 31 2018

nonn

Total number of leaves in all rooted identity trees with n nodes. - Andrew Howroyd, Aug 28 2018

			The a(6) = 12 rooted identity trees with a distinguished leaf:
(((((O))))),
(((O(o)))), (((o(O)))),
((O((o)))), ((o((O)))),
(O(((o)))), (o(((O)))),
((O)((o))), ((o)((O))),
(O(o(o))), (o(O(o))), (o(o(O))).

Andrew Howroyd, Table of n, a(n) for n = 1..200

Cf. A000081, A001678, A003227, A003238, A004111, A038046, A055327, A067824, A301342, A316784.

urit[n_]:=Join@@Table[Select[Union[Sort/@Tuples[urit/@ptn]],UnsameQ@@#&],{ptn,IntegerPartitions[n-1]}];
Table[Sum[Length[Flatten[{t/.{}->1}]],{t,urit[n]}],{n,10}]

WeighMT(u)={my(n=#u, p=x*Ser(u), vars=variables(p)); Vec(exp( sum(i=1, n, (-1)^(i-1)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i ))-1)}
seq(n)={my(v=[y]); for(n=2, n, v=concat([y], WeighMT(v))); apply(p -> subst(deriv(p), y, 1), v)} \\ Andrew Howroyd, Aug 28 2018

a(n) = Sum_{k=1, n} k*A055327(n, k). - Andrew Howroyd, Aug 28 2018

Terms a(26) and beyond from Andrew Howroyd, Aug 28 2018

A317581 a(1) = 1; a(n > 1) = 1 + Sum_{d|n, d

Original entry on oeis.org

1, 0, 0, 1, 0, 2, 0, 0, 1, 2, 0, -2, 0, 2, 2, 1, 0, -2, 0, -2, 2, 2, 0, 4, 1, 2, 0, -2, 0, -6, 0, 0, 2, 2, 2, 7, 0, 2, 2, 4, 0, -6, 0, -2, -2, 2, 0, -4, 1, -2, 2, -2, 0, 4, 2, 4, 2, 2, 0, 16, 0, 2, -2, 1, 2, -6, 0, -2, 2, -6, 0, -12, 0, 2, -2, -2, 2, -6, 0, -4

Offset: 1

Gus Wiseman, Jul 31 2018

If p is prime, a(p^k) = 0 if k is odd, 1 if k is even. - Robert Israel, Aug 01 2018

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A001678, A002033, A007554, A038046, A067824.

f:= n -> 1 + add(numtheory:-mobius(n/d)*procname(d),d=numtheory:-divisors(n) minus {n}):
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Aug 01 2018

a[n_]:=1+Sum[MoebiusMu[n/d]*a[d],{d,Most[Divisors[n]]}];
Array[a,100]

from sympy import mobius, divisors
def A317581(n): return 1 + (0 if n == 1 else sum(mobius(n//d)*A317581(d) for d in divisors(n,generator=True) if d < n)) # Chai Wah Wu, Jan 14 2022

A351405 a(1) = 1; a(n+1) = Sum_{d|n} 2^(n/d - 1) * a(d).

Original entry on oeis.org

1, 1, 3, 7, 17, 33, 75, 139, 289, 557, 1119, 2143, 4341, 8437, 16843, 33343, 66573, 132109, 264243, 526387, 1052549, 2101617, 4202031, 8396335, 16792705, 33570193, 67137403, 134248191, 268492033, 536927489, 1073853307, 2147595131, 4295180241, 8590155085

Offset: 1

Ilya Gutkovskiy, Feb 10 2022

nonn

Cf. A003238, A038046, A054599, A308076.

a:= proc(n) option remember; `if`(n=1, 1,
      add(2^((n-1)/d-1)*a(d), d=numtheory[divisors](n-1)))
    end:
seq(a(n), n=1..34);  # Alois P. Heinz, Feb 10 2022

a[1] = 1; a[n_] := a[n] = Sum[2^((n - 1)/d - 1) a[d], {d, Divisors[n - 1]}]; Table[a[n], {n, 1, 34}]
nmax = 34; A[] = 0; Do[A[x] = x (1 + Sum[2^(k - 1) A[x^k], {k, 1, nmax}]) + O[x]^(nmax + 1) //Normal, nmax + 1]; CoefficientList[A[x], x] // Rest

G.f. A(x) satisfies: A(x) = x * ( 1 + A(x) + 2 * A(x^2) + 4 * A(x^3) + ... + 2^(k-1) * A(x^k) + ... ).
G.f.: x * ( 1 + Sum_{n>=1} a(n) * x^n / (1 - 2 * x^n) ).
a(n) ~ 2^(n-1). - Vaclav Kotesovec, Feb 18 2022

A307992 G.f. A(x) satisfies: A(x) = x + x^2 * (1 + A(x) + 2A(x^2) + 3A(x^3) + ...).

Original entry on oeis.org

1, 1, 1, 3, 4, 9, 9, 20, 16, 38, 28, 61, 39, 110, 52, 149, 84, 225, 101, 317, 120, 454, 175, 543, 198, 823, 243, 940, 327, 1259, 356, 1601, 387, 2051, 515, 2270, 623, 3114, 660, 3373, 829, 4381, 870, 5145, 913, 6264, 1245, 6683, 1292, 8776, 1404, 9477, 1724

Offset: 1

Ilya Gutkovskiy, May 09 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A007439, A038046, A144366, A318372.

a:= proc(n) option remember; `if`(n<3, signum(n), (m->
      m*add(a(d)/d, d=numtheory[divisors](m)))(n-2))
    end:
seq(a(n), n=1..60);  # Alois P. Heinz, May 09 2019

terms = 57; A[] = 0; Do[A[x] = x + x^2 (1 + Sum[k A[x^k], {k, 1, terms}]) + O[x]^(terms + 1) // Normal, terms + 1]; Rest[CoefficientList[A[x], x]]
a[n_] := a[n] = SeriesCoefficient[x + x^2 (1 + Sum[a[k] x^k/(1 - x^k)^2, {k, 1, n - 1}]), {x, 0, n}]; Table[a[n], {n, 1, 57}]
a[n_] := a[n] = Sum[d a[(n - 2)/d], {d, Divisors[n - 2]}]; a[1] = a[2] = 1; Table[a[n], {n, 1, 57}]

G.f.: x + x^2 * (1 + Sum_{n>=1} a(n)*x^n/(1 - x^n)^2).

a(1) = a(2) = 1; a(n+2) = Sum_{d|n} d*a(n/d).

A332753 G.f. A(x) satisfies: A(x) = x * (1 + A(x) + A(x^2)^2 + A(x^3)^3 + ...).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 4, 7, 8, 12, 12, 22, 22, 32, 38, 56, 56, 90, 90, 132, 150, 204, 204, 326, 327, 437, 489, 677, 677, 994, 994, 1361, 1499, 1943, 1958, 2889, 2889, 3733, 4078, 5445, 5445, 7549, 7549, 9969, 10853, 13733, 13733, 19329, 19330, 24577, 26404, 34080

Offset: 1

Ilya Gutkovskiy, Feb 22 2020

nonn

If n is prime or 1 then a(n) = a(n+1).

Cf. A000108, A003238, A008578, A038046.

terms = 53; A[] = 0; Do[A[x] = x (1 + Sum[A[x^k]^k, {k, 1, terms}]) + O[x]^(terms + 1) // Normal, terms + 1]; CoefficientList[A[x], x] // Rest

A338749 a(0) = 1; for n > 0, a(n) = n * Sum_{d|n, d < n} a(d - 1) / d.

Original entry on oeis.org

1, 0, 2, 3, 4, 5, 10, 7, 14, 15, 18, 11, 39, 13, 34, 37, 42, 17, 73, 19, 81, 65, 58, 23, 121, 45, 104, 87, 115, 29, 212, 31, 158, 109, 118, 113, 240, 37, 184, 182, 235, 41, 366, 43, 279, 283, 162, 47, 399, 119, 407, 211, 337, 53, 478, 189, 453, 314, 288, 59, 639

Offset: 0

Ilya Gutkovskiy, Nov 06 2020

nonn

Cf. A038046, A050369, A167865.

a[0] = 1; a[n_] := a[n] = n DivisorSum[n, a[# - 1]/# &, # < n &]; Table[a[n], {n, 0, 60}]
nmax = 60; A[] = 0; Do[A[x] = 1 + Sum[k x^k A[x^k], {k, 2, nmax}] + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

G.f. A(x) satisfies: A(x) = 1 + 2 * x^2 * A(x^2) + 3 * x^3 * A(x^3) + 4 * x^4 * A(x^4) + ...

cp's OEIS Frontend

A007557 Shifts left when inverse Moebius transform applied twice.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A003227 Endpoints (leaves) in rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A214575 Triangle read by rows: T(n,k) is the number of partitions of n in which each part is divisible by the next and have first part equal to k (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A318372 a(1) = 1; a(n+1) = Sum_{d|n} d*a(d).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A317580 Number of unlabeled rooted identity trees with n nodes and a distinguished leaf.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A317581 a(1) = 1; a(n > 1) = 1 + Sum_{d|n, d

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

A351405 a(1) = 1; a(n+1) = Sum_{d|n} 2^(n/d - 1) * a(d).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

A307992 G.f. A(x) satisfies: A(x) = x + x^2 * (1 + A(x) + 2A(x^2) + 3A(x^3) + ...).