A000220 -id:A000220 - cp's OEIS frontend

A004111 Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).

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

N. J. A. Sloane

The nodes are unlabeled.
There is a natural correspondence between rooted identity trees and finitary sets (sets whose transitive closure is finite); each node represents a set, with the children of that node representing the members of that set. When the set corresponding to an identity tree is written out using braces, there is one set of braces for each node of the tree; thus a(n) is also the number of sets that can be made using n pairs of braces. - Franklin T. Adams-Watters, Oct 25 2011
Shifts left under WEIGH transform. - Franklin T. Adams-Watters, Jan 17 2007
Is this the sequence mentioned in the middle of page 355 of Motzkin (1948)? - N. J. A. Sloane, Jul 04 2015. Answer from David Broadhurst, Apr 06 2022: The answer is No. Motzkin was considering a sequence asymptotic to Catalan(n)/(4*n), namely A006082, which begins 1, 1, 1, 2, 3, 6, 12, 27, ... but he miscalculated and got 1, 1, 1, 2, 3, 6, 12, 25, ... instead! - N. J. A. Sloane, Apr 06 2022

			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

Cf. A000009, A000081, A000220, A196118, A196154, A196161, A227819.
Cf. A027750, A035056, A246169.
Column k=1 of A255517, A316074, A316101, A318757.

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

Recurrence: a(n+1) = (1/n) * Sum_{k=1..n} ( Sum_{d|k} (-1)^(k/d+1) d*a(d) ) * a(n-k+1). - Mitchell Harris, Dec 02 2004
G.f. satisfies A(x) = x*exp(A(x) - A(x^2)/2 + A(x^3)/3 - A(x^4)/4 + ...). [Harary and Prins]
Also A(x) = Sum_{n >= 1} a(n)*x^n = x * Product_{n >= 1} (1+x^n)^a(n).
a(n) ~ c * d^n / n^(3/2), where d = A246169 = 2.51754035263200389079535..., c = 0.3625364233974198712298411097408713812865256408189512533230825639621448038... . - Vaclav Kotesovec, Aug 22 2014, updated Dec 26 2020

A246169 Decimal expansion of a constant related to identity trees.

Original entry on oeis.org

2, 5, 1, 7, 5, 4, 0, 3, 5, 2, 6, 3, 2, 0, 0, 3, 8, 9, 0, 7, 9, 5, 3, 5, 4, 5, 9, 8, 4, 6, 3, 4, 4, 7, 2, 7, 7, 3, 3, 5, 9, 8, 1, 2, 6, 6, 8, 0, 3, 1, 1, 8, 4, 6, 3, 4, 3, 7, 3, 4, 8, 2, 2, 0, 8, 0, 7, 9, 1, 5, 9, 4, 3, 2, 2, 3, 2, 7, 4, 1, 4, 4, 1, 1, 8, 7, 5, 4, 3, 1, 5, 3, 8, 5, 4, 8, 3, 4, 5, 9, 5, 6, 2, 3, 8

Offset: 1

Vaclav Kotesovec, Aug 25 2014

			2.51754035263200389079535459846344727733598126680311846...

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 301 and 562.

A. Genitrini, Full asymptotic expansion for Polya structures, arXiv:1605.00837 [math.CO], May 03 2016, p. 8.

Cf. A000220, A035056, A004111, A227806.

Equals lim n -> infinity A000220(n)^(1/n).
Equals lim n -> infinity A035056(n)^(1/n).
Equals lim n -> infinity A004111(n)^(1/n).

More digits from Vaclav Kotesovec, Dec 26 2020

A355051 Number of asymmetric orthoplex n-ominoes with cell centers determining n-3 space.

Original entry on oeis.org

6, 67, 412, 1926, 7856, 29057, 101105, 335081, 1072653, 3337131, 10154700, 30330869, 89226443, 259092076, 744095757, 2116643127, 5971171140, 16722250081, 46529076097, 128722040503, 354276958783, 970546150818

Offset: 7

Robert A. Russell, Jun 16 2022

