A028242 -id:A028242 - cp's OEIS frontend

A141580 Number of unlabeled non-mating graphs with n vertices.

0, 1, 2, 6, 18, 78, 456, 4299, 68754, 1990286, 106088988, 10454883132, 1904236651216, 641859005526860, 401547534010157680, 467956331904669136874, 1019785644052109276678788, 4171197546082606538129623140

Offset: 1

Tanya Khovanova, Aug 19 2008

nonn

a(n) is the difference between A000088 (number of graphs on n unlabeled nodes) and A004110 (number of n-node graphs without endpoints)
A non-mating graph has two vertices with an identical set of neighbors.
The adjacency matrix of a non-mating graph is degenerate.
Also the number of unlabeled graphs with n vertices and at least one endpoint. - Gus Wiseman, Sep 11 2019

			A cycle with 4 vertices is a non-mating graph. In the standard ordering of vertices, vertices 1 and 3 are both connected to vertices 2 an 4, thus having an identical sets of neighbors.
From _Gus Wiseman_, Sep 11 2019: (Start)
Non-isomorphic representatives of the a(2) = 1 through a(5) non-mating graph edge-sets:
  {12}  {12}     {12}           {12}
        {13,23}  {12,34}        {12,34}
                 {13,23}        {13,23}
                 {13,24,34}     {12,35,45}
                 {14,24,34}     {13,24,34}
                 {14,23,24,34}  {14,24,34}
                                {12,34,35,45}
                                {13,24,35,45}
                                {14,23,24,34}
                                {14,25,35,45}
                                {15,25,35,45}
                                {12,25,34,35,45}
                                {14,25,34,35,45}
                                {15,23,24,35,45}
                                {15,25,34,35,45}
                                {13,24,25,34,35,45}
                                {15,24,25,34,35,45}
                                {15,23,24,25,34,35,45}
(End)

Andrew Howroyd, Table of n, a(n) for n = 1..50
Ronald C. Read, The enumeration of mating-type graphs, Report CORR 89-38, Dept. Combinatorics and Optimization, Univ. Waterloo, 1989.
Gus Wiseman, The a(1) = 1 through a(5) = 18 non-mating graphs (isolated vertices not shown).
Gus Wiseman, The a(1) = 1 through a(5) = 18 graphs with at least one endpoint (isolated vertices not shown).

The labeled version is A327379.

Cf. A000088, A004110, A028242, A059167, A245797, A327335, A327371.

