A000602 -id:A000602 - cp's OEIS frontend

A000628 Number of n-node unrooted steric quartic trees; number of n-carbon alkanes C(n)H(2n+2) taking stereoisomers into account.

1, 1, 1, 1, 2, 3, 5, 11, 24, 55, 136, 345, 900, 2412, 6563, 18127, 50699, 143255, 408429, 1173770, 3396844, 9892302, 28972080, 85289390, 252260276, 749329719, 2234695030, 6688893605, 20089296554, 60526543480, 182896187256, 554188210352, 1683557607211, 5126819371356, 15647855317080, 47862049187447, 146691564302648, 450451875783866, 1385724615285949

Offset: 0

N. J. A. Sloane

Trees are unrooted; nodes are unlabeled and have degree <= 4.
Regarding stereoisomers as different means that only the alternating group A_4 acts at each node, not the full symmetric group S_4. See A000602 for the analogous sequence when stereoisomers are not counted as different.
Has also been described as steric planted trees (paraffins) with n nodes.

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 290.
R. Davies and P. J. Freyd, C_{167}H_{336} is The Smallest Alkane with More Realizable Isomers than the Observable Universe has Particles, Journal of Chemical Education, Vol. 66, 1989, pp. 278-281.
J. L. Faulon, D. Visco and D. Roe, Enumerating Molecules, In: Reviews in Computational Chemistry Vol. 21, Ed. K. Lipkowitz, Wiley-VCH, 2005.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Charles M. Blair and Henry R. Henze, The number of stereoisomeric and non-stereoisomeric paraffin hydrocarbons, J. Amer. Chem. Soc., 54 (1932), 1538-1545.
Charles M. Blair and Henry R. Henze, The number of stereoisomeric and non-stereoisomeric paraffin hydrocarbons, J. Amer. Chem. Soc., 54 (4) (1932), 1538-1545. (Annotated scanned copy)
L. Bytautats and D. J. Klein, Alkane Isomer Combinatorics: Stereostructure enumeration and graph-invariant and molecular-property distributions, J. Chem. Inf. Comput. Sci 39 (1999) 803-818, Table 1.
Lorentz Jäntschi and Lavinia-Lorena Pruteanu, Geometry of C_32 cyclic polyyne and some of its clusters, Carpathian J. Math. (2025) Vol. 41, No. 2, 371-391. See p. 371.
Pierre Leroux and Brahim Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992.
Pierre Leroux and Brahim 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)
R. C. Read, The Enumeration of Acyclic Chemical Compounds, pp. 25-61 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976. [Annotated scanned copy] See p. 44.
R. W. Robinson, F. Harary and A. T. Balaban, The numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron 32 (1976), 355-361.
R. W. Robinson, F. Harary and A. T. Balaban, Numbers of chiral and achiral alkanes and monosubstituted alkanes, Tetrahedron 32 (3) (1976), 355-361. (Annotated scanned copy)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees

Equals A000626 + A000627.

Cf. A000598, A000602, A000625, A010372, A010373, A086194, A086200.

s[0]:=1:s[1]:=1:for n from 0 to 60 do s[n+1/3]:=0 od:for n from 0 to 60 do s[n+2/3]:=0 od:for n from 0 to 60 do s[n+1/4]:=0 od:for n from 0 to 60 do s[n+1/2]:=0 od:for n from 0 to 60 do s[n+3/4]:=0 od:s[ -1]:=0:for n from 1 to 50 do s[n+1]:=(2*n/3*s[n/3]+sum(j*s[j]*sum(s[k]*s[n-j-k],k=0..n-j),j=1..n))/n od:for n from 0 to 50 do q[n]:=sum(s[i]*s[n-i],i=0..n) od:for n from 0 to 50 do q[n-1/2]:=0 od:for n from 0 to 40 do f:=n->(3*s[n]+2*s[n/2]+q[(n-1)/2]-q[n]+2*sum(s[j]*s[n-3*j-1],j=0..n/3))/4 od:seq(f(n),n=0..38); # the formulas for s[n+1] and f(n) are from eq.(4) and (12), respectively, of the Robinson et al. paper; s[n]=A000625(n), f(n)=A000628(n); q[n] is the convolution of s[n] with itself; # Emeric Deutsch

max = 40; s[0] = s[1] = 1; s[] = 0; For[n=1, n <= max, n++, s[n+1] = (2*n/3*s[n/3] + Sum[j*s[j]*Sum[s[k]*s[n-j-k], {k, 0, n-j}], {j, 1, n}])/n]; For[n=0, n <= max, n++, q[n] = Sum[s[i]*s[n-i], {i, 0, n}]]; For[n=0, n <= max, n++, q[n-1/2]=0]; f[n] := (3*s[n] + 2*s[n/2] + q[(n-1)/2] - q[n] + 2*Sum[s[j]*s[n-3*j-1], {j, 0, n/3}])/4; Table[f[n], {n, 0, max}] (* Jean-François Alcover, Dec 29 2014, after Emeric Deutsch *)

Blair and Henze give recurrence (see the Maple code).

For even n a(n) = A086194(n) + A086200(n/2), for odd n a(n) = A086194(n).

Additional comments from Steve Strand (snstrand(AT)comcast.net), Aug 20 2003

More terms from Emeric Deutsch, May 16 2004

A006008 Number of inequivalent ways to color vertices of a regular tetrahedron using <= n colors.

Original entry on oeis.org

0, 1, 5, 15, 36, 75, 141, 245, 400, 621, 925, 1331, 1860, 2535, 3381, 4425, 5696, 7225, 9045, 11191, 13700, 16611, 19965, 23805, 28176, 33125, 38701, 44955, 51940, 59711, 68325, 77841, 88320, 99825, 112421, 126175, 141156, 157435, 175085, 194181, 214800, 237021, 260925, 286595, 314116, 343575

Offset: 0

N. J. A. Sloane, Clint. C. Williams (Clintwill(AT)aol.com)

Here "inequivalent" refers to the rotation group of the tetrahedron, of order 12, with cycle index (x1^4 + 8*x1*x3 + 3*x2^2)/12, which is also the alternating group A_4.
Equivalently, number of distinct tetrahedra that can be obtained by painting its faces using at most n colors. - Lekraj Beedassy, Dec 29 2007
Equals row sums of triangle A144680. - Gary W. Adamson, Sep 19 2008

J.-P. Delahaye, 'Le miraculeux "lemme de Burnside"', 'Le coloriage du tetraedre' pp 147 in 'Pour la Science' (French edition of 'Scientific American') No.350 December 2006 Paris.
Martin Gardner, New Mathematical Diversions from Scientific American. Simon and Schuster, NY, 1966, p. 246.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
R. Gugisch, A. Kerber, R. Laue, M. Meringer and C. Ruecker, Kombinatorische Chemie, eine Herausforderung für Mathematik und Infomatik, Spektrum 1/02, 64-67, 2002.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926. (Annotated scanned copy)
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Eric Weisstein's World of Mathematics, Polyhedron Coloring.
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A006550, A060529.
Cf. A144680. - Gary W. Adamson, Sep 19 2008
Cf. A000332(n+3) (unoriented), A000332 (chiral), A006003 (achiral).
Row 3 of A324999.

[(n^4 + 11*n^2 )/12: n in [0..40]]; // Vincenzo Librandi, Aug 12 2011

A006008 := n->1/12*n^2*(n^2+11);
A006008:=-z*(z+1)*(z**2-z+1)/(z-1)**5; # conjectured by Simon Plouffe in his 1992 dissertation

Table[(n^4+11n^2)/12,{n,0,40}] (* or *) LinearRecurrence[{5,-10,10,-5,1},{0,1,5,15,36},40] (* Harvey P. Dale, Aug 11 2011 *)

apply( {A006008(n)=(n^4+11*n^2)/12}, [0..50]) \\ M. F. Hasler, Jan 26 2020

a(n) = (n^4 + 11*n^2)/12. (Replace all x_i's in the cycle index with n.)
Binomial transform of [1, 4, 6, 5, 2, 0, 0, 0, ...]. - Gary W. Adamson, Apr 23 2008
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5), with a(0)=0, a(1)=1, a(2)=5, a(3)=15, a(4)=36. - Harvey P. Dale, Aug 11 2011
a(n) = C(n,1) + 3C(n,2) + 3C(n,3) + 2C(n,4). Each term indicates the number of tetrahedra with exactly 1, 2, 3, or 4 colors. - Robert A. Russell, Dec 03 2014
a(n) = binomial(n+3,4) + binomial(n,4). - Collin Berman, Jan 26 2016
a(n) = A000332(n+3) + A000332(n) = 2*A000332(n+3) - A006003(n) = 2*A000332(n) + A006003(n).
a(n) = A324999(3,n).
E.g.f.: (1/12)*exp(x)*x*(12 + 18*x + 6*x^2 + x^3). - Stefano Spezia, Jan 26 2020
Sum_{n>=1} 1/a(n) = (6 + 22*Pi^2 - 6*sqrt(11)*Pi*coth(sqrt(11)*Pi))/121. - Amiram Eldar, Aug 23 2022

A000022 Number of centered hydrocarbons with n atoms.

Original entry on oeis.org

0, 1, 0, 1, 1, 2, 2, 6, 9, 20, 37, 86, 181, 422, 943, 2223, 5225, 12613, 30513, 74883, 184484, 458561, 1145406, 2879870, 7274983, 18471060, 47089144, 120528657, 309576725, 797790928, 2062142876, 5345531935, 13893615154, 36201693122

Offset: 0

N. J. A. Sloane, E. M. Rains (rains(AT)caltech.edu)

R. G. Busacker and T. L. Saaty, Finite Graphs and Networks, McGraw-Hill, NY, 1965, p. 201. (They reproduce Cayley's mistakes.)
A. Cayley, "Über die analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen", Chem. Ber. 8 (1875), 1056-1059.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

N. J. A. Sloane, Table of n, a(n) for n = 0..60
Jean-François Alcover, Mathematica program translated from N. J. A. Sloane's Maple program for A000022, A000200, A000598, A000602, A000678
Henry Bottomley, Illustration of initial terms of A000022, A000200, A000602
A. Cayley, On the mathematical theory of isomers, Phil. Mag. vol. 67 (1874), 444-447.
A. Cayley, Über die analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen, Chem. Ber. 8 (1875), 1056-1059. (Annotated scanned copy)
H. R. Henze and C. M. Blair, The number of structurally isomeric alcohols of the methanol series, J. Amer. Chem. Soc., 53 (8) (1931), 3042-3046.
H. R. Henze and C. M. Blair, The number of isomeric hydrocarbons of the methane series, J. Amer. Chem. Soc., 53 (8) (1931), 3077-3085.
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Maple program and first 60 terms for A000022, A000200, A000598, A000602, A000678
Index entries for sequences related to trees

A000022 + A000200 = A000602 for n>0. Cf. A010372.

# We continue from the Maple code in A000678: Unordered 4-tuples of ternary trees with one of height i and others of height at most i-1:
N := 45: i := 1: while i<(N+1) do Tb := t[ i ]-t[ i-1 ]: Ts := t[ i ]-1: Q2 := series(Tb*Ts+O(z^(N+1)),z,200): q2[ i ] := Q2: i := i+1; od: q2[ 0 ] := 0: q[ -1 ] := 0:
for i from 0 to N do c[ i ] := series(q[ i ]-q[ i-1 ]-q2[ i ]+O(z^(N+1)),z,200); od:
# erase height information: i := 'i': cent := series(sum(c[ i ],i=0..N),z,200); G000022 := cent; A000022 := n->coeff(G000022,z,n);
# continued in A000200.

n = 40; (* algorithm from Rains and Sloane *)
S3[f_,h_,x_] := f[h,x]^3/6 + f[h,x] f[h,x^2]/2 + f[h,x^3]/3;
S4[f_,h_,x_] := f[h,x]^4/24 + f[h,x]^2 f[h,x^2]/4 + f[h,x] f[h,x^3]/3 + f[h,x^2]^2/8 + f[h,x^4]/4;
T[-1,z_] := 1;  T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S3[T,h-1,z]z, z], n+1];
Sum[Take[CoefficientList[z^(n+1) + S4[T,h-1,z]z - S4[T,h-2,z]z - (T[h-1,z] - T[h-2,z]) (T[h-1,z]-1),z], n+1], {h,1,n/2}] + PadRight[{0,1}, n+1] (* Robert A. Russell, Sep 15 2018 *)

A131482 a(n) is the number of n-celled polyominoes with perimeter 2n+2.

Original entry on oeis.org

1, 1, 2, 4, 11, 27, 83, 255, 847, 2829, 9734, 33724, 118245, 416816, 1478602, 5267171, 18840144, 67611472, 243378415, 878407170, 3178068821, 11523323634, 41865833602, 152382134767

Offset: 1

Tanya Khovanova, Jul 27 2007

2n+2 is the maximal perimeter of an n-celled polyomino. a(n) is the number of n-celled polyominoes that have a tree as their connectedness graph (vertices of this graph correspond to cells and two vertices are connected if the corresponding cells have a common edge).

Andrew Clarke, Isoperimetrical Polyominoes, The Poly Pages.
Herman Tulleken, Polyominoes 2.2: How they fit together, (2019).

Cf. A000105, A057730. Diagonal of A342243.
A359522 counts only polyominoes with holes.
A002013 counts only unbranched polyominoes.
A038142 is the analog for polyhexes.

a(n) <= A000105(n), a(n) <= A057730(n+1).

a(n) >= A000602(n) [see comment on edge graph trees]. - R. J. Mathar, Mar 08 2021

a(14)-a(16) from David Radcliffe, Dec 25 2017
a(17) from David Radcliffe, Dec 26 2017
a(18)-a(24) from John Mason, Dec 11 2021

A005994 Alkane (or paraffin) numbers l(7,n).

Original entry on oeis.org

1, 3, 9, 19, 38, 66, 110, 170, 255, 365, 511, 693, 924, 1204, 1548, 1956, 2445, 3015, 3685, 4455, 5346, 6358, 7514, 8814, 10283, 11921, 13755, 15785, 18040, 20520, 23256, 26248, 29529, 33099, 36993, 41211, 45790, 50730, 56070, 61810, 67991

Offset: 0

N. J. A. Sloane, Winston C. Yang (yang(AT)math.wisc.edu)

Equals A000217 (1, 3, 6, 10, 15, ...) convolved with A193356 (1, 0, 3, 0, 5, ...). - Gary W. Adamson, Feb 16 2009
F(1,4,n) is the number of bracelets with 1 blue, 4 red and n black beads. If F(1,4,1)=3 and F(1,4,2)=9 taken as a base;
F(1,4,n) = n(n+1)(n+2)/6+F(1,2,n) + F(1,4,n-2). [F(1,2,n) is the number of bracelets with 1 blue, 2 red and n black beads. If F(1,2,1)=2 and F(1,2,2)=4 taken as a base F(1,2,n)=n+1+F(1,2,n-2)]. - Ata Aydin Uslu and Hamdi G. Ozmenekse, Jan 11 2012
a(A254338(n)) = 6 for n > 0. - Reinhard Zumkeller, Feb 27 2015

S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1000
Johann Cigler, Some remarks on Rogers-Szegö polynomials and Losanitsch's triangle, arXiv:1711.03340 [math.CO], 2017.
S. J. Cyvin et al., Polygonal systems including the corannulene and coronene homologs: novel applications of Pólya's theorem, Z. Naturforsch., 52a (1997), 867-873.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926. (Annotated scanned copy)
N. J. A. Sloane, Classic Sequences
Ata Aydin Uslu and Hamdi G. Ozmenekse, Number of bracelets made with 1 blue, 4 red and n black beads.
Ata Aydin Uslu and Hamdi G. Ozmenekse, Number of bracelets made with 1 blue, 2 red and n black beads.
Index entries for linear recurrences with constant coefficients, signature (3, -1, -5, 5, 1, -3, 1).

Cf. A006009, A005997, A005993 (first differences).

Cf. A000217, A005408, A282011.

--  Following Gary W. Adamson.
import Data.List (inits, intersperse)
a005994 n = a005994_list !! n
a005994_list = map (sum . zipWith (*) (intersperse 0 [1, 3 ..]) . reverse) $
                   tail $ inits $ tail a000217_list