Orthoplex polyominoes are connected sets of cells of regular tilings with Schläfli symbols {}, {4}, {3,4}, {3,3,4}, {3,3,3,4}, etc. These are tilings of regular orthoplexes projected on their circumspheres. Orthoplex polyominoes are equivalent to multidimensional polyominoes that do not extend more than two units along any axis, i.e., fit within a 2^d cube. An asymmetric polyomino has a symmetry group of order 1.

			a(7)=6 because there are 6 asymmetric heptominoes in 2^4 space. See trunks 1, 6, 8, 12, 27, and 28 in the linked Trunk Generating Functions.

Robert A. Russell, Table of n, a(n) for n = 7..100
Robert A. Russell, Trunk Generating Functions

Cf. A355047 (oriented), A355048 (unoriented), A355049 (chiral) A355050 (achiral), A004111 (rooted asymmetric).

Other dimensions: A036369 (n-2), A000220 (n-1), A355056 (multidimensional).

sa[n_, k_] := sa[n, k] = a[n+1-k, 1] + If[n < 2 k, 0, -sa[n-k, k]];
a[1, 1] := 1; a[n_, 1] := a[n, 1] = Sum[a[i, 1] sa[n-1, i] i, {i, 1, n-1}]/(n-1);
a[n_, k_] := a[n, k] = Sum[a[i, 1] a[n-i, k-1], {i, 1, n-1}];
nmax = 30; A[x_] := Sum[a[i, 1] x^i, {i, 0, nmax}]
Drop[CoefficientList[Series[(14 A[x]^6 + 103 A[x]^7 + 24 A[x]^8 - 6 A[x]^4 A[x^2] - 12 A[x]^5 A[x^2] - 24 A[x]^6 A[x^2] - 18 A[x]^2 A[x^2]^2 + 15 A[x]^3 A[x^2]^2 - 14 A[x^2]^3 + 8 A[x] A[x^2]^3 + 6 A[x]^2 A[x^2]^3 + 4 A[x^3]^2 - 4 A[x] A[x^3]^2 + 24 A[x^2] A[x^4] - 18 A[x] A[x^2] A[x^4] - 6 A[x]^2 A[x^2] A[x^4] - 4 A[x^6] + 4 A[x] A[x^6])/(24 (1-A[x])) + A[x]^6 (5 A[x] + 16 A[x]^2 + 6 A[x]^3 - A[x^2] - 2 A[x] A[x^2])/(2 (1-A[x])^2) - A[x^2] (A[x]^4 A[x^2] + 8 A[x] A[x^2]^2 + 2 A[x]^2 A[x^2]^2 + 10 A[x^2]^3 + 5 A[x] A[x^2]^3 - 2 A[x] A[x^4] - 3 A[x^2] A[x^4] - A[x] A[x^2] A[x^4])/(4 (1-A[x^2])) + A[x]^7 (2 + 42 A[x] + 51 A[x]^2 + 24 A[x]^3 - 3 A[x^2])/(12 (1-A[x])^3) - A[x]^2 A[x^2]^2 (2 A[x] + 5 A[x]^3 + 2 A[x^2] - A[x] A[x^2])/(4 (1-A[x]) (1-A[x^2])) + A[x] A[x^3]^2/(1-A[x^3])/3 + A[x]^9 (17 + 8 A[x])/(8 (1-A[x])^4) - A[x]^5 (1 + 4 A[x]) A[x^2]^2/(4 (1-A[x])^2 (1-A[x^2])) - A[x^2]^4 (8 + 17 A[x] + 16 A[x^2] + 8 A[x] A[x^2])/(8 (1-A[x^2])^2) + A[x] (A[x^4]^2/(1-A[x^4]))/4 + 3 A[x]^10/(8 (1-A[x])^5) - A[x]^6 A[x^2]^2/(4 (1-A[x])^3 (1-A[x^2])) - A[x]^2 A[x^2]^4/(8 (1-A[x]) (1-A[x^2])^2) - 3 (1 + A[x]) A[x^2]^5/(4 (1-A[x^2])^3) +3 (1 + A[x]) A[x^2] A[x^4]^2/(4 (1-A[x^2]) (1-A[x^4])), {x,0,nmax}], x], 7]

