A004111
Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).
Original entry on oeis.org
0, 1, 1, 1, 2, 3, 6, 12, 25, 52, 113, 247, 548, 1226, 2770, 6299, 14426, 33209, 76851, 178618, 416848, 976296, 2294224, 5407384, 12780394, 30283120, 71924647, 171196956, 408310668, 975662480, 2335443077, 5599508648, 13446130438, 32334837886, 77863375126, 187737500013, 453203435319, 1095295264857, 2649957419351
Offset: 0
The 2 identity trees with 4 nodes are:
O O
/ \ |
O O O
| |
O O
|
O
These correspond to the sets {{},{{}}} and {{{{}}}}.
G.f.: x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 12*x^7 + 25*x^8 + 52*x^9 + ...
- F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 330.
- S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 301 and 562.
- F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 64, Eq. (3.3.15); p. 80, Problem 3.10.
- D. E. Knuth, Fundamental Algorithms, 3rd Ed., 1997, pp. 386-388.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- Alois P. Heinz, Table of n, a(n) for n = 0..2500 (first 201 terms from T. D. Noe)
- Joerg Arndt, All identity trees for n = 1..11.
- P. J. Cameron, Some sequences of integers, Discrete Math., 75 (1989), 89-102; also in "Graph Theory and Combinatorics 1988", ed. B. Bollobas, Annals of Discrete Math., 43 (1989), 89-102.
- A. Genitrini, Full asymptotic expansion for Polya structures, arXiv:1605.00837 [math.CO], May 03 2016, p. 8.
- Bernhard Gittenberger, Emma Yu Jin, Michael Wallner, On the shape of random Pólya structures, arXiv|1707.02144 [math.CO], 2017-2018; Discrete Math., 341 (2018), 896-911.
- Frank Harary and Geert Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.
- F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503.
- F. Harary, R. W. Robinson and A. J. Schwenk, Corrigenda: Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A 41 (1986), p. 325.
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 56.
- P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
- T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
- T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
- N. J. A. Sloane, Sketch showing trees with 2 through 6 nodes.
- Index entries for sequences related to rooted trees
-
import Data.List (genericIndex)
a004111 = genericIndex a004111_list
a004111_list = 0 : 1 : f 1 [1] where
f x zs = y : f (x + 1) (y : zs) where
y = (sum $ zipWith (*) zs $ map g [1..]) `div` x
g k = sum $ zipWith (*) (map (((-1) ^) . (+ 1)) $ reverse divs)
(zipWith (*) divs $ map a004111 divs)
where divs = a027750_row k
-- Reinhard Zumkeller, Apr 29 2014
-
A004111 := proc(n)
spec := [ A, {A=Prod(Z,PowerSet(A))} ]:
combstruct[count](spec, size=n) ;
end proc:
# second Maple program:
with(numtheory):
a:= proc(n) a(n):= `if`(n<2, n, add(a(n-k)*add(a(d)*d*
(-1)^(k/d+1), d=divisors(k)), k=1..n-1)/(n-1))
end:
seq(a(n), n=0..50); # Alois P. Heinz, Jul 15 2014
-
s[ n_, k_ ] := s[ n, k ]=a[ n+1-k ]+If[ n<2k, 0, -s[ n-k, k ] ]; a[ 1 ]=1; a[ n_ ] := a[ n ]=Sum[ a[ i ]s[ n-1, i ]i, {i, 1, n-1} ]/(n-1); Table[ a[ i ], {i, 1, 30} ] (* Robert A. Russell *)
a[ n_] := If[ n < 2, Boole[n == 1], Nest[ CoefficientList[ Normal[ Times @@ (Table[1 + x^k, {k, Length@#}]^#) + x O[x]^Length@#], x] &, {}, n - 1][[n]]]; (* Michael Somos, Jul 10 2014 *)
a[n_] := a[n] = Sum[a[n-k]*Sum[a[d]*d*(-1)^(k/d+1),{d, Divisors[k]}], {k, 1, n-1}]/(n-1); a[0]=0; a[1]=1; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 02 2015 *)
-
N=66; A=vector(N+1, j, 1);
for (n=1, N, A[n+1] = 1/n * sum(k=1, n, sumdiv(k, d, (-1)^(k/d+1) * d * A[d]) * A[n-k+1] ) );
concat([0], A)
\\ Joerg Arndt, Jul 10 2014
A007560
Number of planted identity trees where non-root, non-leaf nodes an even distance from root are of degree 2.
Original entry on oeis.org
1, 1, 1, 1, 2, 2, 4, 6, 10, 17, 29, 51, 89, 159, 284, 512, 930, 1692, 3101, 5698, 10515, 19464, 36143, 67296, 125622, 235050, 440756, 828142, 1558955, 2939761, 5552744, 10504222, 19899760, 37750091, 71704061, 136361602, 259618770, 494821629, 944074665
Offset: 1
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
- Alois P. Heinz, Table of n, a(n) for n = 1..1000
- 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 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
- Index entries for sequences related to rooted trees
-
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(a(i), j)*b(n-i*j, i-1), j=0..n/i)))
end:
a:= n-> `if`(n<2, n, b(n-2, n-2)):
seq(a(n), n=1..50); # Alois P. Heinz, May 19 2013
-
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[a[i], j]*b[n-i*j, i-1], {j, 0, n/i}]]]; a[n_] := If[n<2, n, b[n-2, n-2]]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Jan 27 2014, after Alois P. Heinz *)
A316101
Sequence a_k of column k shifts left when Weigh transform is applied k times with a_k(n) = n for n<2; square array A(n,k), n>=0, k>=0, read by antidiagonals.
Original entry on oeis.org
0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 2, 1, 0, 1, 1, 1, 3, 3, 1, 0, 1, 1, 1, 4, 6, 6, 1, 0, 1, 1, 1, 5, 10, 16, 12, 1, 0, 1, 1, 1, 6, 15, 32, 43, 25, 1, 0, 1, 1, 1, 7, 21, 55, 105, 120, 52, 1, 0, 1, 1, 1, 8, 28, 86, 210, 356, 339, 113, 1, 0, 1, 1, 1, 9, 36, 126, 371, 826, 1227, 985, 247, 1
Offset: 0
Square array A(n,k) begins:
0, 0, 0, 0, 0, 0, 0, 0, 0, ...
1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, 1, 1, ...
1, 2, 3, 4, 5, 6, 7, 8, 9, ...
1, 3, 6, 10, 15, 21, 28, 36, 45, ...
1, 6, 16, 32, 55, 86, 126, 176, 237, ...
1, 12, 43, 105, 210, 371, 602, 918, 1335, ...
1, 25, 120, 356, 826, 1647, 2961, 4936, 7767, ...
- Alois P. Heinz, Antidiagonals n = 0..140, flattened
- 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 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]
Columns k=0-10 give:
A057427,
A004111,
A007561,
A316103,
A316104,
A316105,
A316106,
A316107,
A316108,
A316109,
A316110.
-
wtr:= proc(p) local b; b:= proc(n, i) option remember;
`if`(n=0, 1, `if`(i<1, 0, add(binomial(p(i), j)*
b(n-i*j, i-1), j=0..n/i))) end: j-> b(j$2)
end:
g:= proc(k) option remember; local b, t; b[0]:= j->
`if`(j<2, j, b[k](j-1)); for t to k do
b[t]:= wtr(b[t-1]) od: eval(b[0])
end:
A:= (n, k)-> g(k)(n):
seq(seq(A(n, d-n), n=0..d), d=0..14);
-
wtr[p_] := Module[{b}, b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[p[i], j]*b[n - i*j, i - 1], {j, 0, n/i}]]]; b[#, #]&];
g[k_] := g[k] = Module[{b, t}, b[0][j_] := If[j < 2, j, b[k][j - 1]]; For[ t = 1, t <= k + 1, t++, b[t] = wtr[b[t - 1]]]; b[0]];
A[n_, k_] := g[k][n];
Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jul 10 2018, after Alois P. Heinz *)
A144018
Triangle T(n,k), n >= 1, 1 <= k <= n, read by rows, where sequence a_k of column k has a_k(0)=0, followed by (k+1)-fold 1 and a_k(n) shifts k places left under Euler transform.
Original entry on oeis.org
1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 9, 3, 2, 1, 1, 20, 6, 3, 2, 1, 1, 48, 10, 5, 3, 2, 1, 1, 115, 20, 8, 5, 3, 2, 1, 1, 286, 36, 14, 7, 5, 3, 2, 1, 1, 719, 72, 23, 12, 7, 5, 3, 2, 1, 1, 1842, 137, 40, 18, 11, 7, 5, 3, 2, 1, 1, 4766, 275, 69, 30, 16, 11, 7, 5, 3, 2, 1, 1, 12486, 541, 121, 47, 25, 15, 11, 7, 5, 3, 2, 1, 1
Offset: 1
T(5,1) = ([1,2,4]*[1,1,4] + [1]*[1]*4 + [1,2]*[1,1]*2 + [1,3]*[1,2]*1)/4 = 36/4 = 9.
Triangle begins:
1;
1, 1;
2, 1, 1;
4, 2, 1, 1;
9, 3, 2, 1, 1;
20, 6, 3, 2, 1, 1;
48, 10, 5, 3, 2, 1, 1;
115, 20, 8, 5, 3, 2, 1, 1;
286, 36, 14, 7, 5, 3, 2, 1, 1;
719, 72, 23, 12, 7, 5, 3, 2, 1, 1;
- Alois P. Heinz, Rows n = 1..141, flattened
- 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 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
-
etrk:= proc(p) proc(n, k) option remember; `if`(n=0, 1,
add(add(d*p(d, k), d=numtheory[divisors](j))*
procname(n-j, k), j=1..n)/n)
end end:
B:= etrk(T):
T:= (n, k)-> `if`(n<=k, `if`(n=0, 0, 1), B(n-k, k)):
seq(seq(T(n, k), k=1..n), n=1..14);
-
etrk[p_] := Module[{f}, f[n_, k_] := f[n, k] = If[n == 0, 1, (Sum[Sum[d*p[d, k], {d, Divisors[j]}]*f[n-j, k], {j, 1, n-1}] + Sum[d*p[d, k], {d, Divisors[n]}])/n]; f]; b = etrk[t]; t[n_, k_] := If[n <= k, If[n == 0, 0, 1], b[n-k, k]]; Table[t[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Aug 01 2013, after Alois P. Heinz *)
A316075
Sequence shifts left three places under Weigh transform with a(n) = signum(n) for n<3.
Original entry on oeis.org
0, 1, 1, 1, 1, 1, 2, 2, 3, 5, 7, 10, 17, 26, 40, 65, 104, 166, 272, 442, 720, 1186, 1954, 3222, 5346, 8881, 14778, 24668, 41254, 69088, 115959, 194925, 328123, 553200, 933944, 1578614, 2671656, 4526654, 7677736, 13035809, 22154806, 37687152, 64165838
Offset: 0
-
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(a(i), j)*b(n-i*j, i-1), j=0..n/i)))
end:
a:= n-> (k-> `if`(n
A316076
Sequence shifts left four places under Weigh transform with a(n) = signum(n) for n<4.
Original entry on oeis.org
0, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4, 6, 8, 12, 18, 26, 39, 58, 88, 133, 202, 308, 472, 725, 1116, 1725, 2669, 4141, 6437, 10027, 15643, 24448, 38265, 59979, 94143, 147953, 232799, 366725, 578311, 912913, 1442503, 2281429, 3611406, 5721528, 9071789, 14394837
Offset: 0
-
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(a(i), j)*b(n-i*j, i-1), j=0..n/i)))
end:
a:= n-> (k-> `if`(n
A316077
Sequence shifts left five places under Weigh transform with a(n) = signum(n) for n<5.
Original entry on oeis.org
0, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4, 5, 7, 10, 14, 20, 28, 40, 58, 84, 121, 176, 257, 376, 552, 812, 1196, 1767, 2615, 3877, 5757, 8562, 12751, 19018, 28400, 42461, 63554, 95234, 142845, 214473, 322310, 484793, 729797, 1099509, 1657761, 2501299, 3776681
Offset: 0
-
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(a(i), j)*b(n-i*j, i-1), j=0..n/i)))
end:
a:= n-> (k-> `if`(n
A316078
Sequence shifts left six places under Weigh transform with a(n) = signum(n) for n<6.
Original entry on oeis.org
0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4, 5, 6, 9, 12, 16, 23, 31, 43, 61, 85, 118, 168, 236, 333, 475, 674, 958, 1369, 1956, 2796, 4013, 5758, 8270, 11905, 17148, 24720, 35693, 51572, 74573, 107957, 156399, 226740, 329013, 477738, 694148, 1009326, 1468526
Offset: 0
-
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(a(i), j)*b(n-i*j, i-1), j=0..n/i)))
end:
a:= n-> (k-> `if`(n
A316079
Sequence shifts left seven places under Weigh transform with a(n) = signum(n) for n<7.
Original entry on oeis.org
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 11, 14, 19, 26, 35, 48, 65, 89, 122, 167, 230, 317, 438, 606, 840, 1167, 1622, 2260, 3151, 4398, 6148, 8601, 12046, 16888, 23697, 33283, 46783, 65814, 92654, 130539, 184039, 259639, 366533, 517749, 731781
Offset: 0
-
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(a(i), j)*b(n-i*j, i-1), j=0..n/i)))
end:
a:= n-> (k-> `if`(n
A316080
Sequence shifts left eight places under Weigh transform with a(n) = signum(n) for n<8.
Original entry on oeis.org
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 13, 17, 22, 30, 40, 53, 71, 96, 128, 173, 233, 314, 425, 575, 780, 1060, 1442, 1964, 2680, 3658, 5000, 6840, 9366, 12835, 17604, 24164, 33194, 45632, 62775, 86417, 119038, 164077, 226287, 312261, 431138
Offset: 0
-
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(a(i), j)*b(n-i*j, i-1), j=0..n/i)))
end:
a:= n-> (k-> `if`(n
Showing 1-10 of 12 results.
Comments