-- Reinhard Zumkeller, Feb 27 2015

a:= n -> (Matrix([[1, 0$4, 1, 3]]). Matrix(7, (i,j)-> if (i=j-1) then 1 elif j=1 then [3, -1, -5, 5, 1, -3, 1][i] else 0 fi)^n)[1,1]: seq (a(n), n=0..40); # Alois P. Heinz, Jul 31 2008

LinearRecurrence[{3,-1,-5,5,1,-3,1},{1,3,9,19,38,66,110},50] (* or *) CoefficientList[Series[(1+x^2)/((1-x)^3(1-x^2)^2),{x,0,50}],x] (* Harvey P. Dale, May 02 2011 *)
nn=45;With[{a=Accumulate[Range[nn]],b=Riffle[Range[1,nn,2],0]}, Flatten[ Table[ListConvolve[Take[a,n],Take[b,n]],{n,nn}]]] (* Harvey P. Dale, Nov 11 2011 *)

{a(n)=if(n<-4, n=-5-n); polcoeff( (1+x^2)/((1-x)^3*(1-x^2)^2)+x*O(x^n), n)} /* Michael Somos, Mar 08 2007 */

G.f.: (1+x^2)/((1-x)^3*(1-x^2)^2) = (1+x^2)/((1-x)^5*(1+x)^2).
l(c, r) = 1/2 C(c+r-3, r) + 1/2 d(c, r), where d(c, r) is C((c + r - 3)/2, r/2) if c is odd and r is even, 0 if c is even and r is odd, C((c + r - 4)/2, r/2) if c is even and r is even, C((c + r - 4)/2, (r - 1)/2) if c is odd and r is odd.
a(-5-n)=a(n). - Michael Somos, Mar 08 2007
Euler transform of length 4 sequence [3, 3, 0, -1]. - Michael Somos, Mar 08 2007
a(n) = 3a(n-1) - a(n-2) - 5a(n-3) + 5a(n-4) + a(n-5) - 3a(n-6) + a(n-7), with a(0)=1, a(1)=3, a(2)=9, a(4)=19, a(5)=38, a(6)=66, a(7)=110. - Harvey P. Dale, May 02 2011
a(n) = A006009(n)/2 - A000332(n+4) = ((1/2)*Sum_{i=1..n+1} (i+1)*floor((i+1)^2/2)) - binomial(n+4,4). - Enrique Pérez Herrero, May 11 2012
a(n) = (1/48)*(n+1)*(n+3)*((n+2)*(n+4)+3)+1/32*(2*n+5)*(1+(-1)^n). - Yosu Yurramendi, Jun 20 2013
Conjecture: a(n)+a(n+1) = A203286(n+1). - R. J. Mathar, Mar 08 2025

A144528 Triangle read by rows: T(n,k) is the number of trees on n unlabeled nodes with all nodes of degree <= k (n>=1, 0 <= k <= n-1).

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 2, 3, 0, 0, 1, 4, 5, 6, 0, 0, 1, 6, 9, 10, 11, 0, 0, 1, 11, 18, 21, 22, 23, 0, 0, 1, 18, 35, 42, 45, 46, 47, 0, 0, 1, 37, 75, 94, 101, 104, 105, 106, 0, 0, 1, 66, 159, 204, 223, 230, 233, 234, 235, 0, 0, 1, 135, 355, 473, 520, 539, 546, 549, 550, 551

Offset: 1

N. J. A. Sloane, Dec 20 2008

			Triangle begins:
  1
  0 1
  0 0 1
  0 0 1  2
  0 0 1  2  3
  0 0 1  4  5  6
  0 0 1  6  9 10  11
  0 0 1 11 18 21  22  23
  0 0 1 18 35 42  45  46  47
  0 0 1 37 75 94 101 104 105 106
  ...
From _Andrew Howroyd_, Dec 17 2020: (Start)
Formatted as an array to show the full columns:
================================================
n\k  | 0 1 2   3   4   5   6   7   8   9  10
-----+------------------------------------------
   1 | 1 1 1   1   1   1   1   1   1   1   1 ...
   2 | 0 1 1   1   1   1   1   1   1   1   1 ...
   3 | 0 0 1   1   1   1   1   1   1   1   1 ...
   4 | 0 0 1   2   2   2   2   2   2   2   2 ...
   5 | 0 0 1   2   3   3   3   3   3   3   3 ...
   6 | 0 0 1   4   5   6   6   6   6   6   6 ...
   7 | 0 0 1   6   9  10  11  11  11  11  11 ...
   8 | 0 0 1  11  18  21  22  23  23  23  23 ...
   9 | 0 0 1  18  35  42  45  46  47  47  47 ...
  10 | 0 0 1  37  75  94 101 104 105 106 106 ...
  11 | 0 0 1  66 159 204 223 230 233 234 235 ...
  12 | 0 0 1 135 355 473 520 539 546 549 550 ...
  ...
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Rebecca Neville, Graphs whose vertices are forests with bounded degree, Graph Theory Notes of New York, LIV (2008), 12-21. [Wayback Machine link]

Columns k=2..7 are A000012, A000672, A000602, A036650, A036653, A359392.
The last three diagonals give A144527, A144520, A000055.
Cf. A144215, A238414, A299038.

b[n_, i_, t_, k_] := b[n, i, t, k] = If[i<1, 0, Sum[Binomial[b[i-1, i-1,
  k, k] + j-1, j]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]];