k = {}; For[i = 1, i < 8, i++, lg = ListGraphs[i] ; len = Length[lg]; k = Append[k, Length[Select[Range[len], Length[Union[ToAdjacencyMatrix[lg[[ # ]]]]] != i &]]]]; k

a(n) = A000088(n) - A004110(n).

Extended by R. J. Mathar, Sep 12 2008

A168361 Period 2: repeat 2, -1.

Original entry on oeis.org

2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1, 2, -1

Offset: 1

Klaus Brockhaus, Nov 23 2009

Interleaving of A007395 and -A000012.
Binomial transform of 2 followed by a signed version of A007283; also binomial transform of a signed version of A042950.
Second binomial transform of a signed version of A007051 without initial term 1.
Inverse binomial transform of 2 followed by A000079.
A028242 without first two terms gives partial sums.

Index entries for linear recurrences with constant coefficients, signature (0,1).

Cf. A168330 (repeat 3, -2), A007395 (all 2's sequence), A000012 (all 1's sequence), (A007283 3*2^n), A042950, A007051 ((3^n+1)/2), A000079 (powers of 2), A028242 (follow n+1 by n).

&cat[ [2, -1]: n in [1..42] ];
[ n eq 1 select 2 else -Self(n-1)+1: n in [1..84] ];

&cat[[2,-1]^^40]; // Vincenzo Librandi, Jul 20 2016

PadRight[{},120,{2,-1}] (* Harvey P. Dale, Jan 04 2015 *)
Table[(1 - 3 (-1)^n)/2, {n, 120}] (* or *)
Rest@ CoefficientList[Series[x (2 - x)/((1 - x) (1 + x)), {x, 0, 120}], x] (* Michael De Vlieger, Jul 19 2016 *)

a(n)=2-n%2*3 \\ Charles R Greathouse IV, Jul 13 2016

a(n) = (1 - 3*(-1)^n)/2.
a(n) = -a(n-1) + 1 for n > 1; a(1) = 2.
a(n) = a(n-2) for n > 2; a(1) = 2, a(2) = -1.
a(n+1) - a(n) = 3*(-1)^n.
G.f.: x*(2 - x)/((1-x)*(1+x)).
E.g.f.: (1/2)*(-1 + exp(x))*(3 + exp(x))*exp(-x). - G. C. Greubel, Jul 19 2016

G.f. adapted to the offset by Bruno Berselli, Apr 01 2011

A327370 Number of labeled simple graphs with n vertices and exactly n - 1 endpoints (vertices of degree 1).

Original entry on oeis.org

0, 1, 0, 6, 4, 50, 66, 532, 1016, 6876, 16750, 104456, 303612, 1821976, 6067166, 35857200, 133160176, 785514512, 3192117966, 18948962656, 83099447300, 498931946016, 2336474411062, 14234346694976, 70598633745576, 437304764440000, 2282139344678726, 14390600621415552

Offset: 0

Gus Wiseman, Sep 04 2019

nonn

Graphs consist of zero or more paths on two nodes each and either a single isolated node or a star with two or more peripheral nodes. - Andrew Howroyd, Sep 05 2019

			The a(4) = 4 edge-sets:
  {12,13,14}
  {12,23,24}
  {13,23,34}
  {14,24,34}

Andrew Howroyd, Table of n, a(n) for n = 0..500

Column k = n - 1 of A327369.
The unlabeled version is A028242.
Cf. A006125, A059167, A100743, A245797, A294217, A327227, A327377.

f:= gfun:-rectoproc({(n-1)*(n-2)*a(n)-n*(n-3)*(n-2)*a(n-1)-n*(n-1)^2*a(n-2)+(2*n-7)*n*(n-1)*(n-2)*a(n-3)-n*(n-1)*(n-2)*(n-3)*(n-4)*a(n-5)=0, a(0)=0, a(1)=1, a(2)=0, a(3)=6, a(4)=4},a(n),remember):
map(f, [$0..40]); # Robert Israel, Sep 06 2019

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Count[Length/@Split[Sort[Join@@#]],1]==n-1&]],{n,0,5}]
With[{nn=30},CoefficientList[Series[x Exp[x^2/2](Exp[x]-x),{x,0,nn}],x] Range[ 0,nn]!] (* Harvey P. Dale, Apr 28 2022 *)

seq(n)={Vec(serlaplace(x*exp(x^2/2 + O(x^n))*(exp(x + O(x^n))-x)), -(n+1))} \\ Andrew Howroyd, Sep 05 2019

E.g.f.: x*exp(x^2/2)*(exp(x) - x). - Andrew Howroyd, Sep 05 2019

(n-1)*(n-2)*a(n) - n*(n-3)*(n-2)*a(n-1) - n*(n-1)^2*a(n-2) + (2*n-7)*n*(n-1)*(n-2)*a(n-3) - n*(n-1)*(n-2)*(n-3)*(n-4)*a(n-5) = 0. - Robert Israel, Sep 06 2019

Terms a(8) and beyond from Andrew Howroyd, Sep 05 2019

A008624 Expansion of g.f. (1 + x^3)/((1 - x^2)(1 - x^4)) = (1 - x + x^2)/((1 + x)(1 - x)^2*(1 + x^2)).

Original entry on oeis.org

1, 0, 1, 1, 2, 1, 2, 2, 3, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 6, 5, 6, 6, 7, 6, 7, 7, 8, 7, 8, 8, 9, 8, 9, 9, 10, 9, 10, 10, 11, 10, 11, 11, 12, 11, 12, 12, 13, 12, 13, 13, 14, 13, 14, 14, 15, 14, 15, 15, 16, 15, 16, 16, 17

Offset: 0

N. J. A. Sloane

Molien series of 2-dimensional representation of group of order 16 over GF(3).

D. J. Benson, Polynomial Invariants of Finite Groups, Cambridge, 1993, p. 107.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for Molien series
Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Essentially the same as A059169.

Cf. A028242, A110654, A110659.

f := x -> (1+x^3)/((1-x^2)*(1-x^4)): seq(coeff(series(f(x), x, n+1), x, n), n=0..64);
a := n -> floor(n/4) + ((n mod 2 + 1 - floor((n mod 4)/3)) mod 2): seq(a(n), n=0..64); # Johannes W. Meijer, Oct 08 2013

CoefficientList[Series[(1 + x^3) / (1 - x^2) / (1 - x^4), {x, 0, 70}], x] (* Vincenzo Librandi, Aug 15 2013 *)
LinearRecurrence[{1,0,0,1,-1},{1,0,1,1,2},70] (* Harvey P. Dale, Sep 27 2024 *)

a(n) = (3 + 3*(-1)^n + (1-I)*(-I)^n + (1+I)*I^n + 2*n) / 8 \\ Colin Barker, Oct 15 2015

my(x='x+O('x^100)); Vec((1+x^3)/((1-x^2)*(1-x^4))) \\ Altug Alkan, Dec 24 2015

From Reinhard Zumkeller, Aug 05 2005: (Start)
a(n) = floor(n/4) + ((n mod 2 + 1 - floor((n mod 4)/3)) mod 2).
a(n) = A110654(A028242(n)). (End)
a(n) = (3 + 3*(-1)^n + (1-i)*(-i)^n + (1+i)*i^n + 2*n) / 8 where i = sqrt(-1). - Colin Barker, Oct 15 2015
a(n) = (2*n+3+2*cos(n*Pi/2)+3*cos(n*Pi)-2*sin(n*Pi/2))/8. - Wesley Ivan Hurt, Oct 01 2017
E.g.f.: (cos(x) + (3 + x)*cosh(x) - sin(x) + x*sinh(x))/4. - Stefano Spezia, Jan 03 2023

Replaced x^2 three times with x in the generating function (un-aerated). - R. J. Mathar, Oct 23 2008

A076736 Let u(1) = u(2) = u(3) = 2, u(n) = (1 + u(n-1)*u(n-2))/u(n-3); then a(n) is the denominator of u(n).

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 2, 8, 4, 16, 8, 32, 16, 64, 32, 128, 64, 256, 128, 512, 256, 1024, 512, 2048, 1024, 4096, 2048, 8192, 4096, 16384, 8192, 32768, 16384, 65536, 32768, 131072, 65536, 262144, 131072, 524288, 262144, 1048576, 524288, 2097152

Offset: 1

Benoit Cloitre, Nov 24 2002

The sequence 1,4,2,8,4,... has g.f. (1+4*x)/(1-2*x^2) and a(n) = 2^(n/2)*(1+2*sqrt(2) + (1-2*sqrt(2))*(-1)^n)/2. - Paul Barry, Apr 26 2004

The sequence 2,1,4,2,8,... has a(n) = 2^(n/2)*(1+2*sqrt(2)-(1-2*sqrt(2))*(-1)^n)/(2*sqrt(2)) and is essentially the pair-reversal of A016116. - Paul Barry, Apr 26 2004

Harvey P. Dale, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (0,2).

Cf. A005246, A076737.

LinearRecurrence[{0,2},{1,1,1,2,1},50] (* Harvey P. Dale, Aug 25 2015 *)

For n > 4, a(n) = 2^A028242(n-4).
From Colin Barker, Oct 14 2014: (Start)
For n > 5, a(n) = 2*a(n-2).
G.f.: x*(x-1)*(x^3+x^2+2*x+1) / (2*x^2-1). (End)

More terms from Paul Barry, Apr 26 2004

A051263 Expansion of 1/((1-x)(1-x^3)^2(1-x^5)).

Original entry on oeis.org

1, 1, 1, 3, 3, 4, 7, 7, 9, 13, 14, 17, 22, 24, 28, 35, 38, 43, 52, 56, 63, 74, 79, 88, 101, 108, 119, 134, 143, 156, 174, 185, 200, 221, 234, 252, 276, 291, 312, 339, 357, 381, 411, 432, 459, 493, 517, 547, 585, 612, 646, 688, 718, 756, 802, 836, 878, 928, 966

Offset: 0

N. J. A. Sloane

A two-way infinite sequences which is palindromic (up to sign). - Michael Somos, Mar 21 2003

Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (1,0,2,-2,1,-2,1,-2,2,0,1,-1).

Cf. A028242, A028288, A029153.

{a(n) = if( n<-11, -a(-12 - n), if( n<0, 0, polcoeff( 1 / ((1 - x) * (1 - x^3)^2 * (1 - x^5)) + x * O(x^n),n)))} /* Michael Somos, Mar 21 2003 */

G.f.: 1 / ((1 - x) * (1 - x^3)^2 * (1 - x^5)).
a(-12 - n) = -a(n). a(n) = a(n-1) + 2*a(n-3) - 2*a(n-4) + a(n-5) - 2*a(n-6) + a(n-7) - 2*a(n-8) + 2*a(n-9) + a(n-11) - a(n-12). - Michael Somos, Mar 21 2003
A029153(n) = a(floor(n/2) - mod(n,2)) = a(A028242(n - 2)). - Michael Somos, Mar 21 2003
a(n) = 1 + [(n mod 15)=6] + floor((n^3+18*n^2+(87+30*[(n mod 3)=0])*n)/270) where [] is Iverson bracket. - Hoang Xuan Thanh, Jun 06 2025

A063942 Follow k with k-1 and k-2.

Original entry on oeis.org

1, 0, -1, 2, 1, 0, 3, 2, 1, 4, 3, 2, 5, 4, 3, 6, 5, 4, 7, 6, 5, 8, 7, 6, 9, 8, 7, 10, 9, 8, 11, 10, 9, 12, 11, 10, 13, 12, 11, 14, 13, 12, 15, 14, 13, 16, 15, 14, 17, 16, 15, 18, 17, 16, 19, 18, 17, 20, 19, 18, 21, 20, 19, 22, 21, 20, 23, 22, 21, 24, 23, 22, 25, 24, 23, 26, 25, 24, 27, 26, 25, 28, 27, 26, 29, 28, 27, 30, 29, 28, 31, 30, 29, 32

Offset: 0

Jason Earls, Sep 01 2001

Harry J. Smith, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1).

Cf. A028242.

LinearRecurrence[{1, 0, 1, -1}, {1, 0, -1, 2}, 100] (* Amiram Eldar, Oct 04 2022 *)

PARI
```
a(n) = (n\3)-(n%3)+1
```

G.f.: ( 1-x^2+2*x^3-x ) / ( (1+x+x^2)*(x-1)^2 ). - R. J. Mathar, Jul 14 2015
a(3n) = n+1. a(3n+1) = n. a(3n+2) = n-1. - R. J. Mathar, Jan 10 2017
a(n) = (3*n-3-12*cos(2*(n-5)*Pi/3)+4*sqrt(3)*sin(2*(n-5)*Pi/3))/9. - Wesley Ivan Hurt, Sep 29 2017
E.g.f.: exp(x)*(x - 1)/3 + 4*exp(-x/2)*(3*cos(sqrt(3)*x/2) + sqrt(3)*sin(sqrt(3)*x/2))/9. - Stefano Spezia, Oct 02 2022
Sum_{n>=6} (-1)^n/a(n) = 3*(log(2)-1/2). - Amiram Eldar, Oct 04 2022

A209578 Triangle of coefficients of polynomials v(n,x) jointly generated with A209577; see the Formula section.

Original entry on oeis.org

1, 3, 1, 5, 3, 1, 9, 8, 4, 1, 15, 19, 13, 5, 1, 25, 41, 36, 19, 6, 1, 41, 84, 90, 60, 26, 7, 1, 67, 165, 210, 169, 92, 34, 8, 1, 109, 315, 465, 439, 287, 133, 43, 9, 1, 177, 588, 990, 1073, 818, 454, 184, 53, 10, 1, 287, 1079, 2043, 2502, 2178, 1405, 681, 246

Offset: 1

Clark Kimberling, Mar 11 2012

Alternating row sums: 1,0,2,1,3,2,4,3,5,4,... (A028242).

For a discussion and guide to related arrays, see A208510.

			First five rows:
1
1...1
3...2....1
5...6....3....1
9...13...10...4...1
First three polynomials v(n,x): 1, 1 + x , 3 + 2x + x^2.

Cf. A209577, A208510.

u[1, x_] := 1; v[1, x_] := 1; z = 16;
u[n_, x_] := x*u[n - 1, x] + v[n - 1, x];
v[n_, x_] := (x + 1)*u[n - 1, x] + v[n - 1, x] + 1;
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Flatten[%]   (* A209577 *)
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
Flatten[%]   (* A209578 *)

u(n,x)=x*u(n-1,x)+v(n-1,x),
v(n,x)=(x+1)*u(n-1,x)+v(n-1,x)+1,
where u(1,x)=1, v(1,x)=1.

A210871 Triangle of coefficients of polynomials v(n,x) jointly generated with A210870; see the Formula section.

Original entry on oeis.org

1, 1, 2, 1, 1, 3, 1, 3, 2, 5, 1, 2, 7, 3, 8, 1, 4, 5, 15, 5, 13, 1, 3, 12, 10, 30, 8, 21, 1, 5, 9, 31, 20, 58, 13, 34, 1, 4, 18, 22, 73, 38, 109, 21, 55, 1, 6, 14, 54, 51, 162, 71, 201, 34, 89, 1, 5, 25, 40, 145, 111, 344, 130, 365, 55, 144, 1, 7, 20, 85, 105, 361, 233

Offset: 1

Clark Kimberling, Mar 29 2012

Row n, for n>2, starts with 1 and A028242(n) and ends with F(n-1) and F(n+1), where F=A000045 (Fibonacci numbers).
Row sums:  A001045
Alternating row sums: A077925
For a discussion and guide to related arrays, see A208510.

			First six rows:
1
1...2
1...1...3
1...3...2....5
1...2...7....3....8
1...4...5....15...5...13
First three polynomials v(n,x): 1, 1 + 2x, 1 + x + 3x^2

Cf. A210870, A208510.

u[1, x_] := 1; v[1, x_] := 1; z = 14;
u[n_, x_] := u[n - 1, x] + x*v[n - 1, x];
v[n_, x_] := (x + 1)*u[n - 1, x] + (x - 1)*v[n - 1, x] + 1;
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Flatten[%]    (* A210870 *)
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
Flatten[%]    (* A210871 *)
Table[u[n, x] /. x -> 1, {n, 1, z}]  (* A000975 *)
Table[v[n, x] /. x -> 1, {n, 1, z}]  (* A001045 *)
Table[u[n, x] /. x -> -1, {n, 1, z}] (* A113954 *)
Table[v[n, x] /. x -> -1, {n, 1, z}] (* A077925 *)

u(n,x)=u(n-1,x)+x*v(n-1,x),
v(n,x)=(x+1)*u(n-1,x)+(x-1)*v(n-1,x)+1,
where u(1,x)=1, v(1,x)=1.

A373272 Triangle read by rows: T(n,k) = sum of all distinct multiplicities in the integer partitions of n with k parts.

Original entry on oeis.org

1, 1, 2, 1, 1, 3, 1, 3, 3, 4, 1, 2, 6, 4, 5, 1, 4, 7, 6, 5, 6, 1, 3, 10, 11, 10, 6, 7, 1, 5, 11, 16, 14, 12, 7, 8, 1, 4, 15, 20, 22, 14, 14, 8, 9, 1, 6, 16, 26, 28, 29, 20, 16, 9, 10, 1, 5, 20, 34, 41, 40, 34, 23, 18, 10, 11, 1, 7, 22, 42, 50, 54, 44, 35, 26, 20, 11, 12, 1, 6, 26, 52, 69, 75, 68, 54, 44, 29, 22, 12, 13

Offset: 1

Olivier Gérard, May 29 2024

			Array begins:
  1;
  1, 2;
  1, 1,  3;
  1, 3,  3,  4;
  1, 2,  6,  4,  5;
  1, 4,  7,  6,  5,  6;
  1, 3, 10, 11, 10,  6,  7;
  1, 5, 11, 16, 14, 12,  7,  8;
  1, 4, 15, 20, 22, 14, 14,  8, 9;
  1, 6, 16, 26, 28, 29, 20, 16, 9, 10;
  ...
T(6,3) = 7 because the partitions of 6 into 3 parts are 4+1+1, 3+2+1, 2+2+2,
  the multiplicities are (1,2), (1,1,1), (3),
  the distinct multiplicities are respectively (1,2), (1), (3),
  contributing 3+1+3 = 7.

Alois P. Heinz, Rows n = 1..200, flattened (first 40 rows from Olivier Gérard)

Columns k=1-2 give: A057427, A028242.
Main diagonal gives A000027.
Row sums are A373273.
T(2n,n) gives A373104.

Flatten[Table[
  Plus @@@
   Table[Map[Plus @@ Union[Length /@ Split[#]] &,
     IntegerPartitions[n, {k}]], {k, 1, n}], {n, 1, 20}]]

cp's OEIS Frontend

A141580 Number of unlabeled non-mating graphs with n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A168361 Period 2: repeat 2, -1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Magma

Mathematica

PARI

Formula

Extensions

A327370 Number of labeled simple graphs with n vertices and exactly n - 1 endpoints (vertices of degree 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A008624 Expansion of g.f. (1 + x^3)/((1 - x^2)*(1 - x^4)) = (1 - x + x^2)/((1 + x)*(1 - x)^2*(1 + x^2)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A076736 Let u(1) = u(2) = u(3) = 2, u(n) = (1 + u(n-1)*u(n-2))/u(n-3); then a(n) is the denominator of u(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A051263 Expansion of 1/((1-x)*(1-x^3)^2*(1-x^5)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A063942 Follow k with k-1 and k-2.

Views

Author

A008624 Expansion of g.f. (1 + x^3)/((1 - x^2)(1 - x^4)) = (1 - x + x^2)/((1 + x)(1 - x)^2*(1 + x^2)).

A051263 Expansion of 1/((1-x)(1-x^3)^2(1-x^5)).