A060516 -id:A060516 - cp's OEIS frontend

A060576 a(n) = 1 except for a(1) = 0.

1, 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, 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, 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, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Vladeta Jovovic, Apr 03 2001

Old name: Number of homeomorphically irreducible general graphs on 1 labeled node and with n edges.
A homeomorphically irreducible general graph is a graph with multiple edges and loops and without nodes of degree 2.
This sequence is also produced by Wolfram's Rule 253 of Elementary Cellular Automaton as a triangle read by rows giving successive states initiated with a single ON (black) cell.  See the Wolfram, Weisstein and Index links below. - Robert Price, Jan 31 2016
Decimal expansion of 91/900. - Elmo R. Oliveira, May 05 2024

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

V. Jovovic, Generating functions for homeomorphically irreducible general graphs on n labeled nodes.
V. Jovovic, Recurrences for the numbers of homeomorphically irreducible general graphs on m labeled nodes and n edges.
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton.
S. Wolfram, A New Kind of Science.
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata
Index entries for linear recurrences with constant coefficients, signature (1).

Cf. A003514, A060516, A060533-A060537, A060577-A060581.

1, 0, seq(1, n=2..200); # Wesley Ivan Hurt, Apr 12 2017

a(n)=n!=1 \\ Charles R Greathouse IV, Jun 06 2013

G.f.: (x^2 - x + 1)/(1 - x). a(0)=1, a(1)=0; a(n)=1, n > 1.
E.g.f. for homeomorphically irreducible general graphs with n nodes and k edges is (1 + x*y)^(- 1/2)*exp(- x*y/2 + x^2*y^2/4)*Sum_{k >= 0} 1/(1 - x)^binomial(k + 1, 2)*exp(- x^2*y*k^2/(2*(1 + x*y)) - x^2*y*k/2)*y^k/k!.
E.g.f.: e^x - x. - Paul Barry, May 06 2007
a(n) = 1 - binomial(0,n-1). - Arkadiusz Wesolowski, Feb 10 2012

Definition simplified by N. J. A. Sloane, Sep 26 2023

A060533 Number of homeomorphically irreducible multigraphs (or series-reduced multigraphs or multigraphs without nodes of degree 2) on 3 labeled nodes.

Original entry on oeis.org

1, 3, 0, 3, 9, 12, 19, 27, 36, 46, 57, 69, 82, 96, 111, 127, 144, 162, 181, 201, 222, 244, 267, 291, 316, 342, 369, 397, 426, 456, 487, 519, 552, 586, 621, 657, 694, 732, 771, 811, 852, 894, 937, 981, 1026, 1072, 1119, 1167, 1216, 1266, 1317, 1369, 1422

Offset: 0

Vladeta Jovovic, Apr 01 2001

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

Colin Barker, Table of n, a(n) for n = 0..1000
Vladeta Jovovic, Generating functions for homeomorphically irreducible multigraphs on n labeled nodes.
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A003514, A060516, A060534-A060537.

i=5;s=1;lst={s};Do[s+=n+i;If[s>=0, AppendTo[lst, s]], {n, 0, 6!, 1}];lst (* Vladimir Joseph Stephan Orlovsky, Oct 30 2008 *)

Vec((3*x^7-7*x^6+6*x^5+3*x^4-11*x^3+6*x^2-1)/(x-1)^3 + O(x^60)) \\ Colin Barker, Nov 10 2016

G.f.: (3*x^7 - 7*x^6 + 6*x^5 + 3*x^4 - 11*x^3 + 6*x^2 - 1)/(x - 1)^3.
E.g.f. for homeomorphically irreducible multigraphs with n nodes and k edges is (1 + x*y)^( - 1/2)*exp(x*y/2 + x^2*y^2/4)*Sum_{k >= 0} 1/(1 - x)^binomial(k, 2)*exp( - x^2*y*k^2/(2*(1 + x*y)) - x^2*y*k/2)*y^k/k!.
From Colin Barker, Nov 10 2016: (Start)
a(n) = (1 + n)*(2 + n)/2 - 9 for n>4.
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3) for n>7. (End)
Sum_{n>=3} 1/a(n) = 1/72 + 2*tan(sqrt(73)*Pi/2)*Pi/sqrt(73). - Amiram Eldar, Jan 08 2023

