cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A242249 Number A(n,k) of rooted trees with n nodes and k-colored non-root nodes; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 2, 0, 0, 1, 3, 7, 4, 0, 0, 1, 4, 15, 26, 9, 0, 0, 1, 5, 26, 82, 107, 20, 0, 0, 1, 6, 40, 188, 495, 458, 48, 0, 0, 1, 7, 57, 360, 1499, 3144, 2058, 115, 0, 0, 1, 8, 77, 614, 3570, 12628, 20875, 9498, 286, 0, 0, 1, 9, 100, 966, 7284, 37476, 111064, 142773, 44947, 719, 0
Offset: 0

Views

Author

Alois P. Heinz, May 09 2014

Keywords

Comments

From Vaclav Kotesovec, Aug 26 2014: (Start)
Column k > 0 is asymptotic to c(k) * d(k)^n / n^(3/2), where constants c(k) and d(k) are dependent only on k. Conjecture: d(k) ~ k * exp(1). Numerically:
d(1) = 2.9557652856519949747148175... (A051491)
d(2) = 5.6465426162329497128927135... (A245870)
d(3) = 8.3560268792959953682760695...
d(4) = 11.0699628777593263124193026...
d(5) = 13.7856511100846851989303249...
d(6) = 16.5022088446930015657112211...
d(7) = 19.2192613290638657575973462...
d(8) = 21.9366222112987115910888213...
d(9) = 24.6541883249893084812976812...
d(10) = 27.3718979186642404090999595...
d(100) = 272.0126359583480733207362718...
d(101) = 274.7309127032967881125015217...
d(200) = 543.8405620978790523837823296...
d(201) = 546.5588426492458787468860222...
d(101)-d(100) = 2.718276744...
d(201)-d(200) = 2.718280551...
(End)

Examples

			Square array A(n,k) begins:
  0,  0,    0,     0,      0,      0,       0,       0, ...
  1,  1,    1,     1,      1,      1,       1,       1, ...
  0,  1,    2,     3,      4,      5,       6,       7, ...
  0,  2,    7,    15,     26,     40,      57,      77, ...
  0,  4,   26,    82,    188,    360,     614,     966, ...
  0,  9,  107,   495,   1499,   3570,    7284,   13342, ...
  0, 20,  458,  3144,  12628,  37476,   91566,  195384, ...
  0, 48, 2058, 20875, 111064, 410490, 1200705, 2984142, ...

Links

Crossrefs

Columns k=0-10 give: A063524, A000081, A000151, A006964, A052763, A052788, A246235, A246236, A246237, A246238, A246239.
Rows n=0-3 give: A000004, A000012, A001477, A005449.
Lower diagonal gives A242375.
Cf. A255517, A256064.

Programs

  • Maple
    with(numtheory):
A:= proc(n, k) option remember; `if`(n<2, n, (add(add(d*
      A(d, k), d=divisors(j))*A(n-j, k)*k, j=1..n-1))/(n-1))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);
  • Mathematica
    nn = 10; t[x_] := Sum[a[n] x^n, {n, 1, nn}]; Transpose[ Table[Flatten[ sol = SolveAlways[ 0 == Series[ t[x] - x Product[1/(1 - x^i)^(n a[i]), {i, 1, nn}], {x, 0, nn}], x]; Flatten[{0, Table[a[n], {n, 1, nn}]}] /. sol], {n, 0, nn}]] // Grid (* Geoffrey Critzer, Nov 11 2014 *)
A[n_, k_] := A[n, k] = If[n<2, n, Sum[Sum[d*A[d, k], {d, Divisors[j]}] *A[n-j, k]*k, {j, 1, n-1}]/(n-1)]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Dec 04 2014, translated from Maple *)
  • PARI
    \\ ColGf gives column generating function
ColGf(N,k) = {my(A=vector(N, j, 1)); for (n=1, N-1, A[n+1] = k/n * sum(i=1, n, sumdiv(i, d, d*A[d]) * A[n-i+1] ) ); x*Ser(A)}
Mat(vector(8, k, concat(0, Col(ColGf(7, k-1))))) \\ Andrew Howroyd, May 12 2018

Formula

G.f. for column k: x*Product_{n>=1} 1/(1 - x^n)^(k*A(n,k)). - Geoffrey Critzer, Nov 13 2014

