[go: up one dir, main page]
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
Search: a244657 -id:a244657
Displaying 1-10 of 13 results found. page 1 2
     Sort: relevance | references | number | modified | created      Format: long | short | data
A124343 Number of rooted trees on n nodes with thinning limbs. +10
13
1, 1, 2, 3, 6, 10, 21, 38, 78, 153, 314, 632, 1313, 2700, 5646, 11786, 24831, 52348, 111027, 235834, 502986, 1074739, 2303146, 4944507, 10639201, 22930493, 49511948, 107065966, 231874164, 502834328, 1091842824, 2373565195, 5165713137, 11254029616, 24542260010 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,3
COMMENTS
A rooted tree with thinning limbs is such that if a node has k children, all its children have at most k children.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 1..141
EXAMPLE
The a(5) = 6 trees are ((((o)))), (o((o))), (o(oo)), ((o)(o)), (oo(o)), (oooo). - Gus Wiseman, Jan 25 2018
MAPLE
b:= proc(n, i, h, v) option remember; `if`(n=0,
`if`(v=0, 1, 0), `if`(i<1 or v<1 or n<v, 0,
`if`(n=v, 1, add(binomial(A(i, min(i-1, h))+j-1, j)
*b(n-i*j, i-1, h, v-j), j=0..min(n/i, v)))))
end:
A:= proc(n, k) option remember;
`if`(n<2, n, add(b(n-1$2, j$2), j=1..min(k, n-1)))
end:
a:= n-> A(n$2):
seq(a(n), n=1..35); # Alois P. Heinz, Jul 08 2014
MATHEMATICA
b[n_, i_, h_, v_] := b[n, i, h, v] = If[n==0, If[v==0, 1, 0], If[i<1 || v<1 || n<v, 0, If[n==v, 1, Sum[Binomial[A[i, Min[i-1, h]]+j-1, j]*b[n-i*j, i-1, h, v-j], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n<2, n, Sum[b[n-1, n-1, j, j], {j, 1, Min[k, n-1] }]];
a[n_] := A[n, n];
Table[a[n], {n, 1, 35}] (* Jean-François Alcover, Mar 01 2016, after Alois P. Heinz *)
CROSSREFS
Cf. A000081, A032305, A124344-A124348, A290689, A298303, A298304, A298305, A298422.
Row sums of A244657.
KEYWORD
nonn
AUTHOR
Christian G. Bower, Oct 30 2006, suggested by Franklin T. Adams-Watters
EXTENSIONS
More terms from Alois P. Heinz, Jul 04 2014
STATUS
approved
A245120 Number T(n,k) of n-node rooted identity trees with thinning limbs and root outdegree (branching factor) k; triangle T(n,k), n>=1, 0<=k<=max-index-of-row(n), read by rows. +10
12
1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 3, 0, 1, 4, 1, 0, 1, 8, 2, 0, 1, 12, 4, 0, 1, 22, 9, 0, 1, 36, 17, 2, 0, 1, 63, 35, 3, 0, 1, 107, 67, 9, 0, 1, 188, 131, 20, 0, 1, 327, 249, 46, 1, 0, 1, 578, 484, 94, 4, 0, 1, 1020, 922, 202, 11, 0, 1, 1820, 1775, 412, 28 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,14
COMMENTS
In a rooted tree with thinning limbs the outdegree of a parent node is larger than or equal to the outdegree of any of its child nodes.
LINKS
Alois P. Heinz, Rows n = 1..140, flattened
EXAMPLE
The A124346(7) = 6 7-node rooted identity trees with thinning limbs sorted by root outdegree are:
: 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 o : o o :
: | : | | | | : | :
: o : o o o o : o :
: | : | | | : :
: o : o o o : :
: | : | : :
: o : o : :
: | : : :
: o : : :
: : : :
: -1- : -------------2------------ : --3-- :
Thus row 7 = [0, 1, 4, 1].
Triangle T(n,k) begins:
1;
0, 1;
0, 1;
0, 1, 1;
0, 1, 1;
0, 1, 3;
0, 1, 4, 1;
0, 1, 8, 2;
0, 1, 12, 4;
0, 1, 22, 9;
0, 1, 36, 17, 2;
0, 1, 63, 35, 3;
MAPLE
b:= proc(n, i, h, v) option remember; `if`(n=0, `if`(v=0, 1, 0),
`if`(i<1 or v<1 or n<v, 0, add(binomial(A(i, min(i-1, h)), j)
*b(n-i*j, i-1, h, v-j), j=0..min(n/i, v))))
end:
A:= proc(n, k) option remember;
`if`(n<2, n, add(b(n-1$2, j$2), j=1..min(k, n-1)))
end:
g:= proc(n) local k; if n=1 then 0 else
for k while T(n, k)>0 do od; k-1 fi
end:
T:= (n, k)-> b(n-1$2, k$2):
seq(seq(T(n, k), k=0..g(n)), n=1..25);
MATHEMATICA
b[n_, i_, h_, v_] := b[n, i, h, v] = If[n==0, If[v==0, 1, 0], If[i<1 || v<1 || n<v, 0, Sum[Binomial[A[i, Min[i-1, h]], j]*b[n-i*j, i-1, h, v-j], {j, 0, Min[n/i, v]}]]]; A[n_, k_] := A[n, k] = If[n<2, n, Sum[b[n-1, n-1, j, j], {j, 1, Min[k, n-1]}]]; g[n_] := If[n==1, 0, For[k=1, T[n, k]>0, k++]; k-1]; T[n_, k_] := b[n-1, n-1, k, k]; Table[T[n, k], {n, 1, 25}, {k, 0, g[n]}] // Flatten (* Jean-François Alcover, Jan 18 2017, translated from Maple *)
CROSSREFS
Column k=0-10 give: A000007(n-1), A000012 (for n>1), A245121, A245122, A245123, A245124, A245125, A245126, A245127, A245128, A245129.
Row sums give A124346.
Cf. A244657.
KEYWORD
nonn,tabf
AUTHOR
Alois P. Heinz, Jul 12 2014
STATUS
approved
A245151 Number T(n,k) of n-node unlabeled rooted trees with thickening limbs and root outdegree (branching factor) k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows. +10
12
1, 0, 1, 0, 1, 1, 0, 2, 0, 1, 0, 3, 1, 0, 1, 0, 5, 1, 0, 0, 1, 0, 7, 3, 1, 0, 0, 1, 0, 12, 3, 1, 0, 0, 0, 1, 0, 17, 8, 1, 1, 0, 0, 0, 1, 0, 28, 9, 3, 1, 0, 0, 0, 0, 1, 0, 42, 21, 3, 1, 1, 0, 0, 0, 0, 1, 0, 69, 28, 5, 1, 1, 0, 0, 0, 0, 0, 1, 0, 105, 56, 9, 3, 1, 1, 0, 0, 0, 0, 0, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET
1,8
COMMENTS
In a rooted tree with thickening limbs the outdegree of a parent node is smaller than or equal to the outdegree of any of its non-leaf child nodes.
T(n+1,1) = Sum_{k=0..n-1} T(n,k) for n>=1.
T(n+1,n) = T(2n+1,n) = 1 for n>=0.
T(n,1+floor((n-1)/2)) = 0 for n>3.
LINKS
Alois P. Heinz, Rows n = 1..141, flattened
EXAMPLE
The A245152(5) = 5 5-node rooted trees with thickening limbs sorted by root outdegree are:
: 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 : : :
: : : :
: ------1------ : ---2--- : ---4--- :
Thus row 5 = [0, 3, 1, 0, 1].
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 2, 0, 1;
0, 3, 1, 0, 1;
0, 5, 1, 0, 0, 1;
0, 7, 3, 1, 0, 0, 1;
0, 12, 3, 1, 0, 0, 0, 1;
0, 17, 8, 1, 1, 0, 0, 0, 1;
0, 28, 9, 3, 1, 0, 0, 0, 0, 1;
0, 42, 21, 3, 1, 1, 0, 0, 0, 0, 1;
0, 69, 28, 5, 1, 1, 0, 0, 0, 0, 0, 1;
0, 105, 56, 9, 3, 1, 1, 0, 0, 0, 0, 0, 1;
0, 176, 81, 12, 3, 1, 1, 0, 0, 0, 0, 0, 0, 1;
MAPLE
b:= proc(n, i, h, v) option remember; `if`(n=0,
`if`(v=0, 1, 0), `if`(i<1 or v<1 or n<v, 0,
`if`(n=v, 1, add(binomial(A(i, h)+j-1, j)*
b(n-i*j, i-1, h, v-j), j=0..min(n/i, v)))))
end:
A:= proc(n, k) option remember;
`if`(n<2, n, add(b(n-1$2, j$2), j=k..n-1))
end:
T:= (n, k)-> b(n-1$2, k$2):
seq(seq(T(n, k), k=0..n-1), n=1..20);
MATHEMATICA
b[n_, i_, h_, v_] := b[n, i, h, v] = If[n == 0, If[v == 0, 1, 0], If[i<1 || v<1 || n<v, 0, If[n == v, 1, Sum[Binomial[A[i, h] + j - 1, j]*b[n - i*j, i-1, h, v-j], {j, 0, Min[n/i, v]}]]]]; A[n_, k_] := A[n, k] = If[n<2, n, Sum[b[n-1, n-1, j, j], {j, k, n-1}]]; T[n_, k_] := b[n-1, n-1, k, k]; Table[ Table[T[n, k], {k, 0, n - 1}], {n, 1, 20}] // Flatten (* Jean-François Alcover, Jan 27 2015, after Alois P. Heinz *)
CROSSREFS
Columns k=0-10 give: A000007(n-1), A245152(n-1), A245142, A245143, A245144, A245145, A245146, A245147, A245148, A245149, A245150.
Row sums give A245152.
Cf. A244657 (thinning limbs).
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jul 12 2014
STATUS
approved
A244703 Number of n-node unlabeled rooted trees with thinning limbs and root outdegree (branching factor) 2. +10
2
1, 1, 3, 4, 9, 13, 26, 42, 81, 138, 262, 467, 885, 1620, 3076, 5743, 10953, 20721, 39714, 75873, 146139, 281259, 544230, 1053552, 2047147, 3981790, 7766018, 15165195, 29676887, 58148087, 114129308, 224278526, 441368913, 869583189, 1715365690, 3387344619 (list; graph; refs; listen; history; text; internal format)
OFFSET
3,3
COMMENTS
In a rooted tree with thinning limbs the outdegree of a parent node is larger than or equal to the outdegree of any of its child nodes.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 3..1000
FORMULA
a(n) ~ c * d^n / n^(3/2), where d = 2.0554620926822709065075792..., c = 1.0209036918758320315742... . - Vaclav Kotesovec, Aug 27 2014
EXAMPLE
a(6) = 4:
o o o o
/ \ / \ / \ / \
o o o o o o o o
| / \ | | / \ |
o o o o o o o o
| | |
o o o
|
o
MAPLE
b:= proc(n, i, h, v) option remember; `if`(n=0,
`if`(v=0, 1, 0), `if`(i<1 or v<1 or n<v, 0,
`if`(n=v, 1, add(binomial(A(i, min(i-1, h))+j-1, j)
*b(n-i*j, i-1, h, v-j), j=0..min(n/i, v)))))
end:
A:= proc(n, k) option remember;
`if`(n<2, n, add(b(n-1$2, j$2), j=1..min(k, n-1)))
end:
a:= n-> b(n-1$2, 2$2):
seq(a(n), n=3..50);
MATHEMATICA
b[n_, i_, h_, v_] := b[n, i, h, v] = If[n == 0, If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0, If[n == v, 1, Sum[Binomial[A[i, Min[i - 1, h]] + j - 1, j]*b[n - i*j, i - 1, h, v - j], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n<2, n, Sum[b[n-1, n-1, j, j], {j, 1, Min[k, n-1] }]];
a[n_] := b[n-1, n-1, 2, 2];
a /@ Range[3, 50] (* Jean-François Alcover, Dec 27 2020, after Alois P. Heinz *)
CROSSREFS
Column k=2 of A244657.
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 04 2014
STATUS
approved
A244704 Number of n-node unlabeled rooted trees with thinning limbs and root outdegree (branching factor) 3. +10
2
1, 1, 3, 6, 13, 25, 55, 107, 224, 454, 938, 1916, 3969, 8163, 16918, 35010, 72724, 151093, 314749, 656115, 1370348, 2864948, 5998547, 12572884, 26385837, 55431031, 116577538, 245415158, 517152607, 1090771973, 2302729115, 4865449045, 10288826434, 21774842539 (list; graph; refs; listen; history; text; internal format)
OFFSET
4,3
COMMENTS
In a rooted tree with thinning limbs the outdegree of a parent node is larger than or equal to the outdegree of any of its child nodes.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 4..1000
FORMULA
a(n) ~ c * d^n / n^(3/2), where d = 2.1991393868..., c = 1.0259536... . - Vaclav Kotesovec, Aug 27 2014
EXAMPLE
a(7) = 6:
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 o o o o o o o o o o o o
| | |
o o o
|
o
MAPLE
b:= proc(n, i, h, v) option remember; `if`(n=0,
`if`(v=0, 1, 0), `if`(i<1 or v<1 or n<v, 0,
`if`(n=v, 1, add(binomial(A(i, min(i-1, h))+j-1, j)
*b(n-i*j, i-1, h, v-j), j=0..min(n/i, v)))))
end:
A:= proc(n, k) option remember;
`if`(n<2, n, add(b(n-1$2, j$2), j=1..min(k, n-1)))
end:
a:= n-> b(n-1$2, 3$2):
seq(a(n), n=4..50);
MATHEMATICA
b[n_, i_, h_, v_] := b[n, i, h, v] = If[n == 0, If[v == 0, 1, 0], If[i < 1 || v < 1 || n < v, 0, If[n == v, 1, Sum[Binomial[A[i, Min[i - 1, h]] + j - 1, j]*b[n - i*j, i - 1, h, v - j], {j, 0, Min[n/i, v]}]]]];
A[n_, k_] := A[n, k] = If[n < 2, n, Sum[b[n - 1, n - 1, j, j], {j, 1, Min[k, n - 1]}]];
a[n_] := b[n-1, n-1, 3, 3];
a /@ Range[4, 50] (* Jean-François Alcover, Dec 27 2020, after Alois P. Heinz *)
CROSSREFS
Column k=3 of A244657.
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 04 2014
STATUS
approved
A244705 Number of n-node unlabeled rooted trees with thinning limbs and root outdegree (branching factor) 4. +10
2
1, 1, 3, 6, 15, 29, 68, 140, 312, 660, 1443, 3084, 6710, 14425, 31278, 67508, 146300, 316424, 685955, 1486008, 3223480, 6992012, 15179437, 32960891, 71617874, 155661971, 338508703, 736401503, 1602712182, 3489454243, 7600403101, 16560519877, 36097320801 (list; graph; refs; listen; history; text; internal format)
OFFSET
5,3
COMMENTS
In a rooted tree with thinning limbs the outdegree of a parent node is larger than or equal to the outdegree of any of its child nodes.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 5..1000
MAPLE
b:= proc(n, i, h, v) option remember; `if`(n=0,
`if`(v=0, 1, 0), `if`(i<1 or v<1 or n<v, 0,
`if`(n=v, 1, add(binomial(A(i, min(i-1, h))+j-1, j)
*b(n-i*j, i-1, h, v-j), j=0..min(n/i, v)))))
end:
A:= proc(n, k) option remember;
`if`(n<2, n, add(b(n-1$2, j$2), j=1..min(k, n-1)))
end:
a:= n-> b(n-1$2, 4$2):
seq(a(n), n=5..50);
CROSSREFS
Column k=4 of A244657.
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 04 2014
STATUS
approved
A244706 Number of n-node unlabeled rooted trees with thinning limbs and root outdegree (branching factor) 5. +10
2
1, 1, 3, 6, 15, 31, 72, 153, 346, 752, 1673, 3661, 8108, 17814, 39349, 86646, 191251, 421596, 930519, 2052789, 4531648, 10002857, 22088709, 48780279, 107757048, 238069894, 526096509, 1162775782, 2570487392, 5683401236, 12568472173, 27799055016, 61496981626 (list; graph; refs; listen; history; text; internal format)
OFFSET
6,3
COMMENTS
In a rooted tree with thinning limbs the outdegree of a parent node is larger than or equal to the outdegree of any of its child nodes.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 6..1000
MAPLE
b:= proc(n, i, h, v) option remember; `if`(n=0,
`if`(v=0, 1, 0), `if`(i<1 or v<1 or n<v, 0,
`if`(n=v, 1, add(binomial(A(i, min(i-1, h))+j-1, j)
*b(n-i*j, i-1, h, v-j), j=0..min(n/i, v)))))
end:
A:= proc(n, k) option remember;
`if`(n<2, n, add(b(n-1$2, j$2), j=1..min(k, n-1)))
end:
a:= n-> b(n-1$2, 5$2):
seq(a(n), n=6..50);
CROSSREFS
Column k=5 of A244657.
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 04 2014
STATUS
approved
A244707 Number of n-node unlabeled rooted trees with thinning limbs and root outdegree (branching factor) 6. +10
2
1, 1, 3, 6, 15, 31, 74, 157, 359, 786, 1766, 3895, 8710, 19287, 42987, 95437, 212468, 472204, 1050940, 2337221, 5201558, 11573156, 25759514, 57332239, 127633669, 284148877, 632704464, 1408925270, 3137861761, 6989057709, 15568767849, 34684141315, 77277619879 (list; graph; refs; listen; history; text; internal format)
OFFSET
7,3
COMMENTS
In a rooted tree with thinning limbs the outdegree of a parent node is larger than or equal to the outdegree of any of its child nodes.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 7..900
MAPLE
b:= proc(n, i, h, v) option remember; `if`(n=0,
`if`(v=0, 1, 0), `if`(i<1 or v<1 or n<v, 0,
`if`(n=v, 1, add(binomial(A(i, min(i-1, h))+j-1, j)
*b(n-i*j, i-1, h, v-j), j=0..min(n/i, v)))))
end:
A:= proc(n, k) option remember;
`if`(n<2, n, add(b(n-1$2, j$2), j=1..min(k, n-1)))
end:
a:= n-> b(n-1$2, 6$2):
seq(a(n), n=7..50);
CROSSREFS
Column k=6 of A244657.
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 04 2014
STATUS
approved
A244708 Number of n-node unlabeled rooted trees with thinning limbs and root outdegree (branching factor) 7. +10
2
1, 1, 3, 6, 15, 31, 74, 159, 363, 799, 1800, 3988, 8945, 19893, 44486, 99153, 221520, 494187, 1103789, 2463834, 5502927, 12288076, 27448039, 61308387, 136966368, 305999360, 683733350, 1527844853, 3414432569, 7631131801, 17056871547, 38127833992, 85235556468 (list; graph; refs; listen; history; text; internal format)
OFFSET
8,3
COMMENTS
In a rooted tree with thinning limbs the outdegree of a parent node is larger than or equal to the outdegree of any of its child nodes.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 8..500
MAPLE
b:= proc(n, i, h, v) option remember; `if`(n=0,
`if`(v=0, 1, 0), `if`(i<1 or v<1 or n<v, 0,
`if`(n=v, 1, add(binomial(A(i, min(i-1, h))+j-1, j)
*b(n-i*j, i-1, h, v-j), j=0..min(n/i, v)))))
end:
A:= proc(n, k) option remember;
`if`(n<2, n, add(b(n-1$2, j$2), j=1..min(k, n-1)))
end:
a:= n-> b(n-1$2, 7$2):
seq(a(n), n=8..50);
CROSSREFS
Column k=7 of A244657.
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 04 2014
STATUS
approved
A244709 Number of n-node unlabeled rooted trees with thinning limbs and root outdegree (branching factor) 8. +10
2
1, 1, 3, 6, 15, 31, 74, 159, 365, 803, 1813, 4022, 9038, 20128, 45093, 100656, 225263, 503320, 1126045, 2517487, 5631913, 12596046, 28181168, 63045684, 141071758, 315668674, 706452161, 1581088178, 3538954508, 7921759060, 17733983146, 39702719910, 88893039358 (list; graph; refs; listen; history; text; internal format)
OFFSET
9,3
COMMENTS
In a rooted tree with thinning limbs the outdegree of a parent node is larger than or equal to the outdegree of any of its child nodes.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 9..500
MAPLE
b:= proc(n, i, h, v) option remember; `if`(n=0,
`if`(v=0, 1, 0), `if`(i<1 or v<1 or n<v, 0,
`if`(n=v, 1, add(binomial(A(i, min(i-1, h))+j-1, j)
*b(n-i*j, i-1, h, v-j), j=0..min(n/i, v)))))
end:
A:= proc(n, k) option remember;
`if`(n<2, n, add(b(n-1$2, j$2), j=1..min(k, n-1)))
end:
a:= n-> b(n-1$2, 8$2):
seq(a(n), n=9..50);
CROSSREFS
Column k=8 of A244657.
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Jul 04 2014
STATUS
approved
page 1 2

Search completed in 0.012 seconds

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 30 17:27 EDT 2024. Contains 375545 sequences. (Running on oeis4.)