b[0, i_, t_, k_] = 1; a = {}; nmax = 20;
For[ni=2, ni < nmax-1, ni++, (* columns 3 to max-1 *)
  gf[x_] = 1 + Sum[b[j-1, j-1, ni, ni] x^j, {j, 1, nmax}];
  ci[x_] = SymmetricGroupIndex[ni+1, x] /. x[i_] -> gf[x^i];
  a = Append[a, CoefficientList[Normal[Series[
    gf[x] - (gf[x]^2 - gf[x^2])/2 + x ci[x], {x, 0, nmax}]], x]];]
Join[{1, 0, 1, 0, 0, 1}, Table[Join[{0, 0, 1}, Table[a[[k-3]][[n+1]],
{k, 4, n}]], {n, 4, nmax}]] // Flatten (* Robert A. Russell, Feb 05 2023 *)

\\ here V(n,k) gives column k as a vector.
MSet(p,k)={my(n=serprec(p,x)-1); if(min(k,n)<1, 1 + O(x*x^n), polcoef(exp( sum(i=1, min(k,n), (y^i + O(y*y^k))*subst(p + O(x*x^(n\i)), x, x^i)/i ))/(1-y + O(y*y^k)), k, y))}
V(n,k)={my(g=1+O(x)); for(n=2, n, g=x*MSet(g, k-1)); Vec(1 + x*MSet(g, k) + (subst(g, x, x^2) - g^2)/2)}
M(n, m=n)={Mat(vector(m, k, V(n,k-1)[2..1+n]~))}
{ my(T=M(12)); for(n=1, #T~, print(T[n, 1..n])) } \\ Andrew Howroyd, Dec 18 2020

a(53) corrected and terms a(56) and beyond from Andrew Howroyd, Dec 17 2020

A000672 Number of 3-valent trees (= boron trees or binary trees) with n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 4, 6, 11, 18, 37, 66, 135, 265, 552, 1132, 2410, 5098, 11020, 23846, 52233, 114796, 254371, 565734, 1265579, 2841632, 6408674, 14502229, 32935002, 75021750, 171404424, 392658842, 901842517, 2076217086, 4790669518, 11077270335

Offset: 0

N. J. A. Sloane

This can be described in 2 ways: (a) Trees with n nodes of valency <= 3, for n = 0,1,2,3,... (b) Trees with t = 2n+2 nodes of valency either 1 or 3 (implying that there are n nodes of valency 3 - the boron atoms - and n+2 nodes of valency 1 - the hydrogen atoms), for t = 2,4,6,8,...

Essentially the same sequences arises from studying the number of unrooted, unlabeled binary tree topologies with n leaves (see A129860). - Steven Kelk, Jul 22 2016

			The 4 trees with 6 nodes are:
._._._._._. . ._._._._. . ._._._._. . ._._._.
. . . . . . . . | . . . . . . | . . . . | |
G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 11*x^8 + ...

Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.
P. J. Cameron, Oligomorphic Permutation Groups, Cambridge; see Fig. 2 p. 35.
A. Cayley, On the analytical forms called trees, with application to the theory of chemical combinations, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 451).
Joseph Felsenstein, Inferring Phylogenies. Sinauer Associates, Inc., 2004, page 33. Note that at least the first two editions give an incorrect version of this sequence.
R. C. Read, personal communication.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

R. J. Mathar, Table of n, a(n) for n = 0..191 [b-file corrected by _N. J. A. Sloane_, Oct 04 2010]
Dominik Bendle, Janko Boehm, Yue Ren, and Benjamin Schröter, Parallel Computation of tropical varieties, their positive part, and tropical Grassmannians, arXiv:2003.13752 [math.AG], 2020.
Nicolas Broutin and Philippe Flajolet, The distribution of height and diameter in random non-plane binary trees, Random Struct. Algorithms 41, No. 2, 215-252 (2012).
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183.
M. Chan, Tropical hyperelliptic curves, arXiv preprint arXiv:1110.0273 [math.CO], 2011.
Sergio Consoli, Jan Korst, Gijs Geleijnse, and Steffen Pauws, On the minimum quartet tree cost problem, arXiv:1807.00566 [cs.DM], 2018.
S. J. Cyvin, J. Brunvoll, and B. N. Cyvin, Enumeration of constitutional isomers of polyenes, J. Molec. Struct. (Theochem) 357, no. 3 (1995) 255-261.
V. Fack, S. Lievens, and J. Van der Jeugt, On the diameter of the rotation graph of binary coupling trees, Discrete Math. 245 (2002), no. 1-3, 1--18. MR1887046 (2003i:05047).
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, Six-Point Conformal Blocks in the Snowflake Channel, arXiv:2004.02824 [hep-th], 2020.
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, Seven-Point Conformal Blocks in the Extended Snowflake Channel and Beyond, arXiv:2006.13964 [hep-th], 2020.
Jean-François Fortin, Wen-Jie Ma, and Witold Skiba, All Global One- and Two-Dimensional Higher-Point Conformal Blocks, arXiv:2009.07674 [hep-th], 2020.
M. D. Hendy, C. H. C. Little, David Penny, Comparing trees with pendant vertices labelled, SIAM J. Appl. Math. 44 (5) (1984) Table 1
Virginia Perkins Johnson, Enumeration Results on Leaf Labeled Trees, PhD Dissertation, University of South Carolina, 2012. - From _N. J. A. Sloane_, Dec 22 2012
R. Otter, The number of trees, Ann. of Math. (2) 49 (1948), 583-599 discusses asymptotics.
E. M. Rains and N. J. A. Sloane, On Cayley's Enumeration of Alkanes (or 4-Valent Trees), J. Integer Sequences, Vol. 2 (1999), Article 99.1.1.
R. C. Read, Letter to N. J. A. Sloane, Oct. 29, 1976
Eric Weisstein's World of Mathematics, Trivalent Tree
Index entries for sequences related to trees

Column k = 3 of A144528.
A000672 = A000675 + A000673.
Cf. A001190(n+1) (rooted trees).
Cf. A052120, A000022, A000200, A000602, A129860.

(* c = A001190 *) c[n_?OddQ] := c[n] = Sum[c[k]*c[n-k], {k, 1, (n-1)/2}]; c[n_?EvenQ] := c[n] = (1/2)*c[n/2]*(c[n/2] + 1) + Sum[c[k]*c[n-k], {k, 1, n/2-1}]; c[0] = 0; c[1] = 1; b[x_] := If[IntegerQ[x], c[x+1], 0]; a[0] = a[1] = a[2] = 1; a[n_] := b[n/2] - (1/3)*(b[(n-1)/3]-1)*b[(n-1)/3]*(b[(n-1)/3] + 1) + 2*b[n] - b[n+1] - Sum[(1/2)*(b[i]-1)*b[i]*b[-2*i + n - 1], {i, 1, (n-2)/2}] + Sum[b[i]*Sum[b[j]*b[n-i-j-1], {j, i, (1/2)*(n-i-1)}], {i, 1, (n-1)/3}]; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jan 19 2015 *)
n = 50; (* algorithm from Rains and Sloane *)
S2[f_,h_,x_] := f[h,x]^2/2 + f[h,x^2]/2;
S3[f_,h_,x_] := f[h,x]^3/6 + f[h,x] f[h,x^2]/2 + f[h,x^3]/3;
T[-1,z_] := 1;  T[h_,z_] := T[h,z] = Table[z^k, {k,0,n}].Take[CoefficientList[z^(n+1) + 1 + S2[T,h-1,z]z, z], n+1];
Sum[Take[CoefficientList[z^(n+1) + S3[T,h-1,z]z - S3[T,h-2,z]z - (T[h-1,z] - T[h-2,z]) (T[h-1,z]-1),z], n+1], {h,1,n/2}] + PadRight[{1,1}, n+1] + Sum[Take[CoefficientList[z^(n+1) + (T[h,z] - T[h-1,z])^2/2 + (T[h,z^2] - T[h-1,z^2])/2, z],n+1], {h,0,n/2}] (* Robert A. Russell, Sep 15 2018 *)
n = 60; c[n_?OddQ] := c[n] = Sum[c[k]*c[n-k], {k,1,(n-1)/2}];
c[n_?EvenQ] := c[n] = (1/2)*c[n/2]*(c[n/2] + 1) + Sum[c[k]*c[n-k],
  {k,1,n/2-1}]; c[0] = 0; c[1] = 1; (* as in program 1 above *)
gf[x_] := Sum[c[i+1] x^i, {i,0,n}]; (* g.f. for A001190(n+1) *)
ci[x_] := SymmetricGroupIndex[3, x] /. x[i_] -> gf[x^i];
CoefficientList[Normal[Series[gf[x] - (gf[x]^2 - gf[x^2])/2 +
x ci[x], {x,0,n}]], x] (* Robert A. Russell, Jan 17 2023 *)

Rains and Sloane give a g.f.
a(0)=a(1)=a(2)=1, a(n) = 2*b(n+1) - b(n+2) + b((n+1)/2) - 2*C(1+b(n/3), 3) - Sum_{i=1..[(n-1)/2]} C(b(i), 2)*b(n-2*i) + Sum_{i=1..[n/3]} b(i) Sum_{j=i..[(n-i)/2]} b(j)*b(n-i-j), where b(x) = A001190(x+1) if x is an integer, otherwise 0 (Cyvin et al.) [Index of A001190 shifted by R. J. Mathar, Mar 08 2010]
a(n) = A000673(n) + A000675(n).
a(n) ~ c * d^n / n^(5/2), where d = A086317 = 2.4832535361726368585622885181... and c = 1.2551088797592580080398489829149157375... . - Vaclav Kotesovec, Apr 19 2016
G.f.: B(x) - cycle_index(S2,-B(x)) + x * cycle_index(S3,B(x)) = B(x) - (B(x)^2 - B(x^2)) / 2 + x * (B(x)^3 + 3*B(x) B(x^2) + 2*B(x^3)) / 6, where B(x) = 1 + x * cycle_index(S2,B(x)) = 1 + x * (B(x)^2 + B(x^2)) / 2 is the generating function for A001190(n+1). - Robert A. Russell, Jan 17 2023

A005995 Alkane (or paraffin) numbers l(8,n).

Original entry on oeis.org

1, 3, 12, 28, 66, 126, 236, 396, 651, 1001, 1512, 2184, 3108, 4284, 5832, 7752, 10197, 13167, 16852, 21252, 26598, 32890, 40404, 49140, 59423, 71253, 85008, 100688, 118728, 139128, 162384, 188496, 218025, 250971, 287964, 329004, 374794, 425334, 481404, 543004

Offset: 0

N. J. A. Sloane, Winston C. Yang (yang(AT)math.wisc.edu)

