A000081 -id:A000081 - cp's OEIS frontend

A242353 Number T(n,k) of two-colored rooted trees of order n and structure k; triangle T(n,k), n>=1, 1<=k<=A000081(n), read by rows.

2, 4, 8, 6, 16, 12, 16, 8, 32, 24, 32, 16, 32, 24, 20, 24, 10, 64, 48, 64, 32, 64, 48, 40, 48, 20, 64, 48, 64, 32, 64, 48, 48, 36, 40, 32, 12, 128, 96, 128, 64, 128, 96, 80, 96, 40, 128, 96, 128, 64, 128, 96, 96, 72, 80, 64, 24, 128, 96, 128, 64, 128, 96, 80

Offset: 1

Martin Paech, May 11 2014

The underlying partitions of n-1 (cf. A000041) for the construction of the trees with n nodes are generated in descending order, the elements within a partition are sorted in ascending order, e.g.,
n = 1
  {0} |-> () |-> 10_2
n = 2
  {1} |-> (()) |-> 1100_2
n = 3
  {2} > {1, 1} |-> ((())) > (()()) |-> 111000_2 > 110100_2
n = 4
  {3} > {1, 2} > {1, 1, 1} |-> (((()))) > ((()())) > (()(())) > (()()()) |-> 11110000_2 > 11101000_2 > 11011000_2 > 11010100_2
The decimal equivalents of the binary encoded rooted trees in row n are the descending ordered elements of row n in A216648.

			Let {u, d} be a set of two colors, corresponding each with the up-spin and down-spin electrons in the underlying physical problem. (We consider each rooted tree as a cutout of the Bethe lattice in infinite dimensions.) Then for
n = 1 with A000081(1) = 1
  u(), d() are the 2 two-colored trees of the first and only structure k = 1 (sum is 2 = A038055(1)); for
n = 2 with A000081(2) = 1
  u(u()), u(d()), d(u()), d(d()) are the 4 two-colored trees of the first and only structure k = 1 (sum is 4 = A038055(2)); for
n = 3 with A000081(3) = 2
  u(u(u())), u(u(d())), u(d(u())), u(d(d())), d(u(u())), d(u(d())), d(d(u())), d(d(d())) are the 8 two-colored trees of the structure k = 1 and
  u(u()u()), u(u()d()), u(d()d()), d(u()u()), d(u()d()), d(d()d()) are the 6 two-colored trees of the structure k = 2 (sum is 14 = A038055(3)).
Triangle T(n,k) begins:
2;
4;
8,   6;
16, 12, 16,  8;
32, 24, 32, 16, 32, 24, 20, 24, 10;

G. Gruber, Entwicklung einer graphbasierten Methode zur Analyse von Hüpfsequenzen auf Butcherbäumen und deren Implementierung in Haskell, Diploma thesis, Marburg, 2011
Eva Kalinowski, Mott-Hubbard-Isolator in hoher Dimension, Dissertation, Marburg: Fachbereich Physik der Philipps-Universität, 2002.

Martin Paech, Rows n = 1..14, flattened
E. Kalinowski and W. Gluza, Evaluation of High Order Terms for the Hubbard Model in the Strong-Coupling Limit, arXiv:1106.4938, 2011 (Physical Review B 85, 045105, Jan 2012)
E. Kalinowski and M. Paech, Table of two-colored Butcher trees B(n,k,m) up to order n = 5.
M. Paech, A sonification of this sequence, created with MUSICALGORITHMS, using simple 'division operation' instead of modulo scaling (3047 elements, 240 bpm).
M. Paech, E. Kalinowski, W. Apel, G. Gruber, R. Loogen, and E. Jeckelmann, Ground-state energy and beyond: High-accuracy results for the Hubbard model on the Bethe lattice in the strong-coupling limit, DPG Spring Meeting, Berlin, TT 45.91 (2012)

Row sums give A038055.
Row length is A000081.
Total number of elements up to and including row n is A087803.
Cf. A216648.

A336039 Numbers k such that A000081(k) is divisible by k.

