A327371 -id:A327371 - cp's OEIS frontend

A028242 Follow n+1 by n. Also (essentially) Molien series of 2-dimensional quaternion group Q_8.

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

Offset: 0

N. J. A. Sloane

A two-way infinite sequences which is palindromic (up to sign). - Michael Somos, Mar 21 2003
Number of permutations of [n+1] avoiding the patterns 123, 132 and 231 and having exactly one fixed point. Example: a(0) because we have 1; a(2)=2 because we have 213 and 321; a(3)=1 because we have 3214. - Emeric Deutsch, Nov 17 2005
The ring of invariants for the standard action of Quaternions on C^2 is generated by x^4 + y^4, x^2 * y^2, and x * y * (x^4 - y^4). - Michael Somos, Mar 14 2011
A000027 and A001477 interleaved. - Omar E. Pol, Feb 06 2012
First differences are A168361, extended by an initial -1. (Or: a(n)-a(n-1) = A168361(n+1), for all n >= 1.) - M. F. Hasler, Oct 05 2017
Also the number of unlabeled simple graphs with n + 1 vertices and exactly n endpoints (vertices of degree 1). The labeled version is A327370. - Gus Wiseman, Sep 06 2019

			G.f. = 1 + 2*x^2 + x^3 + 3*x^4 + 2*x^5 + 4*x^6 + 3*x^7 + 5*x^8 + 4*x^9 + 6*x^10 + 5*x^11 + ...
Molien g.f. = 1 + 2*t^4 + t^6 + 3*t^8 + 2*t^10 + 4*t^12 + 3*t^14 + 5*t^16 + 4*t^18 + 6*t^20 + ...

D. Benson, Polynomial Invariants of Finite Groups, Cambridge, p. 23.
S. Mukai, An Introduction to Invariants and Moduli, Cambridge, 2003; see p. 15.
M. D. Neusel and L. Smith, Invariant Theory of Finite Groups, Amer. Math. Soc., 2002; see p. 97.
L. Smith, Polynomial Invariants of Finite Groups, A K Peters, 1995, p. 90.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
H. W. Gould, The inverse of a finite series and a third-order recurrent sequence, Fibonacci Quart. 44 (2006), no. 4, 302-315. See page 311.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, Annals of Combinatorics, 6, 2002, 407-418 (Theorem 3.3).
MathOverflow, A question about an application of Molien's formula to find the generators and relations of an invariant ring.
Gus Wiseman, The a(3) = 2 through a(7) = 4 graphs with exactly n - 1 endpoints.
Index entries for Molien series.
Index entries for two-way infinite sequences.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A000124 (a=1, a=n+a), A028242 (a=1, a=n-a).
Partial sums give A004652. A030451(n)=a(n+1), n>0.
Cf. A052938 (same sequence except no leading 1,0,2).
Cf. A000027, A001477.
Column k = n - 1 of A327371.
Cf. A000035, A004526, A004110, A059167, A109613, A110654, A110657, A110658, A110660, A168361, A245797, A327227, A327369, A327370, A327377.

a:=[1];; for n in [2..80] do a[n]:=(n-1)-a[n-1]; od; a; # Muniru A Asiru, Dec 16 2018

import Data.List (transpose)
a028242 n = n' + 1 - m where (n',m) = divMod n 2
a028242_list = concat $ transpose [a000027_list, a001477_list]
-- Reinhard Zumkeller, Nov 27 2012

&cat[ [n+1, n]: n in [0..37] ]; // Klaus Brockhaus, Nov 23 2009

series((1+x^3)/(1-x^2)^2,x,80);
A028242:=n->floor((n+1+(-1)^n)/2): seq(A028242(n), n=0..100); # Wesley Ivan Hurt, Mar 17 2015

Table[(1 + 2 n + 3 (-1)^n)/4, {n, 0, 74}] (* or *)
LinearRecurrence[{1, 1, -1}, {1, 0, 2}, 75] (* or *)
CoefficientList[Series[(1 - x + x^2)/((1 - x) (1 - x^2)), {x, 0, 74}], x] (* Michael De Vlieger, May 21 2017 *)
Table[{n,n-1},{n,40}]//Flatten (* Harvey P. Dale, Jun 26 2017 *)
Table[3*floor(n/2)-n+1,{n,0,40}] (* Pierre-Alain Sallard, Dec 15 2018 *)