From M. F. Hasler, May 01 2009: (Start)
Also, number of 5-element subsets of {1,...,n+5} whose elements sum to an odd integer, i.e. column 5 of A159916.
A linear recurrent sequence with constant coefficients and characteristic polynomial x^9 - 3*x^8 + 8*x^6 - 6*x^5 - 6*x^4 + 8*x^3 - 3*x + 1. (End)
Equals (1/2)*((1, 6, 21, 56, 126, 252, ...) + (1, 0, 3, 0, 6, 0, 10, ...)), see A000389 and A000217.
Equals row sums of triangle A160770.
F(1,5,n) is the number of bracelets with 1 blue, 5 identical red and n identical black beads. If F(1,5,1) = 3 and F(1,5,2) = 12 taken as a base, F(1,5,n) = n(n+1)(n+2)(n+3)/24 + F(1,3,n) + F(1,5,n-2). [F(1,3,n) is the number of bracelets with 1 blue, 3 identical red and n identical black beads. If F(1,3,1) = 2 and F(1,3,2) = 6 taken as a base F(1,3,n) = n(n+1)/2 + [|n/2|] + 1 + F(1,3,n-2)], where [|x|]: if a is an integer and a<=x

S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Winston C. Yang (paper in preparation).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Johann Cigler, Some remarks on Rogers-Szegö polynomials and Losanitsch's triangle, arXiv:1711.03340 [math.CO], 2017.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926. (Annotated scanned copy)
N. J. A. Sloane, Classic Sequences
L. Smith, Polynomial invariants of finite groups. A survey of recent developments. Bull. Amer. Math. Soc. (N.S.) 34 (1997), no. 3, 211-250.
Ata A. Uslu and Hamdi G. Ozmenekse, F(1,3,n)
Ata A. Uslu and Hamdi G. Ozmenekse, F(1,5,n)
Index entries for linear recurrences with constant coefficients, signature (3, 0, -8, 6, 6, -8, 0, 3, -1).

Cf. A160770, A053132 (bisection), A271870 (bisection), A018210 (partial sums).

a:= n-> (Matrix([[1, 0$6, -3, -9]]). Matrix(9, (i,j)-> if (i=j-1) then 1 elif j=1 then [3, 0, -8, 6, 6, -8, 0, 3, -1][i] else 0 fi)^n)[1, 1]: seq(a(n), n=0..40); # Alois P. Heinz, Jul 31 2008

a[n_?OddQ] := 1/240*(n+1)*(n+2)*(n+3)*(n+4)*(n+5); a[n_?EvenQ] := 1/240*(n+2)*(n+4)*(n+6)*(n^2+3*n+5); Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Mar 17 2014, after M. F. Hasler *)
LinearRecurrence[{3, 0, -8, 6, 6, -8, 0, 3, -1},{1, 3, 12, 28, 66, 126, 236, 396, 651},40] (* Ray Chandler, Sep 23 2015 *)

a(k)= if(k%2,(k+1)*(k+3)*(k+5),(k+6)*(k^2+3*k+5))*(k+2)*(k+4)/240 \\ M. F. Hasler, May 01 2009

G.f.: (1+3*x^2)/((1-x)^3*(1-x^2)^3).
a(2n-1) = n(n+1)(n+2)(2n+1)(2n+3)/30, a(2n) = (n+1)(n+2)(n+3)(4n^2+6n+5)/ 30. [M. F. Hasler, May 01 2009]
a(n) = (1/240)*(n+1)*(n+2)*(n+3)*(n+4)*(n+5) + (1/16)*(n+2)*(n+4)*(1/2)*(1+(-1)^n). [Yosu Yurramendi, Jun 20 2013]
a(n) = A038163(n)+3*A038163(n-2). - R. J. Mathar, Mar 29 2018

A005997 Number of paraffins.

Original entry on oeis.org

1, 3, 10, 20, 39, 63, 100, 144, 205, 275, 366, 468, 595, 735, 904, 1088, 1305, 1539, 1810, 2100, 2431, 2783, 3180, 3600, 4069, 4563, 5110, 5684, 6315, 6975, 7696, 8448, 9265, 10115, 11034, 11988, 13015, 14079, 15220, 16400, 17661, 18963, 20350, 21780, 23299

Offset: 1

N. J. A. Sloane

S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Enrique Pérez Herrero, Table of n, a(n) for n = 1..5000
M. Golafshan, M. Rigo, and M. Whiteland, Computing the k-binomial complexity of generalized Thue-Morse words, arXiv:2412.18425 [math.CO], 2024. See p. 29.
S. M. Losanitsch, Die Isomerie-Arten bei den Homologen der Paraffin-Reihe, Chem. Ber. 30 (1897), 1917-1926. (Annotated scanned copy)
Index entries for linear recurrences with constant coefficients, signature (2,1,-4,1,2,-1).

Cf. A005999.

a:= n-> (Matrix([[0, 0, -1, -5, -12, -26]]). Matrix(6, (i, j)-> if (i=j-1) then 1 elif j=1 then [2, 1, -4, 1, 2, -1][i] else 0 fi)^n)[1, 1]: seq (a(n), n=1..50); # Alois P. Heinz, Jul 31 2008

A005997[n_]:=1+Floor[(n-1)/2]+2*(Binomial[n+1,3]-Binomial[Floor[(n+1)/2],3]-Binomial[Ceiling[(n+1)/2],3]); Array[A005997,37] (* Enrique Pérez Herrero, Apr 22 2012 *)
LinearRecurrence[{2, 1, -4, 1, 2, -1}, {1, 3, 10, 20, 39, 63}, 37] (* Bruno Berselli, Apr 22 2012 *)