G.f.: (14 A(x)^6 + 103 A(x)^7 + 24 A(x)^8 - 6 A(x)^4 A(x^2) - 12 A(x)^5 A(x^2) - 24 A(x)^6 A(x^2) - 18 A(x)^2 A(x^2)^2 + 15 A(x)^3 A(x^2)^2 - 14 A(x^2)^3 + 8 A(x) A(x^2)^3 + 6 A(x)^2 A(x^2)^3 + 4 A(x^3)^2 - 4 A(x) A(x^3)^2 + 24 A(x^2) A(x^4) - 18 A(x) A(x^2) A(x^4) - 6 A(x)^2 A(x^2) A(x^4) - 4 A(x^6) + 4 A(x) A(x^6))/(24 (1 - A(x))) +A(x)^6 (5 A(x) + 16 A(x)^2 + 6 A(x)^3 - A(x^2) - 2 A(x) A(x^2))/(2 (1 - A(x))^2) - A(x^2) (A(x)^4 A(x^2) + 8 A(x) A(x^2)^2 + 2 A(x)^2 A(x^2)^2 + 10 A(x^2)^3 + 5 A(x) A(x^2)^3 - 2 A(x) A(x^4) - 3 A(x^2) A(x^4) - A(x) A(x^2) A(x^4))/(4 (1 - A(x^2))) + A(x)^7 (2 + 42 A(x) + 51 A(x)^2 + 24 A(x)^3 - 3 A(x^2))/(12 (1 - A(x))^3) - A(x)^2 A(x^2)^2 (2 A(x) + 5 A(x)^3 + 2 A(x^2) - A(x) A(x^2))/(4 (1 - A(x)) (1 - A(x^2))) + A(x) A(x^3)^2/(1 - A(x^3))/3 + A(x)^9 (17 + 8 A(x))/(8 (1 - A(x))^4) - A(x)^5 (1 + 4 A(x)) A(x^2)^2/(4 (1 - A(x))^2 (1 - A(x^2))) - A(x^2)^4 (8 + 17 A(x) + 16 A(x^2) + 8 A(x) A(x^2))/(8 (1 - A(x^2))^2) + A(x) (A(x^4)^2/(1 - A(x^4)))/4 + 3 A(x)^10/(8 (1 - A(x))^5) - A(x)^6 A(x^2)^2/(4 (1 - A(x))^3 (1 - A(x^2))) - A(x)^2 A(x^2)^4/(8 (1 - A(x)) (1 - A(x^2))^2) - 3 (1 + A(x)) A(x^2)^5/(4 (1 - A(x^2))^3) + 3 (1 + A(x)) A(x^2) A(x^4)^2/(4 (1 - A(x^2)) (1 - A(x^4))) where A(x) is the generating function for rooted identity trees with n nodes in A004111.

A055334 Number of asymmetric (identity) trees with n nodes and k leaves.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 3, 3, 0, 0, 0, 4, 8, 3, 0, 0, 5, 14, 10, 0, 0, 0, 7, 25, 29, 6, 0, 0, 8, 40, 65, 25, 1, 0, 0, 10, 62, 135, 90, 13, 0, 0, 12, 89, 252, 244, 69, 1, 0, 0, 14, 127, 445, 591, 276, 27, 0, 0, 16, 173, 739, 1273, 868, 172, 3, 0, 0, 19

Offset: 1

Christian G. Bower, May 12 2000

A pair of zeros marks the next row.

			1; 0; 0; 0; 0; 0; 0,0,1; 0,0,1; 0,0,2,1; 0,0,3,3; 0,0,4,8,3; ...

Index entries for sequences related to trees

Row sums give A000220. Columns 3 through 8: A001399(n-7), A055335-A055339.

G.f.: A(x, y)=(1-x+x*y)*B(x, y)-(1/2)*(B(x, y)^2+B(x^2, y^2)). B(x, y): g.f. of A055327.

A355056 Number of asymmetric multidimensional n-ominoes with cell centers determining n-3 space.

Original entry on oeis.org

5, 46, 275, 1283, 5281, 19607, 68476, 227196, 727780, 2263148, 6881482, 20529511, 60312548, 174870492, 501443277, 1424142358, 4011274417, 11216074419, 31160837273, 86078096135, 236568911194, 647181951619

Offset: 5

Robert A. Russell, Jun 16 2022

Multidimensional polyominoes are connected sets of cells of regular tilings with Schläfli symbols {oo}, {4,4}, {4,3,4}, {4,3,3,4}, etc. Each tile is a regular orthotope (hypercube). An asymmetric polyomino has a symmetry group of order 1.

			a(5)=5 as there are exactly five asymmetric pentominoes in 2-space.