A060537 Number of homeomorphically irreducible multigraphs (or series-reduced multigraphs or multigraphs without nodes of degree 2) on 7 labeled nodes.

Original entry on oeis.org

1, 21, 105, 266, 1386, 6678, 25403, 100506, 384678, 1393903, 4831890, 15955485, 50080478, 149211930, 421819950, 1132236630, 2890927935, 7040892159, 16411041500, 36733789575, 79230165105, 165194651065, 333926559540

Offset: 0

Vladeta Jovovic, Apr 01 2001

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

Vladeta Jovovic, Generating functions for homeomorphically irreducible multigraphs on n labeled nodes

Cf. A003514, A060516, A060533-A060537.

G.f.: (7*x^33 - 42*x^32 + 105*x^31 + 3598*x^30 - 64995*x^29 + 498369*x^28 - 2213029*x^27 + 6169800*x^26 - 10213560*x^25 + 4476990*x^24 + 27664014*x^23 - 97812519*x^22 + 197723150*x^21 - 296237340*x^20 + 352014180*x^19 - 334492361*x^18 + 243984426*x^17 - 117769575*x^16 + 9628325*x^15 + 45726945*x^14 - 50729175*x^13 + 31353175*x^12 - 11717370*x^11 + 1358280*x^10 + 1395765*x^9 - 1068648*x^8 + 395328*x^7 - 77805*x^6 + 882*x^5 + 4095*x^4 - 1141*x^3 + 126*x^2 - 1)/(x - 1)^21. E.g.f. for homeomorphically irreducible multigraphs with n nodes and k edges is (1 + x*y)^( - 1/2)*exp(x*y/2 + x^2*y^2/4)*Sum_{k >= 0} 1/(1 - x)^binomial(k, 2)*exp( - x^2*y*k^2/(2*(1 + x*y)) - x^2*y*k/2)*y^k/k!.

A060581 Number of homeomorphically irreducible general graphs on 6 labeled node and with n edges.

Original entry on oeis.org

1, 15, 81, 441, 2151, 9957, 43122, 174162, 666267, 2403987, 8183601, 26281065, 79660856, 228180456, 618992466, 1595081266, 3918506466, 9211519476, 20797923546, 45258309066, 95225448306, 194283668576, 385361919996

Offset: 0

Vladeta Jovovic, Apr 03 2001

A homeomorphically irreducible general graph is a graph with multiple edges and loops and without nodes of degree 2.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

Cf. A003514, A060516, A060533-A060537, A060576-A060581.

G.f.: (6*x^30 - 30*x^29 - 90*x^28 + 898*x^27 - 5703*x^26 + 67854*x^25 - 552925*x^24 + 2795730*x^23 - 9663357*x^22 + 24476292*x^21 - 47540991*x^20 + 73129860*x^19 - 91373250*x^18 + 94675608*x^17 - 82549758*x^16 + 60794764*x^15 - 37293240*x^14 + 18277860*x^13 - 6426742*x^12 + 945252*x^11 + 680499*x^10 - 726250*x^9 + 423825*x^8 - 187536*x^7 + 66981*x^6 - 19092*x^5 + 4065*x^4 - 560*x^3 + 24*x^2 + 6*x - 1)/(x - 1)^21. E.g.f. for homeomorphically irreducible general graphs with n nodes and k edges is (1 + x*y)^( - 1/2)*exp( - x*y/2 + x^2*y^2/4)*Sum_{k >= 0} 1/(1 - x)^binomial(k + 1, 2)*exp( - x^2*y*k^2/(2*(1 + x*y)) - x^2*y*k/2)*y^k/k!.

A060534 Number of homeomorphically irreducible multigraphs (or series-reduced multigraphs or multigraphs without nodes of degree 2) on 4 labeled nodes.

Original entry on oeis.org

1, 6, 3, 10, 48, 84, 182, 372, 699, 1222, 2007, 3132, 4688, 6780, 9528, 13068, 17553, 23154, 30061, 38484, 48654, 60824, 75270, 92292, 112215, 135390, 162195, 193036, 228348, 268596, 314276, 365916, 424077, 489354, 562377, 643812, 734362, 834768, 945810

Offset: 0

Vladeta Jovovic, Apr 01 2001

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

Colin Barker, Table of n, a(n) for n = 0..1000
Vladeta Jovovic, Generating functions for homeomorphically irreducible multigraphs on n labeled nodes
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Cf. A003514, A060516, A060533, A060535-A060537.

Vec(-(4*x^12-12*x^11+6*x^10+50*x^9-180*x^8+282*x^7-208*x^6+30*x^5+72*x^4-62*x^3+18*x^2-1)/((x-1)^6) + O(x^40)) \\ Colin Barker, Nov 10 2016

G.f.: - (4*x^12 - 12*x^11 + 6*x^10 + 50*x^9 - 180*x^8 + 282*x^7 - 208*x^6 + 30*x^5 + 72*x^4 - 62*x^3 + 18*x^2 - 1)/((x - 1)^6).
E.g.f. for homeomorphically irreducible multigraphs with n nodes and k edges is (1 + x*y)^( - 1/2)*exp(x*y/2 + x^2*y^2/4)*Sum_{k >= 0} 1/(1 - x)^binomial(k, 2)*exp( - x^2*y*k^2/(2*(1 + x*y)) - x^2*y*k/2)*y^k/k!.
From Colin Barker, Nov 10 2016: (Start)
a(n) = 60 + 48*(1+n) - 12*(1+n)*(2+n) + (1+n)*(2+n)*(3+n)*(4+n)*(5+n)/120 for n>6.
a(n) = 6*a(n-1)- 15*a(n-2) + 20*a(n-3) - 15*a(n-4) + 6*a(n-5) - a(n-6) for n>12.
(End)

A060577 Number of homeomorphically irreducible general graphs on 2 labeled nodes and with n edges.

Original entry on oeis.org

1, 1, 4, 6, 11, 17, 24, 32, 41, 51, 62, 74, 87, 101, 116, 132, 149, 167, 186, 206, 227, 249, 272, 296, 321, 347, 374, 402, 431, 461, 492, 524, 557, 591, 626, 662, 699, 737, 776, 816, 857, 899, 942, 986, 1031, 1077, 1124, 1172, 1221, 1271, 1322, 1374, 1427

Offset: 0

Vladeta Jovovic, Apr 04 2001

A homeomorphically irreducible general graph is a graph with multiple edges and loops and without nodes of degree 2.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

V. Jovovic, Generating functions for homeomorphically irreducible general graphs on n labeled nodes
V. Jovovic, Recurrences for the numbers of homeomorphically irreducible general graphs on m labeled nodes and n edges
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Cf. A003514, A046691, A060516, A060533-A060537, A060576-A060581.

gf := (2*x^5 - 4*x^4 + 4*x^3 - 4*x^2 + 2*x - 1)/(x - 1)^3: s := series(gf, x, 100): for i from 0 to 100 do printf(`%d,`,coeff(s,x,i)) od:

Join[{1, 1, 4}, Table[n (n + 3)/2 - 3, {n, 3, 60}]] (* Bruno Berselli, Aug 20 2015 *)

G.f.: (2*x^5 - 4*x^4 + 4*x^3 - 4*x^2 + 2*x - 1)/(x - 1)^3.
E.g.f. for homeomorphically irreducible general graphs with n nodes and k edges is (1 + x*y)^( - 1/2)*exp( - x*y/2 + x^2*y^2/4)*Sum_{k >= 0} 1/(1 - x)^binomial(k + 1, 2)*exp( - x^2*y*k^2/(2*(1 + x*y)) - x^2*y*k/2)*y^k/k!.
From Marco Ripà, Aug 20 2015: (Start)
a(n) = ceiling( (1/2)*(3*n^2 - 10*n + 9)/(n - 2) ) + floor( (3/2)*(n-1)^2 ) - n^2 + 3*n - 3 with n > 2, a(0) = a(1) = 1, a(2) = 4.
a(n) = n*(n + 3)/2 - 3 for n > 2.
a(n) = A046691(n-1) for n > 2. (End)

More terms from James Sellers, Apr 04 2001

A060517 Triangle T(n,k) of series-reduced (or homeomorphically irreducible) graphs with loops on n labeled nodes and with k edges, k=0..binomial(n+1,2).

Original entry on oeis.org

1, 1, 0, 1, 1, 2, 1, 1, 3, 6, 6, 6, 3, 1, 1, 6, 15, 34, 58, 60, 60, 50, 33, 10, 1, 1, 10, 35, 120, 265, 475, 820, 1200, 1615, 1860, 1693, 1060, 425, 105, 15, 1, 1, 15, 75, 330, 990, 2691, 6326, 13170, 26205, 48055, 79206, 112863, 133535, 124680, 88890, 47874

Offset: 0

Vladeta Jovovic, Mar 24 2001

			[1], [1, 0], [1, 1, 2, 1], [1, 3, 6, 6, 6, 3, 1], [1, 6, 15, 34, 58, 60, 60, 50, 33, 10, 1], [1, 10, 35, 120, 265, 475, 820, 1200, 1615, 1860, 1693, 1060, 425, 105, 15, 1], [1, 15, 75, 330, 990, 2691, 6326, 13170, 26205, 48055, 79206, 112863, 133535, 124680, 88890, 47874, 19443, 5925, 1330, 210, 21, 1], ...

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.

Row sums: A060516, A003514, A060514.

E.g.f.: (1 + x * y)^( - 1/2) * exp( - x * y/2 - x^2 * y^2/4) * Sum_{k=0..inf}(1 + x)^binomial(k + 1, 2) * exp( - x^2 * y * k^2/(2 * (1 + x * y)) + x^2 * y * k/2) * x^k/k!

A060535 Number of homeomorphically irreducible multigraphs (or series-reduced multigraphs or multigraphs without nodes of degree 2) on 5 labeled nodes.

Original entry on oeis.org

1, 10, 15, 30, 165, 430, 1170, 3180, 7935, 18610, 40948, 84570, 164740, 304690, 538630, 915574, 1504135, 2398460, 3725495, 5653790, 8404075, 12261860, 17592335, 24857870, 34638440, 47655326, 64798470, 87157890, 116059590

Offset: 0

Vladeta Jovovic, Apr 01 2001

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

Vladeta Jovovic, Generating functions for homeomorphically irreducible multigraphs on n labeled nodes

Cf. A003514, A060516, A060533-A060537.

G.f.: (5*x^18 - 20*x^17 + 30*x^16 + 58*x^15 - 745*x^14 + 2790*x^13 - 5270*x^12 + 5010*x^11 - 711*x^10 - 4380*x^9 + 6270*x^8 - 4470*x^7 + 1535*x^6 + 178*x^5 - 450*x^4 + 210*x^3 - 40*x^2 + 1)/(x - 1)^10. E.g.f. for homeomorphically irreducible multigraphs with n nodes and k edges is (1 + x*y)^( - 1/2)*exp(x*y/2 + x^2*y^2/4)*Sum_{k >= 0} 1/(1 - x)^binomial(k, 2)*exp( - x^2*y*k^2/(2*(1 + x*y)) - x^2*y*k/2)*y^k/k!.

A060536 Number of homeomorphically irreducible multigraphs (or series-reduced multigraphs or multigraphs without nodes of degree 2) on 6 labeled nodes.

Original entry on oeis.org

1, 15, 45, 90, 495, 1866, 5990, 19920, 62655, 186525, 526470, 1403265, 3530000, 8388495, 18884475, 40442635, 82775970, 162663240, 308201500, 565176105, 1006419120, 1745321275, 2955037455, 4895398755, 7950135835, 12677752431

Offset: 0

Vladeta Jovovic, Apr 01 2001

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

Vladeta Jovovic, Generating functions for homeomorphically irreducible multigraphs on n labeled nodes

Cf. A003514, A060516, A060533-A060537.

G.f.: - (6*x^25 - 30*x^24 + 60*x^23 + 615*x^22 - 9280*x^21 + 54909*x^20 - 186150*x^19 + 404285*x^18 - 581340*x^17 + 522915*x^16 - 172878*x^15 - 289605*x^14 + 590880*x^13 - 581955*x^12 + 337755*x^11 - 67650*x^10 - 74150*x^9 + 84315*x^8 - 42870*x^7 + 10410*x^6 + 888*x^5 - 1590*x^4 + 535*x^3 - 75*x^2 + 1)/(x - 1)^15. E.g.f. for homeomorphically irreducible multigraphs with n nodes and k edges is (1 + x*y)^( - 1/2)*exp(x*y/2 + x^2*y^2/4)*Sum_{k >= 0} 1/(1 - x)^binomial(k, 2)*exp( - x^2*y*k^2/(2*(1 + x*y)) - x^2*y*k/2)*y^k/k!.

A060578 Number of homeomorphically irreducible general graphs on 3 labeled node and with n edges.

Original entry on oeis.org

1, 3, 9, 21, 60, 135, 282, 537, 945, 1561, 2451, 3693, 5378, 7611, 10512, 14217, 18879, 24669, 31777, 40413, 50808, 63215, 77910, 95193, 115389, 138849, 165951, 197101, 232734, 273315, 319340, 371337, 429867, 495525, 568941, 650781, 741748

Offset: 0

Vladeta Jovovic, Apr 03 2001

A homeomorphically irreducible general graph is a graph with multiple edges and loops and without nodes of degree 2.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

Cf. A003514, A060516, A060533-A060537, A060576-A060581.

CoefficientList[Series[-(8x^9-36x^8+66x^7-70x^6+51x^5-24x^4+8x^3-6x^2+3x-1)/(x-1)^6,{x,0,40}],x] (* Harvey P. Dale, Jul 22 2018 *)

G.f.: - (8*x^9 - 36*x^8 + 66*x^7 - 70*x^6 + 51*x^5 - 24*x^4 + 8*x^3 - 6*x^2 + 3*x - 1)/(x - 1)^6. E.g.f. for homeomorphically irreducible general graphs with n nodes and k edges is (1 + x*y)^( - 1/2)*exp( - x*y/2 + x^2*y^2/4)*Sum_{k >= 0} 1/(1 - x)^binomial(k + 1, 2)*exp( - x^2*y*k^2/(2*(1 + x*y)) - x^2*y*k/2)*y^k/k!.

cp's OEIS Frontend

A060576 a(n) = 1 except for a(1) = 0.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

A060533 Number of homeomorphically irreducible multigraphs (or series-reduced multigraphs or multigraphs without nodes of degree 2) on 3 labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A060537 Number of homeomorphically irreducible multigraphs (or series-reduced multigraphs or multigraphs without nodes of degree 2) on 7 labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A060581 Number of homeomorphically irreducible general graphs on 6 labeled node and with n edges.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A060534 Number of homeomorphically irreducible multigraphs (or series-reduced multigraphs or multigraphs without nodes of degree 2) on 4 labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

A060577 Number of homeomorphically irreducible general graphs on 2 labeled nodes and with n edges.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A060517 Triangle T(n,k) of series-reduced (or homeomorphically irreducible) graphs with loops on n labeled nodes and with k edges, k=0..binomial(n+1,2).

Views

Author

Keywords

Examples

References

Crossrefs

Formula

A060535 Number of homeomorphically irreducible multigraphs (or series-reduced multigraphs or multigraphs without nodes of degree 2) on 5 labeled nodes.

Views

Author

Keywords

References

Links

Crossrefs