{a(n) = (n\2) - (n%2) + 1} \\ Michael Somos, Oct 02 1999

A028242(n)=n\2+!bittest(n,0) \\ M. F. Hasler, Oct 05 2017

s=((1+x^3)/(1-x^2)^2).series(x, 80); s.coefficients(x, sparse=False) # G. C. Greubel, Dec 16 2018

Expansion of the Molien series for standard action of Quaternions on C^2: (1 + t^6) / (1 - t^4)^2 = (1 - t^12) / ((1 - t^4)^2 * (1 - t^6)) in powers of t^2.
Euler transform of length 6 sequence [0, 2, 1, 0, 0, -1]. - Michael Somos, Mar 14 2011
a(n) = n - a(n-1) [with a(0) = 1] = A000035(n-1) + A004526(n). - Henry Bottomley, Jul 25 2001
G.f.: (1 - x + x^2) / ((1 - x) * (1 - x^2)) = ( 1+x^2-x ) / ( (1+x)*(x-1)^2 ).
a(2*n) = n + 1, a(2*n + 1) = n, a(-1 - n) = -a(n).
a(n) = a(n - 1) + a(n - 2) - a(n - 3).
a(n) = floor(n/2) + 1 - n mod 2. a(2*k) = k+1, a(2*k+1) = k; A110657(n) = a(a(n)), A110658(n) = a(a(a(n))); a(n) = A109613(n)-A110654(n) = A110660(n)/A110654(n). - Reinhard Zumkeller, Aug 05 2005
a(n) = 2*floor(n/2) - floor((n-1)/2). - Wesley Ivan Hurt, Oct 22 2013
a(n) = floor((n+1+(-1)^n)/2). - Wesley Ivan Hurt, Mar 15 2015
a(n) = (1 + 2n + 3(-1)^n)/4. - Wesley Ivan Hurt, Mar 18 2015
a(n) = Sum_{i=1..floor(n/2)} floor(n/(n-i)) for n > 0. - Wesley Ivan Hurt, May 21 2017
a(2n) = n+1, a(2n+1) = n, for all n >= 0. - M. F. Hasler, Oct 05 2017
a(n) = 3*floor(n/2) - n + 1. - Pierre-Alain Sallard, Dec 15 2018
E.g.f.: ((2 + x)*cosh(x) + (x - 1)*sinh(x))/2. - Stefano Spezia, Aug 01 2022
Sum_{n>=2} (-1)^(n+1)/a(n) = 1. - Amiram Eldar, Oct 04 2022

First part of definition adjusted to match offset by Klaus Brockhaus, Nov 23 2009

A327369 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and exactly k endpoints (vertices of degree 1).

Original entry on oeis.org

1, 1, 0, 1, 0, 1, 2, 0, 6, 0, 15, 12, 30, 4, 3, 314, 320, 260, 80, 50, 0, 13757, 10890, 5445, 1860, 735, 66, 15, 1142968, 640836, 228564, 64680, 16800, 2772, 532, 0, 178281041, 68362504, 17288852, 3666600, 702030, 115416, 17892, 1016, 105

Offset: 0

Gus Wiseman, Sep 04 2019

			Triangle begins:
      1
      1     0
      1     0     1
      2     0     6     0
     15    12    30     4     3
    314   320   260    80    50     0
  13757 10890  5445  1860   735    66    15

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

Row sums are A006125.
Row sums without the first column are A245797.
Column k = 0 is A059167.
Column k = 1 is A277072.
Column k = 2 is A277073.
Column k = 3 is A277074.
Column k = n is A123023.
Column k = n - 1 is A327370.
The unlabeled version is A327371.
The covering version is A327377.
Cf. A004110, A055302, A055314, A059166, A059167, A100743, A327227, A327228, A327362, A327364.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Count[Length/@Split[Sort[Join@@#]],1]==k&]],{n,0,5},{k,0,n}]

Row(n)={ \\ R, U, B are e.g.f. of A055302, A055314, A059167.
  my(R=sum(n=1, n, x^n*sum(k=1, n, stirling(n-1, n-k, 2)*y^k/k!)) + O(x*x^n));
  my(U=sum(n=2, n, x^n*sum(k=1, n, stirling(n-2, n-k, 2)*y^k/k!)) + O(x*x^n));
  my(B=x^2/2 + log(sum(k=0, n, 2^binomial(k, 2)*(x*exp(-x + O(x^n)))^k/k!)));
  my(A=exp(x + U + subst(B-x, x, x*(1-y) + R)));
  Vecrev(n!*polcoef(A, n), n + 1);
}
{ for(n=0, 8, print(Row(n))) } \\ Andrew Howroyd, Oct 05 2019

Column-wise binomial transform of A327377.

E.g.f.: exp(x + U(x,y) + B(x*(1-y) + R(x,y))), where R(x,y) is the e.g.f. of A055302, U(x,y) is the e.g.f. of A055314 and B(x) + x is the e.g.f. of A059167. - Andrew Howroyd, Oct 05 2019

Terms a(28) and beyond from Andrew Howroyd, Sep 09 2019

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

Original entry on oeis.org

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

A327372 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with exactly k endpoints (vertices of degree 1).

Original entry on oeis.org

1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 3, 1, 1, 1, 1, 11, 5, 4, 1, 2, 0, 62, 29, 18, 6, 4, 2, 1, 510, 225, 101, 32, 13, 4, 3, 0, 7459, 2674, 842, 223, 72, 19, 9, 3, 1, 197867, 50834, 10784, 2171, 504, 115, 34, 9, 4, 0, 9808968, 1653859, 228863, 32322, 5268, 944, 209, 46, 16, 4, 1

Offset: 0

Gus Wiseman, Sep 04 2019

			Triangle begins:
   1
   0  0
   0  0  1
   1  0  1  0
   3  1  1  1  1
  11  5  4  1  2  0

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)
Gus Wiseman, The unlabeled graphs covering 5 vertices with k endpoints.

Row sums are A002494.
Column k = 0 is A261919.
The non-covering version is A327371.
The labeled version is A327377.
Cf. A000088, A004110, A294217, A327227, A327369, A327370.

\\ Needs G(n) defined in A327371.
T(n)={my(v=Vec(G(n)*(1 - x))); vector(#v, n, Vecrev(v[n], n))}
my(A=T(10)); for(n=1, #A, print(A[n])) \\ Andrew Howroyd, Jan 11 2024

Column-wise first differences of A327371.

Terms a(21) and beyond from Andrew Howroyd, Sep 11 2019

A055540 Total number of leaves (nodes of vertex degree 1) in all graphs of n nodes.

Original entry on oeis.org

0, 2, 4, 14, 38, 153, 766, 6259, 88064, 2324157, 116563882, 11060411527, 1968703079886, 654492092481733, 406111248305672980, 471005105043787823717, 1023566652048387537072658, 4179937690541808658135640875, 32172436158252943170541450460638

Offset: 1

Eric W. Weisstein

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Tree Leaf

Cf. A003227, A003228, A055541, A327371.

\\ See A327371 for G.
seq(n)=Vec(subst(deriv(G(n), y), y, 1), -n) \\ Andrew Howroyd, Jan 22 2021

a(n) = Sum_{k=1..n} k*A327371(n, k). - Andrew Howroyd, Sep 04 2019

a(8) and a(9) from Eric W. Weisstein, Jun 02 2004
a(10) from Andrew Howroyd, Sep 04 2019
Terms a(11) and beyond from Andrew Howroyd, Jan 22 2021

A325115 Number of simple graphs on n unlabeled nodes with exactly 1 endpoint (node of degree 1).

Original entry on oeis.org

0, 0, 0, 1, 6, 35, 260, 2934, 53768, 1707627, 96648020, 9886429142, 1842161884708, 629505254017556, 397043155634566696, 464930596621838689900, 1016021072554513545893264, 4162479064042009639168386134, 32096876145378032622994745784856

Offset: 1

Andrew Howroyd, Sep 04 2019

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50

Column k=1 of A327371.

Cf. A277072 (labeled case), A325125.

Terms a(11) and beyond from Andrew Howroyd, Feb 02 2021

A325125 Number of simple graphs on n unlabeled nodes with exactly 2 endpoints (nodes of degree 1).

Original entry on oeis.org

0, 1, 2, 3, 7, 25, 126, 968, 11752, 240615, 8529544, 534168034, 59794030430, 12082250628276, 4446033336286696, 3002923486915259644, 3748228681583390913192, 8696890616699403375722774, 37700601714008218904828607832, 306674623374061557486512987705844

Offset: 1

Andrew Howroyd, Sep 04 2019

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50

Column k=2 of A327371.

Cf. A277073 (labeled case), A325115.

Terms a(11) and beyond from Andrew Howroyd, Feb 02 2021

A304222 Triangle T(n,k) read by rows: number of simple connected graphs with n nodes and k endpoints, n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 3, 1, 1, 1, 0, 11, 5, 3, 1, 1, 0, 61, 29, 14, 5, 2, 1, 0, 507, 224, 86, 25, 8, 2, 1, 0, 7442, 2666, 762, 184, 48, 11, 3, 1, 0, 197772, 50779, 10173, 1890, 374, 72, 16, 3, 1, 0, 9808209, 1653431, 220627, 29252, 4252, 660, 115, 20, 4, 1, 0

Offset: 0

R. J. Mathar, May 11 2018

Endpoints are vertices with 0 or 1 (less than 2) edges.

			The triangle starts in row n=0 with column 0 <= k <= n as:
       1;
       1,     0;
       0,     0,     1;
       1,     0,     1,    0;
       3,     1,     1,    1,   0;
      11,     5,     3,    1,   1,  0;
      61,    29,    14,    5,   2,  1,  0;
     507,   224,    86,   25,   8,  2,  1, 0;
    7442,  2666,   762,  184,  48, 11,  3, 1, 0;
  197772, 50779, 10173, 1890, 374, 72, 16, 3, 1, 0;

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows 0..50)

Cf. A001349 (row sums), A004108 (first column), A055290 (trees only), A327371.

InvEulerMT(u)={my(n=#u, p=log(1+x*Ser(u)), vars=variables(p)); Vec(sum(i=1, n, moebius(i)*substvec(p + O(x*x^(n\i)), vars, apply(v->v^i,vars))/i) )}
permcount(v) = {my(m=1, s=0, k=0, t); for(i=1, #v, t=v[i]; k=if(i>1&&t==v[i-1], k+1, 1); m*=t*k; s+=t); s!/m}
edges(v) = {sum(i=2, #v, sum(j=1, i-1, gcd(v[i], v[j]))) + sum(i=1, #v, v[i]\2)}
G(n)={sum(k=0, n, my(s=0); forpart(p=k, s+=permcount(p) * 2^edges(p) * prod(i=1, #p, (1 - x^p[i])/(1 - (x*y)^p[i]) + O(x*x^(n-k)))); x^k*s/k!)}
T(n)={my(v=InvEulerMT(Vec(G(n)-1))); v[2]=y^2; concat([[1]], vector(#v, n, Vecrev(v[n], n+1))) }
my(A=T(10)); for(n=1, #A, print(A[n])) \\ Andrew Howroyd, Jan 22 2021

Terms a(55) and beyond from Andrew Howroyd, Jan 22 2021

cp's OEIS Frontend

A028242 Follow n+1 by n. Also (essentially) Molien series of 2-dimensional quaternion group Q_8.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A327369 Triangle read by rows where T(n,k) is the number of labeled simple graphs with n vertices and exactly k endpoints (vertices of degree 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A327372 Triangle read by rows where T(n,k) is the number of unlabeled simple graphs covering n vertices with exactly k endpoints (vertices of degree 1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A055540 Total number of leaves (nodes of vertex degree 1) in all graphs of n nodes.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A325115 Number of simple graphs on n unlabeled nodes with exactly 1 endpoint (node of degree 1).

Views

Author

Keywords

Links

Crossrefs

Extensions

A325125 Number of simple graphs on n unlabeled nodes with exactly 2 endpoints (nodes of degree 1).

Views

Author

Keywords

Links

Crossrefs

Extensions