Robert A. Russell, Table of n, a(n) for n = 5..100
Robert A. Russell, Trunk Generating Functions

Cf. A355052 (oriented), A355053 (unoriented), A355054 (chiral), A355055 (achiral), A191092 (fixed), A004111 (rooted asymmetric).

Other dimensions: A036366 (n-2), A000220 (n-1), A355051 (orthoplex).

sa[n_, k_] := sa[n, k] = a[n+1-k, 1] + If[n < 2 k, 0, -sa[n-k, k]];
a[1, 1] := 1; a[n_, 1] := a[n, 1] = Sum[a[i, 1] sa[n-1, i] i, {i, 1, n-1}]/(n-1);
a[n_, k_] := a[n, k] = Sum[a[i, 1] a[n-i, k-1], {i, 1, n-1}];
nmax = 30; A[x_] := Sum[a[i, 1] x^i, {i, 0, nmax}]
Drop[CoefficientList[Series[(4 A[x]^4 + 37 A[x]^5 + 12 A[x]^6 - 6 A[x]^3 A[x^2] - 10 A[x]^4 A[x^2] - 4 A[x^2]^2 - 17 A[x] A[x^2]^2 - 2 A[x^2]^3 + 2 A[x] A[x^4]) / 8 + (24 A[x]^5 + 515 A[x]^6 + 325 A[x]^7 + 24 A[x]^8 - 48 A[x]^4 A[x^2] - 96 A[x]^5 A[x^2] - 24 A[x]^6 A[x^2] - 21 A[x]^2 A[x^2]^2 + 21 A[x]^3 A[x^2]^2 - 14 A[x^2]^3 + 8 A[x] A[x^2]^3 + 6 A[x]^2 A[x^2]^3 + 4 A[x^3]^2 - 4 A[x] A[x^3]^2 + 24 A[x^2] A[x^4] - 18 A[x] A[x^2] A[x^4] - 6 A[x]^2 A[x^2] A[x^4] - 4 A[x^6] + 4 A[x] A[x^6]) / (24 (1-A[x])) + A[x]^5 (2 A[x] + 67 A[x]^2 + 46 A[x]^3 + 6 A[x]^4 - 3 A[x^2] - 6 A[x] A[x^2] - 2 A[x]^2 A[x^2]) / (2 (1-A[x])^2) - A[x^2] (2 A[x]^2 A[x^2] + 6 A[x]^3 A[x^2] + 2 A[x]^4 A[x^2] + 13 A[x^2]^2 + 31 A[x] A[x^2]^2 + 2 A[x]^2 A[x^2]^2 + 15 A[x^2]^3 + 5 A[x] A[x^2]^3 - 3 A[x^4] - 5 A[x] A[x^4] - 3 A[x^2] A[x^4] - A[x] A[x^2] A[x^4]) / (4 (1-A[x^2])) + A[x]^6 (4 A[x] + 153 A[x]^2 + 75 A[x]^3 + 12 A[x]^4 - 3 A[x^2] - 3 A[x] A[x^2]) / (6 (1-A[x])^3) - A[x]^2 A[x^2]^2 (2 A[x] + 7 A[x]^2 + 5 A[x]^3 + A[x^2] - A[x] A[x^2]) / (2 (1-A[x]) (1-A[x^2])) + A[x] A[x^3]^2 / (1-A[x^3]) / 3 + A[x]^9 (21 + 4 A[x]) / (2 (1-A[x])^4) - A[x]^5 (3 + 2 A[x]) A[x^2]^2 / ((1-A[x])^2 (1-A[x^2])) - A[x^2]^4 (5 + 7 A[x] + 3 A[x^2] + A[x] A[x^2]) / (1-A[x^2])^2 + A[x] A[x^4]^2 / (2 (1-A[x^4])) + 3 A[x]^10 / (2 (1-A[x])^5) - A[x]^6 A[x^2]^2 / ((1-A[x])^3 (1-A[x^2])) - 2 (1 + A[x]) A[x^2]^5 / (1-A[x^2])^3 + 3 (1 + A[x]) A[x^2] A[x^4]^2 / (2 (1-A[x^2]) (1-A[x^4])), {x,0,nmax}], x], 5]