Original entry on oeis.org

1, 4, 24, 72, 121, 475, 8744, 19933, 38357, 41685

Offset: 1

Vaclav Kotesovec, Jul 07 2020

No other terms below 100000. - Mathieu Gouttenoire, Nov 01 2021

			24 is in the sequence because A000081(24) = 24 * 30988541.
72 is in the sequence because A000081(72) = 72 * 77434098197798038469129694128.

Cf. A000081, A051420, A336042.

a(10) from Mathieu Gouttenoire, Nov 01 2021

A051529 INVERT transform of A000081 = [1, 1, 1, 2, 4, 9, 20, 48, 115, 286,...].

Original entry on oeis.org

1, 2, 4, 9, 21, 51, 126, 318, 812, 2100, 5482, 14438, 38303, 102302, 274824, 742210, 2013941, 5488239, 15014376, 41221775, 113542455, 313681756, 868994723, 2413526848, 6719132105, 18746838609, 52412080624, 146812972155, 411977724704, 1158006098132

Offset: 0

N. J. A. Sloane

nonn

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

Cf. A000081, A000107.

with(numtheory): b:= proc(n) option remember; local d, j; `if`(n<=1, 1, (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1)) end: a:= proc(n) option remember; local i; `if`(n<1, 1, add(a(n-i) *b(i-1), i=1..n+1)) end: seq(a(n), n=0..30);  # Alois P. Heinz, Apr 01 2009

b[n_] := b[n] = If[n <= 1, 1, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n - j], {j, 1, n - 1}])/ (n - 1)];
a[n_] := a[n] = If[n < 1, 1, Sum[a[n - i]*b[i - 1], {i, 1, n + 1}]];
a /@ Range[0, 30] (* Jean-François Alcover, Mar 01 2021, after Alois P. Heinz *)

A051784 Apply the "Stirling-Bernoulli transform" to A000081 = (1,1,1,2,4,9,20,...), rooted trees.

Original entry on oeis.org

1, 0, 0, -6, 12, -270, 1500, -43806, 302652, -12857550, 132059100, -5733723006, 89592628092, -3922345875630, 79865827177500, -3844579915776606, 95745315867430332, -4957995149918778510, 151156611852387524700, -8193660691162420044606, 298062602379028314213372

Offset: 0

N. J. A. Sloane, Dec 09 1999

sign

The "Stirling-Bernoulli transform" maps a sequence b_0, b_1, b_2, ... to a sequence c_0, c_1, c_2, ..., where if B has o.g.f. B(x), c has e.g.f. exp(x)*B(1-exp(x)).

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