A319254 Array read by antidiagonals: T(n,k) is the number of series-reduced rooted trees with n leaves of k colors.

Original entry on oeis.org

1, 2, 1, 3, 3, 2, 4, 6, 10, 5, 5, 10, 28, 40, 12, 6, 15, 60, 156, 170, 33, 7, 21, 110, 430, 948, 785, 90, 8, 28, 182, 965, 3396, 6206, 3770, 261, 9, 36, 280, 1890, 9376, 28818, 42504, 18805, 766, 10, 45, 408, 3360, 21798, 97775, 256172, 301548, 96180, 2312
Offset: 1

Views

Author

Andrew Howroyd, Sep 15 2018

Keywords

Comments

Not all colors need to be used.
See table 2.3 in the Johnson reference.

Examples

			Array begins:
==================================================================
n\k|   1     2       3        4         5         6          7
---+--------------------------------------------------------------
1  |   1     2       3        4         5         6          7 ...
2  |   1     3       6       10        15        21         28 ...
3  |   2    10      28       60       110       182        280 ...
4  |   5    40     156      430       965      1890       3360 ...
5  |  12   170     948     3396      9376     21798      44856 ...
6  |  33   785    6206    28818     97775    269675     642124 ...
7  |  90  3770   42504   256172   1068450   3496326    9632960 ...
8  | 261 18805  301548  2357138  12081605  46897359  149491104 ...
9  | 766 96180 2195100 22253672 140160650 645338444 2379859608 ...
...

Links

Crossrefs

Columns 1..5 are A000669, A050381, A220823, A220824, A220825.
Main diagonal is A319369.
Cf. A141610, A242249, A255517, A256064, A256068, A319376.

Programs

  • Maple
    b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
seq(seq(A(n, 1+d-n), n=1..d), d=1..12);  # Alois P. Heinz, Sep 17 2018
  • Mathematica
    b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A[i, k] + j - 1, j] b[n - i j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n k, b[n, n - 1, k]];
Table[A[n, 1 + d - n], {d, 1, 12}, {n, 1, d}] // Flatten (* Jean-François Alcover, Sep 11 2019, after Alois P. Heinz *)
  • PARI
    \\ here R(n,k) gives k'th column as a vector.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n,k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v,[0]))[n])); v}
{my(T=Mat(vector(8, k, R(8, k)~))); for(n=1, #T~, print(T[n,]))} \\ Andrew Howroyd, Sep 15 2018

A319376 Triangle read by rows: T(n,k) is the number of lone-child-avoiding rooted trees with n leaves of exactly k colors.

Original entry on oeis.org

1, 1, 1, 2, 6, 4, 5, 30, 51, 26, 12, 146, 474, 576, 236, 33, 719, 3950, 8572, 8060, 2752, 90, 3590, 31464, 108416, 175380, 134136, 39208, 261, 18283, 245916, 1262732, 3124650, 4014348, 2584568, 660032, 766, 94648, 1908858, 14047288, 49885320, 95715728, 101799712, 56555904, 12818912
Offset: 1

Views

Author

Andrew Howroyd, Sep 17 2018

Keywords

Comments

Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.

Examples

			Triangle begins:
    1;
    1,     1;
    2,     6,      4;
    5,    30,     51,      26;
   12,   146,    474,     576,     236;
   33,   719,   3950,    8572,    8060,   2752;
   90,  3590,  31464,  108416,  175380,  134136,   39208;
  261, 18283, 245916, 1262732, 3124650, 4014348, 2584568, 660032;
  ...
From _Gus Wiseman_, Dec 31 2020: (Start)
The 12 trees counted by row n = 3:
  (111)    (112)    (123)
  (1(11))  (122)    (1(23))
           (1(12))  (2(13))
           (1(22))  (3(12))
           (2(11))
           (2(12))
(End)

Links

Crossrefs

Columns k=1..2 are A000669, A319377.
Main diagonal is A000311.
Row sums are A316651.
Cf. A141610, A242249, A255517, A256064, A256068, A319254, A319541, A326396.
The unlabeled version, counting inequivalent leaf-colorings of lone-child-avoiding rooted trees, is A330465.
Lone-child-avoiding rooted trees are counted by A001678 (shifted left once).
Labeled lone-child-avoiding rooted trees are counted by A060356.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Cf. A000014, A000081, A000169, A005804, A206429, A330951.

Programs

  • Maple
    b:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(A(i, k)+j-1, j)*b(n-i*j, i-1, k), j=0..n/i)))
    end:
A:= (n, k)-> `if`(n<2, n*k, b(n, n-1, k)):
T:= (n, k)-> add(A(n, k-j)*(-1)^j*binomial(k, j), j=0..k-1):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Sep 18 2018
  • Mathematica
    b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[A[i, k] + j - 1, j] b[n - i j, i - 1, k], {j, 0, n/i}]]];
A[n_, k_] := If[n < 2, n k, b[n, n - 1, k]];
T[n_, k_] := Sum[(-1)^(k - i)*Binomial[k, i]*A[n, i], {i, 1, k}];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 24 2019, after Alois P. Heinz *)
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]]]];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p],{p,Select[mps[m],1Gus Wiseman, Dec 31 2020 *)
  • PARI
    \\ here R(n,k) is k-th column of A319254.
EulerT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, 1/n))))-1, -#v)}
R(n, k)={my(v=[k]); for(n=2, n, v=concat(v, EulerT(concat(v, [0]))[n])); v}
M(n)={my(v=vector(n, k, R(n,k)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k,i)*v[i])))}
{my(T=M(10)); for(n=1, #T~, print(T[n, ][1..n]))}

Formula

T(n,k) = Sum_{i=1..k} (-1)^(k-i)*binomial(k,i)*A319254(n,i).
Sum_{k=1..n} k * T(n,k) = A326396(n). - Alois P. Heinz, Sep 11 2019

A256068 Number T(n,k) of rooted identity trees with n nodes and colored non-root nodes using exactly k colors; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 0, 2, 14, 16, 0, 3, 60, 174, 125, 0, 6, 254, 1434, 2464, 1296, 0, 12, 1087, 10746, 33362, 40455, 16807, 0, 25, 4742, 77556, 388312, 816535, 763104, 262144, 0, 52, 21020, 551460, 4191916, 13617210, 21501684, 16328620, 4782969
Offset: 1

Views

Author

Alois P. Heinz, Mar 13 2015

Keywords

Examples

			T(4,2) = 14:
:   0   0   0   0   0   0     0       0
:   |   |   |   |   |   |     |       |
:   1   1   2   2   2   1     1       2
:   |   |   |   |   |   |    / \     / \
:   1   2   1   2   1   2   1   2   1   2
:   |   |   |   |   |   |
:   2   1   1   1   2   1
:
:     0      0      0      0      0      0
:    / \    / \    / \    / \    / \    / \
:   1   1  2   1  1   2  2   2  1   2  2   1
:   |      |      |      |      |      |
:   2      1      1      1      2      2
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,    3;
  0,  2,   14,    16;
  0,  3,   60,   174,    125;
  0,  6,  254,  1434,   2464,   1296;
  0, 12, 1087, 10746,  33362,  40455,  16807;
  0, 25, 4742, 77556, 388312, 816535, 763104, 262144;
  ...

Links

Crossrefs

Columns k=0-1 give: A063524 (for n>0), A004111 (for n>1):
Main diagonal gives: A000272 (for n>0).
Row sums give A319220(n-1).
T(2n+1,n) gives A309996.
Cf. A255517, A256064.

Programs

  • Maple
    with(numtheory):
A:= proc(n, k) option remember; `if`(n<2, n, add(A(n-j, k)*add(
      k*A(d, k)*d*(-1)^(j/d+1), d=divisors(j)), j=1..n-1)/(n-1))
    end:
T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n-1), n=1..10);
  • Mathematica
    A[n_, k_] := A[n, k] = If[n < 2, n, Sum[A[n - j, k] Sum[k A[d, k] d * (-1)^(j/d + 1), {d, Divisors[j]}], {j, 1, n - 1}]/(n - 1)];
T[n_, k_] := Sum[A[n, k - i] (-1)^i Binomial[k, i], {i, 0, k}];
Table[T[n, k], {n, 10}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, May 29 2020, after Maple *)

Formula

T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A255517(n).

A141610 Number of rooted trees with n points and exactly k specified colors: C(n,k), 1<=n, 1<=k<=n.

Original entry on oeis.org

1, 1, 2, 2, 10, 9, 4, 44, 102, 64, 9, 196, 870, 1304, 625, 20, 876, 6744, 18200, 20080, 7776, 48, 4020, 50421, 218260, 416500, 362322, 117649, 115, 18766, 371676, 2427600, 7133655, 10465290, 7503328, 2097152, 286, 89322, 2731569, 25919692, 110136425, 242427438, 288002582, 175481056, 43046721
Offset: 1

Views

Author

Robert A. Russell, Aug 22 2008, Aug 27 2008

Keywords

Comments

The number of rooted trees with n points having any of c colors is Sum_k C(n,k) {c choose k}.

Examples

			C(n,1) is the number of rooted trees with n points (A000081). C(n,n)=n^{n-1}. C(3,2)=10 is the number of rooted trees with three points and two colors: AAB, ABB, ABA, BAA, BAB, BBA, A(BB), A(AB), B(AA), B(AB), where ABC is a rooted tree with A the root, B attached to A and C; A(BC) is a rooted tree with A the root, A attached to B and C.
   1;
   1,   2;
   2,  10,    9;
   4,  44,  102,    64;
   9, 196,  870,  1304,   625;
  20, 876, 6744, 18200, 20080, 7776;
  ...

Links

Crossrefs

Columns 1..3 are A000081, A339642, A339643.
C(n,n) is A000169.
Row sums are A339644.
Cf. A256064.

Programs

  • Maple
    b:= proc(n, k) option remember; `if`(n<2, k*n, (add(add(b(d, k)*
      d, d=numtheory[divisors](j))*b(n-j, k), j=1..n-1))/(n-1))
    end:
C:= (n, k)-> add(b(n, k-j)*binomial(k, j)*(-1)^j, j=0..k):
seq(seq(C(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Dec 11 2020
  • Mathematica
    p[a_List]:=a;p[a_List,b_List,c___List]:=If[Length[a]
<=Length[b],p[PadRight[a,Length[b]]+b,c],p[b,a,c]];
c[i_,j_]:=If[iJean-François Alcover, Jan 04 2021, after Alois P. Heinz *)
  • PARI
    \\ here U(N, m) is adaptation of A000081 for m colors.
U(N, m)={my(A=vector(N, j, m)); for(n=1, N-1, A[n+1] = sum(k=1, n, sumdiv(k, d, d*A[d]) * A[n-k+1])/n); A}
M(n)={my(v=vector(n, i, U(n,i)~)); Mat(vector(n, k, sum(i=1, k, (-1)^(k-i)*binomial(k, i)*v[i])))}
{my(T=M(10)); for(n=1, #T~, print(T[n,][1..n]))} \\ Andrew Howroyd, Sep 15 2018

A309994 Number of forests of rooted trees with 2n colored nodes using exactly n colors.

Original entry on oeis.org

1, 2, 89, 14845, 5613775, 3809941836, 4073969863427, 6316651717425358, 13407079935176225215, 37344967651943608528498, 132181958309965092862822183, 579566807739313784043087337938, 3083812115454145185391757131500066, 19577110356940490275990571617295644659
Offset: 0

Views

Author

Alois P. Heinz, Aug 26 2019

Keywords

Links

Crossrefs

Cf. A256064.

Programs

  • Maple
    b:= proc(n, k) option remember; `if`(n<2, n, (add(add(d*b(d, k),
      d=numtheory[divisors](j))*b(n-j, k)*k, j=1..n-1))/(n-1))
    end:
a:= n-> add(b(2*n+1, n-i)*(-1)^i*binomial(n, i), i=0..n):
seq(a(n), n=0..15);
  • Mathematica
    b[n_, k_] := b[n, k] = If[n < 2, n, Sum[Sum[d*b[d, k], {d, Divisors[j]}]*b[n-j, k]*k, {j, 1, n-1}]/(n-1)];
a[n_] := Sum[b[2*n+1, n-i]*(-1)^i*Binomial[n, i], {i, 0, n}];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Sep 15 2022, after Alois P. Heinz *)

Formula

a(n) = A256064(2*n+1,n).
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.