G.f.: (4 A(x)^4 + 37 A(x)^5 + 12 A(x)^6 - 6 A(x)^3 A(x^2) - 10 A(x)^4 A(x^2) - 4 A(x^2)^2 - 17 A(x) A(x^2)^2 - 2 A(x^2)^3 + 2 A(x) A(x^4)) / 8 + (24 A(x)^5 + 515 A(x)^6 + 325 A(x)^7 + 24 A(x)^8 - 48 A(x)^4 A(x^2) - 96 A(x)^5 A(x^2) - 24 A(x)^6 A(x^2) - 21 A(x)^2 A(x^2)^2 + 21 A(x)^3 A(x^2)^2 - 14 A(x^2)^3 + 8 A(x) A(x^2)^3 + 6 A(x)^2 A(x^2)^3 + 4 A(x^3)^2 - 4 A(x) A(x^3)^2 + 24 A(x^2) A(x^4) - 18 A(x) A(x^2) A(x^4) - 6 A(x)^2 A(x^2) A(x^4) - 4 A(x^6) + 4 A(x) A(x^6)) / (24 (1-A(x))) + A(x)^5 (2 A(x) + 67 A(x)^2 + 46 A(x)^3 + 6 A(x)^4 - 3 A(x^2) - 6 A(x) A(x^2) - 2 A(x)^2 A(x^2)) / (2 (1-A(x))^2) - A(x^2) (2 A(x)^2 A(x^2) + 6 A(x)^3 A(x^2) + 2 A(x)^4 A(x^2) + 13 A(x^2)^2 + 31 A(x) A(x^2)^2 + 2 A(x)^2 A(x^2)^2 + 15 A(x^2)^3 + 5 A(x) A(x^2)^3 - 3 A(x^4) - 5 A(x) A(x^4) - 3 A(x^2) A(x^4) - A(x) A(x^2) A(x^4)) / (4 (1-A(x^2))) + A(x)^6 (4 A(x) + 153 A(x)^2 + 75 A(x)^3 + 12 A(x)^4 - 3 A(x^2) - 3 A(x) A(x^2)) / (6 (1-A(x))^3) - A(x)^2 A(x^2)^2 (2 A(x) + 7 A(x)^2 + 5 A(x)^3 + A(x^2) - A(x) A(x^2)) / (2 (1-A(x)) (1-A(x^2))) + A(x) A(x^3)^2 / (1-A(x^3)) / 3 + A(x)^9 (21 + 4 A(x)) / (2 (1-A(x))^4) - A(x)^5 (3 + 2 A(x)) A(x^2)^2 / ((1-A(x))^2 (1-A(x^2))) - A(x^2)^4 (5 + 7 A(x) + 3 A(x^2) + A(x) A(x^2)) / (1-A(x^2))^2 + A(x) A(x^4)^2 / (2 (1-A(x^4))) + 3 A(x)^10 / (2 (1-A(x))^5) - A(x)^6 A(x^2)^2 / ((1-A(x))^3 (1-A(x^2))) - 2 (1 + A(x)) A(x^2)^5 / (1-A(x^2))^3 + 3 (1 + A(x)) A(x^2) A(x^4)^2 / (2 (1-A(x^2)) (1-A(x^4))) where A(x) is the generating function for rooted identity trees with n nodes in A004111.

A035056 Number of asymmetric forests with n nodes.

Original entry on oeis.org

1, 1, 0, 0, 0, 0, 0, 1, 2, 4, 9, 21, 44, 96, 206, 450, 981, 2159, 4757, 10571, 23563, 52835, 118939, 269047, 610878, 1392677, 3186001, 7313882, 16842202, 38900699, 90098260, 209229601, 487077685, 1136549747, 2657859059, 6228447488, 14624515804, 34402798404

Offset: 0

Christian G. Bower, Oct 15 1998

nonn

Steven R. Finch, Mathematical Constants, Cambridge, 2003, p. 301 and 562.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
N. J. A. Sloane, Transforms
Index entries for sequences related to forests

Cf. A000220, A004111, A005195, A246169.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(b((i-1)$2), j)*b(n-i*j, i-1), j=0..n/i)))
    end:
g:= n-> b((n-1)$2):
h:= proc(n) option remember; g(n)-add(g(i)*g(n-i), i=0..n)/2
       -`if`(irem(n, 2)=1, 0, g(n/2))/2
    end:
f:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(h(i), j)*f(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> f(n, n):
seq(a(n), n=0..40);  # Alois P. Heinz, May 20 2013

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[b[i-1, i-1], j]*b[n-i*j, i-1], {j, 0, n/i}]]]; g[n_] := b[n-1, n-1]; h[n_] := h[n] = g[n] - Sum[g[i]*g[n-i], {i, 0, n}]/2 - If[Mod[n, 2]==1, 0, g[n/2]]/2; f[n_, i_] := f[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[h[i], j]*f[n - i*j, i-1], {j, 0, n/i}]]]; a[n_] := f[n, n]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 21 2016, after Alois P. Heinz *)

Weigh transform of A000220.

a(n) ~ c * d^n / n^(5/2), where d = A246169 = 2.51754035263200389079535..., c = 0.421943694962576031011358... . - Vaclav Kotesovec, Aug 25 2014

A038080 Number of identity trees with 3-colored nodes.

Original entry on oeis.org

1, 3, 3, 9, 39, 189, 981, 5490, 31674, 189954, 1170126, 7382745, 47494197, 310712808, 2061987642, 13855192866, 94113385437, 645424668666, 4464027720900, 31110200069511, 218292811705458, 1541172223659249

Offset: 0

Christian G. Bower, Jan 04 1999

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
Index entries for sequences related to trees

Cf. A000220, A038077-A038079, A052757, A255517.

G.f.: B(x) - B^2(x)/2 - B(x^2)/2, where B(x) is g.f. for A038079.

a(n) ~ c * d^n / n^(5/2), where d = 7.969494030514425004826375511986491746399264355846412073489715938... and c = 0.3712461766927875417276388215355520756010680416348018056669... - Vaclav Kotesovec, Dec 26 2020

A038078 Number of identity trees with 2-colored nodes.

Original entry on oeis.org

1, 2, 1, 2, 6, 20, 69, 270, 1026, 4120, 16794, 70230, 298306, 1288912, 5642559, 25007756, 111998920, 506348902, 2308338456, 10602357346, 49026021552, 228085486580, 1067020210339, 5016982766202, 23698640081356, 112422573858292, 535414026652828, 2559204304109868

Offset: 0

Christian G. Bower, Jan 04 1999

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..500
Index entries for sequences related to trees

Cf. A000220. A038077-A038080.

Cf. A246312.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(2*b(i-1$2), j)*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n=0, 1, 2*b(n-1$2) -2*add(b(j-1$2)*b(n-j-1$2)
        , j=1..n-1) -`if`(irem(n, 2, 'r')=0, b(r-1$2), 0)):
seq(a(n), n=0..35);  # Alois P. Heinz, Aug 02 2013

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[2*b[i-1, i-1], j]*b[n-i*j, i-1], {j, 0, n/i}]]];
a[n_] := If[n==0, 1, 2*b[n-1, n-1] - 2*Sum[b[j-1, j-1]*b[n-j-1, n-j-1], {j, 1, n-1}] - If[Mod[n, 2]==0, r=n/2; b[r-1, r-1], 0]];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Mar 01 2016, after Alois P. Heinz *)

G.f.: B(x) - B^2(x)/2 - B(x^2)/2, where B(x) is g.f. for A038077.

a(n) ~ c * d^n / n^(5/2), where d = A246312 = 5.2490324912281705791649522161843092..., c = 0.356142078281568492877259973613... . - Vaclav Kotesovec, Sep 06 2014

A352764 Smallest number of edges in an asymmetric n-node graph, or -1 if no such graph exists.

Original entry on oeis.org

0, -1, -1, -1, -1, 6, 6, 6, 7, 8, 9, 10, 11, 12, 13, 13, 14, 15, 16, 17, 18, 19, 20, 21, 21, 22, 23, 24, 25, 26, 27, 28, 29, 29, 30, 31, 32, 33, 34, 35, 36, 37, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 55, 56, 57, 58, 59

Offset: 1

Pontus von Brömssen, Apr 02 2022

sign

