A271831 -id:A271831 - cp's OEIS frontend

A095268 Number of distinct degree sequences among all n-vertex graphs with no isolated vertices.

1, 0, 1, 2, 7, 20, 71, 240, 871, 3148, 11655, 43332, 162769, 614198, 2330537, 8875768, 33924859, 130038230, 499753855, 1924912894, 7429160296, 28723877732, 111236423288, 431403470222, 1675316535350, 6513837679610, 25354842100894, 98794053269694, 385312558571890, 1504105116253904, 5876236938019298, 22974847399695092

Offset: 0

Eric W. Weisstein, May 31 2004

nonn

A002494 is the number of graphs on n nodes with no isolated points and A095268 is the number of these graphs having distinct degree sequences.
Now that more terms have been computed, we can see that this is not the self-convolution of any integer sequence. - Paul D. Hanna, Aug 18 2006
Is it true that a(n+1)/a(n) tends to 4? Is there a heuristic argument why this might be true? - Gordon F. Royle, Aug 29 2006
Previous values a(30) = 5876236938019300 from Lorand Lucz, Jul 07 2013 and a(31) = 22974847474172100 from Lorand Lucz, Sep 03 2013 are wrong. New values a(30) and a(31) independently computed Kai Wang and Axel Kohnert. - Vaclav Kotesovec, Apr 15 2016
In the article by A. Iványi, G. Gombos, L. Lucz, T. Matuszka: "Parallel enumeration of degree sequences of simple graphs II" is in the tables on pages 258 and 261 a wrong value a(31) = 22974847474172100, but in the abstract another wrong value a(31) = 22974847474172374. - Vaclav Kotesovec, Apr 15 2016
The asymptotic formula given below confirms that a(n+1)/a(n) tends to 4. - Tom Johnston, Jan 18 2023

			a(4) = 7 because a 4-vertex graph with no isolated vertices can have degree sequence 1111, 2211, 2222, 3111, 3221, 3322 or 3333.
From _Gus Wiseman_, Dec 31 2020: (Start)
The a(0) = 1 through a(3) = 7 sorted degree sequences (empty column indicated by dot):
  ()  .  (1,1)  (2,1,1)  (1,1,1,1)
                (2,2,2)  (2,2,1,1)
                         (2,2,2,2)
                         (3,1,1,1)
                         (3,2,2,1)
                         (3,3,2,2)
                         (3,3,3,3)
For example, the complete graph K_4 has degrees y = (3,3,3,3), so y is counted under a(4). On the other hand, the only half-loop-graphs (up to isomorphism) with degrees y = (4,2,2,1) are: {(1),(1,2),(1,3),(1,4),(2,3)} and {(1),(2),(3),(1,2),(1,3),(1,4)}; and since neither of these is a graph (due to having half-loops), y is not counted under a(4).
(End)

Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Table of n, a(n) for n = 0..1651 (terms 0 through 79 from Kai Wang)
Paul Balister, Serte Donderwinkel, Carla Groenland, Tom Johnston, and Alex Scott, Counting graphic sequences via integrated random walks, arXiv:2301.07022 [math.CO], 2023.
A. Iványi, L. Lucz, T. Matuszka and S. Pirzada, Parallel enumeration of degree sequences of simple graphs, Acta Univ. Sapiantiae, Inform.4 (2) (2012) 260-288.
A. Iványi, G. Gombos, L. Lucz, and T. Matuszka, Parallel enumeration of degree sequences of simple graphs II, Acta Universitatis Sapientiae, Informatica, Volume 5, Issue 2 (Dec 2013).
A. Iványi, L. Lucz, T. F. Móri and P. Sótér, On Erdős-Gallai and Havel-Hakimi algorithms, Acta Univ. Sapiantiae, Inform. 3 (2) (2011) 230-268.
A. Kohnert, Number of different degree sequences of a graph with no isolated vertices, 2016.
Frank Ruskey, Alley CATs in Search of Good Homes
Kai Wang, Efficient Counting of Degree Sequences, arXiv:1604.04148 [math.CO], 2016. Gives 79 terms. But a(30) and a(31) are different.
Eric Weisstein's World of Mathematics, Degree sequence
Gus Wiseman, Counting and ranking factorizations, factorability, and vertex-degree partitions for groupings into pairs.

Cf. A002494, A004250, A007721 (analog for connected graphs), A271831.
Counting the same partitions by sum gives A000569.
Allowing isolated nodes gives A004251.
The version with half-loops is A029889, with covering case A339843.
Covering simple graphs are ranked by A309356 and A320458.
Graphical partitions are ranked by A320922.
The version with loops is A339844, with covering case A339845.
A006125 counts simple graphs, with covering case A006129.
A027187 counts partitions of even length, ranked by A028260.
A058696 counts partitions of even numbers, ranked by A300061.
A339659 is a triangle counting graphical partitions.
Cf. A007717, A096373, A181819, A320921, A322661, A339559, A339560.