G.f.: (x^3+3*x^2+x+1)*x / ((-1+x)^2*(-1+x^2)^2).
a(n) = A005999(n) + (n-1)^2. - Enrique Pérez Herrero, Mar 27 2012
a(n) = 1 + floor((n-1)/2) + 2*(C(n+1,3)-C(floor((n+1)/2),3)-C(ceiling((n+1)/2),3)). - Enrique Pérez Herrero, Apr 22 2012
a(n) = (n+1)*(2*n^2-(-1)^n+1)/8. - Bruno Berselli, Apr 22 2012
a(n) = A004526(n) + 2*A111384(n). - Enrique Pérez Herrero, Apr 25 2012
E.g.f.: (x*(3 + 4*x + x^2)*cosh(x) + (1 + 2*x + 4*x^2 + x^3)*sinh(x))/4. - Stefano Spezia, Dec 13 2021

A089022 Number of walks of length 2n on the 3-regular tree beginning and ending at some fixed vertex.

Original entry on oeis.org

1, 3, 15, 87, 543, 3543, 23823, 163719, 1143999, 8099511, 57959535, 418441191, 3043608351, 22280372247, 164008329423, 1213166815047, 9012417249663, 67208553680247, 502920171632943, 3775020828459687, 28415858155984863, 214444848602732247, 1622146752543427983

Offset: 0

Paul Boddington, Nov 11 2003

The generating function for the corresponding sequence for the m-regular tree is 2*(m-1)/(m-2+m*sqrt(1-4*(m-1)*x)). When m=2 this reduces to the usual generating function for the central binomial coefficients.

Hankel transform is A133460. - Philippe Deléham, Dec 01 2007

			a(2) = 15 because there are 3*3=9 walks whose second step is to return to the starting vertex and 3*2=6 walks whose second step is to move away from the starting vertex.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Libor Caha and Daniel Nagaj, The pair-flip model: a very entangled translationally invariant spin chain, arXiv:1805.07168 [quant-ph], 2018.
Pakawut Jiradilok and Supanat Kamtue, Transportation Distance between Probability Measures on the Infinite Regular Tree, arXiv:2107.09876 [math.CO], 2021.
Ed Pegg Jr., K-Cayley Trees

Column k=3 of A183135.

A000602 := x -> 2^x*binomial(2*x, x)-9^x+1/3*2^x*binomial(2*x, x) * hypergeom([1, 2*x+1], [x+1], 2/3); # Tobias Friedrich (tfried(AT)mpi-inf.mpg.de), Jun 12 2007

Table[2^n*Binomial[2*n,n]-3^(n-1)*Sum[(2/3)^k*Binomial[n+k,n],{k,0,n-1}],{n,0,20}] (* or *)
CoefficientList[Series[4/(1+3*Sqrt[1-8*x]), {x, 0, 20}], x] (* Vaclav Kotesovec, Oct 17 2012 *)

my(x='x+O('x^30)); Vec(4/(1+3*sqrt(1-8*x))) \\ Joerg Arndt, May 10 2013

G.f.: 4/(1+3*sqrt(1-8*x)).
a(n) = 2^n * binomial(2*n,n) - 3^(n-1) * Sum_{j=0..n-1} (2/3)^j*binomial(n+j,n). - Tobias Friedrich (tfried(AT)mpi-inf.mpg.de), Jun 12 2007
a(n) = Sum_{k=0..n} A039599(n,k)*2^(n-k). - Philippe Deléham, Aug 25 2007
From Paul Barry, Sep 04 2009: (Start)
G.f.: 1/(1-3x/(1-2x/(1-2x/(1-2x/(1-2x/(1-... (continued fraction);
G.f.: (1-2*x*c(x))/(1-3*x-2*x*c(x)), where c(x) is the g.f. of A000108. (End)
a(n) = A126087(2n). - Philippe Deléham, Nov 02 2011
D-finite with recurrence n*a(n) + (12-17*n)*a(n-1) + 36*(2n-3)*a(n-2) = 0. - R. J. Mathar, Nov 14 2011
a(n) ~ 6*8^n/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 17 2012
From Karol A. Penson, Sep 06 2014: (Start)
a(n) is the (2*n)-th moment of a positive function W(x) = (3/Pi)*sqrt(8-x^2)/(9-x^2), on the segment x = (0,2*sqrt(2)): a(n) = Integral_{x=0..2*sqrt(2)} x^(2*n)*W(x) dx;
a(n) is the special value of hypergeometric function 2F1, in Maple notation: a(n)=2*8^n*GAMMA(n+1/2)*hypergeom([1,n+1/2],[n+2],8/9)/(3*sqrt(Pi)*(n+1)!). (End)
a(n) = A151374(n)*hypergeom([1,n+1/2],[n+2],8/9)*(2/3). - Peter Luschny, Sep 06 2014

Previous Showing 21-30 of 76 results. Next

cp's OEIS Frontend

A000628 Number of n-node unrooted steric quartic trees; number of n-carbon alkanes C(n)H(2n+2) taking stereoisomers into account.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A006008 Number of inequivalent ways to color vertices of a regular tetrahedron using <= n colors.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A000022 Number of centered hydrocarbons with n atoms.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

A131482 a(n) is the number of n-celled polyominoes with perimeter 2n+2.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A005994 Alkane (or paraffin) numbers l(7,n).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A144528 Triangle read by rows: T(n,k) is the number of trees on n unlabeled nodes with all nodes of degree <= k (n>=1, 0 <= k <= n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A000672 Number of 3-valent trees (= boron trees or binary trees) with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links