with(numtheory):
b:= proc(n) option remember; local d, j; `if` (n<3, 1,
      (add(add(d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
    end:
a:= n-> add((-1)^k *k! *Stirling2(n+1, k+1)*b(k), k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, May 17 2013

b[n_] := b[n] = Module[{d, j}, If[n < 3, 1, Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}]/(n-1)]]; a[n_] := Sum[(-1)^k*k!*StirlingS2[n+1, k+1]*b[k], {k, 0, n}]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jul 01 2014, after Alois P. Heinz *)

A074797 a(n) = A000081(n+1) - 2*A000081(n).

Original entry on oeis.org

1, 2, 8, 19, 56, 147, 404, 1082, 2954, 8001, 21865, 59759, 164085, 451465, 1246358, 3448876, 9569376, 26611517, 74172493, 207159274, 579724677, 1625287220, 4564461309, 12839597611, 36172421770, 102053738981, 288317817804, 815591326704, 2309951078955

Offset: 4

Alford Arnold, Sep 07 2002

Counts exceptional non-overlapping circles. These circles are exceptional because they are neither generated by encircling any case at level n-1 nor do they result from appending an external circle to any case at level n-1. When n=4 the case is (())(()).

			a(8) = 56 because we can write A000081(9) - 2*A000081(8) = 286 - 2*115.
a(8) also = 56 because we know that 8=6+2=5+3=4+4=4+2+2=3+3+2=2+2+2+2 and these partitions contribute 20*1 + 9*2 + 4*5/2 + 4 + 3 + 1 cases.

Alois P. Heinz, Table of n, a(n) for n = 4..1000

Cf. A000081.

with(numtheory):
b:= proc(n) option remember; local d, j; `if` (n<2, n,
      (add(add(d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1))
    end:
a:= n-> b(n+1)-2*b(n):
seq(a(n), n=4..50);  # Alois P. Heinz, May 16 2013

a81[1] = 1; a81[n_] := a81[n] = Sum[a81[n-k]*DivisorSum[k, #*a81[#]&], {k, 1, n-1}]/(n-1); a[n_] := a81[n+1] - 2*a81[n]; Table[a[n], {n, 4, 50}] (* Jean-François Alcover, Jan 08 2016 *)

More terms from Sascha Kurz, Feb 10 2003

A124682 a(n) = A002861(n) + A000081(n).

Original entry on oeis.org

2, 3, 6, 13, 29, 71, 173, 444, 1148, 3030, 8059, 21715, 58836, 160687, 441083, 1217134, 3372386, 9380948, 26180962, 73292358, 205731862, 578922864, 1632707684, 4614098810, 13064064882, 37052720050, 105257568244, 299452309023, 853094139960, 2433439189419

Offset: 1

N. J. A. Sloane, Dec 26 2006

nonn

See A126285.

A242354 Number T(n,k) of four-colored rooted trees of order n and structure k; triangle T(n,k), n>=1, 1<=k<=A000081(n), read by rows.

Original entry on oeis.org

4, 16, 64, 40, 256, 160, 256, 80, 1024, 640, 1024, 320, 1024, 640, 544, 640, 140, 4096, 2560, 4096, 1280, 4096, 2560, 2176, 2560, 560, 4096, 2560, 4096, 1280, 4096, 2560, 2560, 1600, 2176, 1280, 224, 16384, 10240, 16384, 5120, 16384, 10240, 8704, 10240, 2240

Offset: 1

Martin Paech, May 16 2014

The underlying partitions of n-1 (cf. A000041) for the construction of the trees with n nodes are generated in descending order, the elements within a partition are sorted in ascending order, e.g.,
n = 1
  {0} |-> () |-> 10_2
n = 2
  {1} |-> (()) |-> 1100_2
n = 3
  {2} > {1, 1} |-> ((())) > (()()) |-> 111000_2 > 110100_2
n = 4
  {3} > {1, 2} > {1, 1, 1} |-> (((()))) > ((()())) > (()(())) > (()()()) |-> 11110000_2 > 11101000_2 > 11011000_2 > 11010100_2
The decimal equivalents of the binary encoded rooted trees in row n are the descending ordered elements of row n in A216648.

			Let {h, u, d, p} be a set of four colors, corresponding to the four possible "states" of each tree node (lattice site) in the underlying physical problem, namely its occupation with no electron (hole), with one up-spin electron, with one down-spin electron, or with one up-spin and one down-spin electron (pair). (We consider each rooted tree as a cutout of the Bethe lattice in infinite dimensions.) Then for
n = 1 with A000081(1) = 1
  h(), u(), d(), p() are the 4 four-colored trees of the first and only structure k = 1 (sum is 4 = A136793(1)); for
n = 2 with A000081(2) = 1
  h(h()), h(u()), h(d()), h(p()),
  u(h()), u(u()), u(d()), u(p()),
  d(h()), d(u()), d(d()), d(p()),
  p(h()), p(u()), p(d()), p(p()) are the 16 four-colored trees of the first and only structure k = 1 (sum is 16 = A136793(2)); for
n = 3 with A000081(3) = 2
  h(h(h())), h(h(u())), h(h(d())), h(h(p())),
  h(u(h())), ...
                              ..., p(d(p())),
  p(p(h())), p(p(u())), p(p(d())), p(p(p())) are the 64 four-colored trees of the structure k = 1 and
  h(h()h()), h(h()u()), h(h()d()), h(h()p()),
  h(u()u()), h(u()d()), h(u()p()),
  h(d()d()), h(d()p()),
  h(p()p()),
  ...,
  p(h()h()), p(h()u()), p(h()d()), p(h()p()),
  p(u()u()), p(u()d()), p(u()p()),
  p(d()d()), p(d()p()),
  p(p()p()) are the 40 four-colored trees of the structure k = 2 (sum is 104 = A136793(3)).
Triangle T(n,k) begins:
4;
16;
64, 40;
256, 160, 256, 80;
1024, 640, 1024, 320, 1024, 640, 544, 640, 140;

G. Gruber, Entwicklung einer graphbasierten Methode zur Analyse von Hüpfsequenzen auf Butcherbäumen und deren Implementierung in Haskell, Diploma thesis, Marburg, 2011
Eva Kalinowski, Mott-Hubbard-Isolator in hoher Dimension, Dissertation, Marburg: Fachbereich Physik der Philipps-Universität, 2002.

Martin Paech, Rows n = 1..10, flattened
E. Kalinowski and W. Gluza, Evaluation of High Order Terms for the Hubbard Model in the Strong-Coupling Limit, arXiv:1106.4938, 2011 (Physical Review B 85, 045105, Jan 2012)
E. Kalinowski and M. Paech, Table of four-colored Butcher trees B(n,k,m) up to order n = 4.
M. Paech, E. Kalinowski, W. Apel, G. Gruber, R. Loogen, and E. Jeckelmann, Ground-state energy and beyond: High-accuracy results for the Hubbard model on the Bethe lattice in the strong-coupling limit, DPG Spring Meeting, Berlin, TT 45.91 (2012)

Row sums give A136793.
Row length is A000081.
Total number of elements up to and including row n is A087803.
Cf. A216648, A242353.

A244519 Expansion of Product_{n>=1} (1 + H(x^n)) where H(x) is the g.f. of A000081.

Original entry on oeis.org

1, 1, 2, 4, 8, 16, 35, 76, 175, 414, 1009, 2510, 6382, 16448, 42961, 113352, 301715, 808932, 2182739, 5921803, 16143975, 44199809, 121477237, 335015538, 926814691, 2571322157, 7152404733, 19942874638, 55729271645, 156051344975, 437801148097, 1230423785329, 3463777894236, 9766002585763, 27574869734583, 77965430442158

Offset: 0

Joerg Arndt, Jul 10 2014

nonn

Which combinatorial objects does this sequence count?

Joerg Arndt, Table of n, a(n) for n = 0..500

Cf. A001372 (expansion of 1/Product_{n>=1} (1 - H(x^n))).

N=66;  A=vector(N+1, j, 1);
for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, d * A[d]) * A[n-k+1] ) );
A000081=concat([0], A);
H(t)=subst(Ser(A000081, 't), 't, t);
x='x+O('x^N);
T=prod(n=1,N, 1 + H(x^n));
Vec(T)

A275330 Triangle read by rows, T(n,k) = t(n-k+1)Sum_{d|k} dt(d) with t = A000081, for n>=1 and 1<=k<=n.

Original entry on oeis.org

1, 1, 3, 2, 3, 7, 4, 6, 7, 19, 9, 12, 14, 19, 46, 20, 27, 28, 38, 46, 129, 48, 60, 63, 76, 92, 129, 337, 115, 144, 140, 171, 184, 258, 337, 939, 286, 345, 336, 380, 414, 516, 674, 939, 2581, 719, 858, 805, 912, 920, 1161, 1348, 1878, 2581, 7238

Offset: 1

Peter Luschny, Aug 18 2016

			Table starts:
[n] [k=1,2,...] row sum
[1] [1] 1
[2] [1, 3] 4
[3] [2, 3, 7] 12
[4] [4, 6, 7, 19] 36
[5] [9, 12, 14, 19, 46] 100
[6] [20, 27, 28, 38, 46, 129] 288
[7] [48, 60, 63, 76, 92, 129, 337] 805
[8] [115, 144, 140, 171, 184, 258, 337, 939] 2288
[9] [286, 345, 336, 380, 414, 516, 674, 939, 2581] 6471

T(n,0) = A000081(n).
T(n,n) = A209397(n).
Sum_k T(n,k) = A095350(n+1).
Cf. A275331.

@cached_function
def t():
    n = 1
    b = [0,1]
    while True:
        S = [b[n-k+1]*sum(d*b[d] for d in divisors(k)) for k in (1..n)]
        b.append(sum(S)//n)
        yield S
        n += 1
t_list = t()
for n in (1..12): print(next(t_list))

A275331 Triangle read by rows, T(n,k) = kSum_{m=1..n/k} t(k)t(n-k*m+1) with t = A000081, for n>=1 and 1<=k<=n.

Original entry on oeis.org

1, 2, 2, 4, 2, 6, 8, 6, 6, 16, 17, 10, 12, 16, 45, 37, 24, 30, 32, 45, 120, 85, 50, 60, 64, 90, 120, 336, 200, 120, 132, 160, 180, 240, 336, 920, 486, 280, 318, 336, 405, 480, 672, 920, 2574, 1205, 692, 750, 800, 945, 1080, 1344, 1840, 2574, 7190

Offset: 1

Peter Luschny, Aug 18 2016

			Triangle starts:
[n] [k=1,2,...] row sum
[1] [1] 1
[2] [2, 2] 4
[3] [4, 2, 6] 12
[4] [8, 6, 6, 16] 36
[5] [17, 10, 12, 16, 45] 100
[6] [37, 24, 30, 32, 45, 120] 288
[7] [85, 50, 60, 64, 90, 120, 336] 805
[8] [200, 120, 132, 160, 180, 240, 336, 920] 2288
[9] [486, 280, 318, 336, 405, 480, 672, 920, 2574] 6471

T(n,0) = A087803(n).
T(n,n) = A055544(n).
Sum_k T(n,k) = A095350(n+1).
Cf. A000081, A275330.

@cached_function
def t():
    n = 1
    b = [0,1]
    while True:
        S = [k*sum(b[k]*b[n-k*m+1] for m in (1..n//k)) for k in (1..n)]
        b.append(sum(S)//n)
        yield S
        n += 1
t_list = t()
for n in (1..8): print(next(t_list))

cp's OEIS Frontend

A242353 Number T(n,k) of two-colored rooted trees of order n and structure k; triangle T(n,k), n>=1, 1<=k<=A000081(n), read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A336039 Numbers k such that A000081(k) is divisible by k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A051529 INVERT transform of A000081 = [1, 1, 1, 2, 4, 9, 20, 48, 115, 286,...].

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

A051784 Apply the "Stirling-Bernoulli transform" to A000081 = (1,1,1,2,4,9,20,...), rooted trees.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

A074797 a(n) = A000081(n+1) - 2*A000081(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A124682 a(n) = A002861(n) + A000081(n).

Views

Author

Keywords

Crossrefs

A242354 Number T(n,k) of four-colored rooted trees of order n and structure k; triangle T(n,k), n>=1, 1<=k<=A000081(n), read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A244519 Expansion of Product_{n>=1} (1 + H(x^n)) where H(x) is the g.f. of A000081.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A275330 Triangle read by rows, T(n,k) = t(n-k+1)*Sum_{d|k} d*t(d) with t = A000081, for n>=1 and 1<=k<=n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Sage

A275331 Triangle read by rows, T(n,k) = k*Sum_{m=1..n/k} t(k)*t(n-k*m+1) with t = A000081, for n>=1 and 1<=k<=n.

A275330 Triangle read by rows, T(n,k) = t(n-k+1)Sum_{d|k} dt(d) with t = A000081, for n>=1 and 1<=k<=n.

A275331 Triangle read by rows, T(n,k) = kSum_{m=1..n/k} t(k)t(n-k*m+1) with t = A000081, for n>=1 and 1<=k<=n.