For n >= 7, there exists an asymmetric forest with n nodes and a(n) edges. Proof: Let G be a graph with n nodes and a(n) edges, and assume that it has a cyclic component C, which must have at least 6 nodes. (The only asymmetric graph with less than 6 nodes is the 1-node graph.) There exist asymmetric trees of all orders >= 7, so a(n) < n and at least one component of G must be a tree. Let T be such a component with the largest number of nodes. If we replace C and T with an asymmetric tree, keeping the total number of nodes fixed, the resulting graph is still asymmetric (the new tree is larger than all other acyclic components in G), has a(n) edges (by definition, it cannot have less than a(n) edges, so C can only have one cycle), and one cyclic component less than G. This process can be repeated until an acyclic graph with a(n) edges and n nodes is obtained.

For some n, there also exist cyclic asymmetric graphs with a(n) edges, e.g., when n = 6, 7, 14, or 15. This is likely to occur when n is just below Sum_{k=1..m} t(k) for some m, with t(k) as defined in the Formula section.

Pontus von Brömssen, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Identity Graph
Wikipedia, Asymmetric graph

Cf. A000220, A352765 (number of extremal graphs).

For n >= 7, a(n) = n-m, where m is the largest positive integer with Sum_{k=1..m} t(k) <= n and t(k) is the order of the k-th largest asymmetric tree (so the sequence (t(k)) is nondecreasing and has A000220(j) occurrences of j).

A036366 Number of asymmetric n-ominoes in n-2 space.

Original entry on oeis.org

0, 1, 4, 13, 42, 113, 309, 792, 2049, 5167, 13071, 32724, 82006, 204619, 510655, 1272101, 3168971, 7888446, 19636642, 48868367, 121621466, 302673515, 753319709, 1875049668, 4667676111, 11620911254, 28936281066, 72062264255

Offset: 3

Robert A. Russell

			0 asymmetric trominoes in 1-space;
1 asymmetric tetromino in 2-space;
4 asymmetric pentominoes in 3-space.

W. F. Lunnon, Counting Multidimensional Polyominoes, Computer Journal, Vol. 18 (1975), pp. 366-67.

Cf. A004111, A000220, A036365.

sa[ n_, k_ ] := sa[ n, k ]=a[ n+1-k, 1 ]+If[ n<2k, 0, -sa[ n-k, k ] ]; a[ 1, 1 ] := 1;
a[ n_, 1 ] := a[ n, 1 ]=Sum[ a[ i, 1 ]sa[ n-1, i ]i, {i, 1, n-1} ]/(n-1);
a[ n_, k_ ] := a[ n, k ]=Sum[ a[ i, 1 ]a[ n-i, k-1 ], {i, 1, n-1} ];
Table[ a[ i, 3 ]/2+5a[ i, 4 ]/8+Sum[ a[ i, j ], {j, 5, i} ]-If[ OddQ[ i ], 0, 5a[ i/2, 2 ]/8
-If[ OddQ[ i/2 ], 0, a[ i/4, 1 ]/4 ]+Sum[ a[ i/2, j ], {j, 3, i/2} ] ]
-Sum[ a[ j, 1 ](a[ i-2j, 1 ]/2+a[ i-2j, 2 ]/4)+Sum[ If[ OddQ[ k ], a[ j,
(k-1)/2 ]a[ i-2j, 1 ], 0 ], {k, 5, i} ], {j, 1, (i-1)/2} ], {i, 3, 30} ]

G.f.: A^3(x)/2 - A(x)A(x^2)/2 + 5A^4(x)/8 - A^2(x)A(x^2)/4 - 5A^2(x^2)/8 + A(x^4)/4 + A^5(x)/(1-A(x)) - (A(x)+A(x^2))*A^2(x^2)/(1-A(x^2)), where A(x) is the generating function for rooted identity trees with n nodes (that is, the g.f. of sequence A004111).

cp's OEIS Frontend

A004111 Number of rooted identity trees with n nodes (rooted trees whose automorphism group is the identity group).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A246169 Decimal expansion of a constant related to identity trees.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions

A355051 Number of asymmetric orthoplex n-ominoes with cell centers determining n-3 space.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A055334 Number of asymmetric (identity) trees with n nodes and k leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A355056 Number of asymmetric multidimensional n-ominoes with cell centers determining n-3 space.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A035056 Number of asymmetric forests with n nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A038080 Number of identity trees with 3-colored nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A038078 Number of identity trees with 2-colored nodes.

Views

Author

Keywords

Links