Table[Length[Union[Sort[Table[Count[Join@@#,i],{i,n}]]&/@Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&]]],{n,0,5}] (* Gus Wiseman, Dec 31 2020 *)

a(n) ~ c * 4^n / n^(3/4) for some c > 0. Computational estimates suggest c ≈ 0.074321. - Tom Johnston, Jan 18 2023

Edited by N. J. A. Sloane, Aug 26 2006
More terms from Gordon F. Royle, Aug 21 2006
a(21) and a(22) from Frank Ruskey, Aug 29 2006
a(23) from Frank Ruskey, Aug 31 2006
a(24)-a(29) from Matuszka Tamás, Jan 10 2013
a(30)-a(31) from articles by Kai Wang and Axel Kohnert, Apr 15 2016
a(0) = 1 and a(1) = 0 prepended by Gus Wiseman, Dec 31 2020

A102276 a(n) = (a(n-1) * a(n-5) + a(n-3)^2) / a(n-6) with a(0) = ... = a(5) = 1, a(n) = a(5-n) for all n in Z.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 3, 4, 8, 17, 50, 107, 239, 1103, 3775, 14463, 55283, 256666, 2059753, 9820288, 55075036, 503857819, 4083736906, 44590046729, 335845998321, 3581731774609, 68868876045617, 782035904796497, 11680434156713849, 194342679446776442

Offset: 0

Michael Somos, Jan 02 2005

nonn

Sequence defined by recursion derived from a genus 2 curve.
Similar to the Somos-6 and Somos-7 sequences with many bilinear identities.
If a0 := a(n), a1 := a(n+1), ..., a5 := a(n+5), a6 := a(n+6) and a6 = (a5*a1 + a3^2)/a0 for all n in Z, then c := (a0^2*a1*a4*a5^2 + a0^2*a3*a4^3 + a1^3*a2*a5^2 + a0*a2^2*a3*a4^2 + a1^2*a2*a3^2*a5 + a0*a2*a3^3*a4 + a1*a2^3*a3*a5 + a2^3*a3^3)/(a0*a1*a2*a3*a4*a5) is constant. - Michael Somos, Jun 30 2024

Seiichi Manyama, Table of n, a(n) for n = 0..211
A. J. van der Poorten, Curves of Genus 2, Continued Fractions and Somos Sequences, arXiv:math/0412372 [math.NT], 2004.
A. J. van der Poorten, Curves of Genus 2, Continued Fractions and Somos Sequences, J. Integer Seqs., 8 (2005), #05.3.4.
Index entries for two-way infinite sequences

Cf. A006720, A006722, A256858, A256916, A018896, A271341, A271835, A271831, A271837, A271838, A271839.

I:=[1, 2, 3, 4, 8, 17]; [1, 1, 1, 1, 1] cat [n le 6 select I[n] else (Self(n-1)*Self(n-5) + Self(n-3)^2)/Self(n-6): n in [1..30]]; // G. C. Greubel, Aug 03 2018

Join[{1, 1, 1, 1, 1}, RecurrenceTable[{a[n] == (a[n-1]*a[n-5] + a[n-3]^2)/a[n-6], a[6] == 1, a[7] == 2, a[8] == 3, a[9] == 4, a[10] == 8, a[11] == 17}, a, {n, 6, 60}]] (* G. C. Greubel, Aug 03 2018 *)

{a(n) = my(an); if( n<0, a(5-n), n++; an = vector(n,i,1); for(k=7, n, an[k] = (an[k-1]*an[k-5] + an[k-3]^2) / an[k-6]); an[n])};

a(n) = A256858(2*n - 5) for all n in Z. - Michael Somos, Apr 13 2015
Let b(n) = A256916(n). Then 0 = a(n) * b(n) - a(n-2) * b(n+2) + a(n-3) * b(n+3) for all n in Z. - Michael Somos, Apr 13 2015
0 = a(n) * a(n+6) - a(n+1) * a(n+5) - a(n+3) * a(n+3) for all n in Z. - Michael Somos, Apr 13 2015
0 = a(n) * a(n+9) + a(n+2) * a(n+7) - a(n+3) * a(n+6) - 9 * a(n+4) * a(n+5) for all n in Z. - Michael Somos, Apr 13 2015

A271341 Somos's sequence {a(4,n)} defined in comment in A018896.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 10, 19, 35, 60, 156, 284, 499, 930, 1836, 7116, 21586, 52869, 115344, 356076, 972840, 3350009, 11844969, 37689894, 215136930, 785604755, 2444023816, 7985904285, 36968693334, 230985863335, 1429813280831, 6838592493455, 27144055289355, 191201731942399

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Apr 04 2016

nonn

The sequence of the first differences begins from 9 zeros, 5 1's and 4 consecutive squares, beginning with 2^2.

A generalization see in the comment in A018896.

Seiichi Manyama, Table of n, a(n) for n = 0..318

Cf. A018896, A006720, A102276, A271835, A271831, A271837, A271838, A271839.

[n le 10 select 1 else (Self(n-1)*Self(n-9) + Self(n-5)^2 )/Self(n-10): n in [1..40]]; // G. C. Greubel, Feb 21 2018

k = 4; Set[#, 1] & /@ Map[a[k, #] &, Range[0, 2 k + 1]]; a[k_, n_] /;
n >= 2 k + 2 := (a[k, n - 1] a[k, n - 2 k - 1] + a[k, n - k - 1]^2) / a[k, n - 2 k - 2]; Table[a[k, n], {n, 0, 42}] (* Michael De Vlieger, Apr 04 2016 *)
a[n_ /; 0 <= n <= 10] = 1; a[n_]:= a[n] = (a[n-1]*a[n-9] + a[n-5]^2)/a[n -10]; Table[a[n], {n,0,40}] (* G. C. Greubel, Feb 21 2018 *)

{a(n) = if(n< 10, 1, (a(n-1)*a(n-9) + a(n-5)^2)/a(n-10))};
for(n=0,40, print1(a(n), ", ")) \\ G. C. Greubel, Feb 21 2018

More terms from Michael De Vlieger, Apr 04 2016

A271835 Somos's sequence {a(5,n)} defined in comment in A018896: a(0)=a(1)= ... = a(11) = 1; for n>=12, a(n) = (a(n-1)*a(n-11) + a(n-6)^2)/a(n-12).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 11, 20, 36, 61, 97, 243, 425, 700, 1199, 2183, 4115, 14902, 43515, 102827, 214168, 418685, 1223440, 3053628, 9484929, 31351174, 95335734, 260010845, 1305343146, 4437434637, 12553187856, 35704506092

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Apr 15 2016

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..368
Eric Weisstein's World of Mathematics, Somos Sequence

Cf. A018896, A006125, A006720, A102276, A271341, A271831, A271837, A271838, A271839.

[n le 12 select 1 else (Self(n-1)*Self(n-11) + Self(n-6)^2 )/Self(n-12): n in [1..50]]; // G. C. Greubel, Feb 21 2018

a[k_,n_]:=a[k,n]= If[n>2k+1,(a[k,(n-1)]*a[k,(n-2k-1)]+(a[k,(n-k-1)])^2 )/a[k,(n-2k-2)],1]; Map[a[5,#]&,Range[0,43]] (* Peter J. C. Moses, Apr 15 2016 *)
RecurrenceTable[{Table[a[i]==1,{i,0,11}],a[n]==(a[n-1]a[n-11]+a[n-6]^2)/ a[n-12]},a,{n,50}](* Harvey P. Dale, Sep 24 2021 *)

{a(n) = if(n< 12, 1, (a(n-1)*a(n-11) + a(n-6)^2)/a(n-12))};
for(n=0,50, print1(a(n), ", ")) \\ G. C. Greubel, Feb 21 2018

More terms from Alois P. Heinz, Apr 15 2016

A271837 Somos's sequence {a(7,n)} defined in comment in A018896: a(0)=a(1)= ... = a(15) = 1; for n>=16, a(n) = (a(n-1)*a(n-15)+ a(n-8)^2)/a(n-16).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 13, 22, 38, 63, 99, 148, 212, 505, 842, 1284, 1966, 3153, 5312, 9200, 15968, 51401, 141522, 319386, 631223, 1149722, 2003800, 3442200, 9402302, 20908517, 55671036, 164685883, 466783858

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Apr 15 2016

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..463
Eric Weisstein's World of Mathematics, Somos Sequence

Cf. A018896, A006125, A006720, A102276, A271341, A271831, A271835, A271838, A271839.

[n le 16 select 1 else (Self(n-1)*Self(n-15) + Self(n-8)^2 )/Self(n-16): n in [1..50]]; // G. C. Greubel, Feb 21 2018

a[k_,n_]:=a[k,n] = If[n>2*k+1,(a[k,(n-1)]*a[k,(n-2*k-1)]+(a[k,(n-k-1)])^2 )/a[k,(n-2*k-2)],1]; Map[a[7,#]&,Range[0,50]] (* Peter J. C. Moses, Apr 15 2016 *)

{a(n) = if(n< 16, 1, (a(n-1)*a(n-15) + a(n-8)^2)/a(n-16))};
for(n=0,50, print1(a(n), ", ")) \\ G. C. Greubel, Feb 21 2018

A271838 Somos's sequence {a(8,n)} defined in comment in A018896: a(0)=a(1)= ... = a(17) = 1; for n>=18, a(n) = (a(n-1)*a(n-17)+ a(n-9)^2)/a(n-18).

Original entry on oeis.org

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, 10, 14, 23, 39, 64, 100, 149, 213, 294, 688, 1130, 1683, 2484, 3800, 6100, 10143, 17082, 28584, 87352, 234714, 521145, 1013424, 1809100, 3067659, 5075784, 8375940, 22379904, 47848348

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Apr 15 2016

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..510
Eric Weisstein's World of Mathematics, Somos Sequence

Cf. A018896, A006125, A006720, A102276, A271341, A271835, A271831, A271837, A271839.

[n le 18 select 1 else (Self(n-1)*Self(n-17) + Self(n-9)^2 )/Self(n-18): n in [1..40]]; // G. C. Greubel, Feb 21 2018

a[k_,n_]:=a[k,n] = If[n>2*k+1,(a[k,(n-1)]*a[k,(n-2*k-1)]+(a[k,(n-k-1)])^2 )/a[k,(n-2*k-2)],1]; Map[a[8,#]&,Range[0,50]] (* Peter J. C. Moses, Apr 15 2016 *)
RecurrenceTable[{a[0]==a[1]==a[2]==a[3]==a[4]==a[5]==a[6]==a[7]==a[8]==a[9]== a[10]==a[11]==a[12]==a[13]==a[14]==a[15]==a[16]==a[17]==1,a[n]==(a[n-1]a[n-17]+ a[n-9]^2)/a[n-18]},a,{n,60}] (* Harvey P. Dale, Jun 30 2023 *)

{a(n) = if(n< 18, 1, (a(n-1)*a(n-17) + a(n-9)^2)/a(n-18))};
for(n=0,40, print1(a(n), ", ")) \\ G. C. Greubel, Feb 21 2018

A271839 Somos's sequence {a(9,n)} defined in comment in A018896: a(0)= a(1) = ... = a(19) = 1; for n >= 20, a(n) = (a(n-1)*a(n-19) + a(n-10)^2)/a(n-20).

Original entry on oeis.org

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, 10, 11, 15, 24, 40, 65, 101, 150, 214, 295, 395, 911, 1479, 2164, 3105, 4571, 7033, 11252, 18383, 30095, 48707, 141866, 372815, 816479, 1567804, 2757573, 4585139, 7385515

Offset: 0

Vladimir Shevelev and Peter J. C. Moses, Apr 15 2016

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..555
Eric Weisstein's World of Mathematics, Somos Sequence

Cf. A018896, A006125, A006720, A102276, A271341, A271835, A271831, A271837, A271838.

[n le 20 select 1 else (Self(n-1)*Self(n-19) + Self(n-10)^2 )/Self(n-20): n in [1..50]]; // G. C. Greubel, Feb 21 2018

a[k_,n_]:=a[k,n]=If[n>2k+1,(a[k,(n-1)]*a[k,(n-2k-1)]+(a[k,(n-k-1)])^2)/a[k,(n-2k-2)],1];
Map[a[9,#]&,Range[0,70]] (* Peter J. C. Moses, Apr 15 2016 *)

{a(n) = if(n< 20, 1, (a(n-1)*a(n-19) + a(n-10)^2)/a(n-20))};
for(n=0,50, print1(a(n), ", ")) \\ G. C. Greubel, Feb 21 2018

cp's OEIS Frontend

A095268 Number of distinct degree sequences among all n-vertex graphs with no isolated vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A102276 a(n) = (a(n-1) * a(n-5) + a(n-3)^2) / a(n-6) with a(0) = ... = a(5) = 1, a(n) = a(5-n) for all n in Z.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A271341 Somos's sequence {a(4,n)} defined in comment in A018896.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A271835 Somos's sequence {a(5,n)} defined in comment in A018896: a(0)=a(1)= ... = a(11) = 1; for n>=12, a(n) = (a(n-1)*a(n-11) + a(n-6)^2)/a(n-12).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A271837 Somos's sequence {a(7,n)} defined in comment in A018896: a(0)=a(1)= ... = a(15) = 1; for n>=16, a(n) = (a(n-1)*a(n-15)+ a(n-8)^2)/a(n-16).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

A271838 Somos's sequence {a(8,n)} defined in comment in A018896: a(0)=a(1)= ... = a(17) = 1; for n>=18, a(n) = (a(n-1)*a(n-17)+ a(n-9)^2)/a(n-18).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

A271839 Somos's sequence {a(9,n)} defined in comment in A018896: a(0)= a(1) = ... = a(19) = 1; for n >= 20, a(n) = (a(n-1)*a(n-19) + a(n-10)^2)/a(n-20).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI