A073717 -id:A073717 - cp's OEIS frontend

A326329 Number of simple graphs covering {1..n} with no crossing or nesting edges.

1, 0, 1, 4, 13, 44, 149, 504, 1705, 5768, 19513, 66012

Offset: 0

Gus Wiseman, Jun 27 2019

Covering means there are no isolated vertices. Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

Is this (apart from offsets) the same as A073717? - R. J. Mathar, Jul 04 2019

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
Gus Wiseman, The a(5) = 44 covering simple graphs with no crossing or nesting edges.

The case for set partitions is A001519.
Covering simple graphs are A006129.
The case with just nesting or just crossing edges forbidden is A324169.
The binomial transform is the non-covering case A326244.
Cf. A000108, A006125, A007297, A054726, A099947, A324327, A326279, A326293.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

A216182 Riordan array ((1+x)/(1-x)^2, x(1+x)^2/(1-x)^2).

Original entry on oeis.org

1, 3, 1, 5, 7, 1, 7, 25, 11, 1, 9, 63, 61, 15, 1, 11, 129, 231, 113, 19, 1, 13, 231, 681, 575, 181, 23, 1, 15, 377, 1683, 2241, 1159, 265, 27, 1, 17, 575, 3653, 7183, 5641, 2047, 365, 31, 1, 19, 833, 7183, 19825, 22363, 11969, 3303, 481, 35, 1

Offset: 0

Philippe Deléham, Mar 11 2013

Triangle formed of odd-numbered columns of the Delannoy triangle A008288.

			Triangle begins
   1;
   3,   1;
   5,   7,    1;
   7,  25,   11,    1;
   9,  63,   61,   15,    1;
  11, 129,  231,  113,   19,    1;
  13, 231,  681,  575,  181,   23,   1;
  15, 377, 1683, 2241, 1159,  265,  27,  1;
  17, 575, 3653, 7183, 5641, 2047, 365, 31, 1;
  ...

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. (columns:) A005408, A001845, A001847, A001849, A008419.
Cf. Diagonals: A000012, A004767, A060820.
Cf. A008288 (Delannoy triangle), A114123 (even-numbered columns of A008288).

A216182[n_, k_]:= Hypergeometric2F1[-n +k, -2*k-1, 1, 2];
Table[A216182[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Nov 19 2021 *)

def A216182(n,k): return simplify( hypergeometric([-n+k, -2*k-1], [1], 2) )
flatten([[A216182(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Nov 19 2021

T(2n, n) = A108448(n+1).
Sum_{k=0..n} T(n,k) = A073717(n+1).
From G. C. Greubel, Nov 19 2021: (Start)
T(n, k) = A008288(n+k+1, 2*k+1).
T(n, k) = hypergeometric([-n+k, -2*k-1], [1], 2). (End)

A075536 a(n) = ((1+(-1)^n)T(n+1) + (1-(-1)^n)S(n))/2, where T(n) = tribonacci numbers A000073, S(n) = generalized tribonacci numbers A001644.

Original entry on oeis.org

0, 1, 1, 7, 4, 21, 13, 71, 44, 241, 149, 815, 504, 2757, 1705, 9327, 5768, 31553, 19513, 106743, 66012, 361109, 223317, 1221623, 755476, 4132721, 2555757, 13980895, 8646064, 47297029, 29249425, 160004703, 98950096, 541292033, 334745777

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Sep 23 2002

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0, 3, 0, 1, 0, 1).

Cf. A000073, A001644, A005013, A005247.

R:=PowerSeriesRing(Integers(), 40); [0] cat Coefficients(R!( x*(1+x+4*x^2+x^3-x^4)/(1-3*x^2-x^4-x^6) )); // G. C. Greubel, Apr 21 2019

A075536 := proc(n)
    if type(n,'even') then
        A000073(n+1) ;
    else
        A001644(n) ;
    end if;
end proc:
seq(A075536(n),n=0..80) ; # R. J. Mathar, Aug 05 2021

CoefficientList[Series[(x+x^2+4x^3+x^4-x^5)/(1-3x^2-x^4-x^6), {x, 0, 40}], x]
LinearRecurrence[{0,3,0,1,0,1},{0,1,1,7,4,21},40] (* Harvey P. Dale, Jul 10 2012 *)

my(x='x+O('x^40)); concat([0], Vec(x*(1+x+4*x^2+x^3-x^4)/(1-3*x^2-x^4-x^6))) \\ G. C. Greubel, Apr 21 2019

(x*(1+x+4*x^2+x^3-x^4)/(1-3*x^2-x^4-x^6)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Apr 21 2019

a(2n) = A073717(n) = A000073(2n+1).
a(2n+1) = A001644(2n+1).
a(n) = 3*a(n-2) + a(n-4) + a(n-6), a(0)=0, a(1)=1, a(2)=1, a(3)=7, a(4)=4, a(5)=21.
O.g.f.: x*(1 + x + 4*x^2 + x^3 - x^4)/(1 - 3*x^2 - x^4 - x^6).

Index in definition corrected. - R. J. Mathar, Aug 05 2021

cp's OEIS Frontend

A326329 Number of simple graphs covering {1..n} with no crossing or nesting edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A216182 Riordan array ((1+x)/(1-x)^2, x(1+x)^2/(1-x)^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

A075536 a(n) = ((1+(-1)^n)T(n+1) + (1-(-1)^n)S(n))/2, where T(n) = tribonacci numbers A000073, S(n) = generalized tribonacci numbers A001644.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

cp's OEIS Frontend

A326329 Number of simple graphs covering {1..n} with no crossing or nesting edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A216182 Riordan array ((1+x)/(1-x)^2, x(1+x)^2/(1-x)^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

A075536 a(n) = ((1+(-1)^n)*T(n+1) + (1-(-1)^n)*S(n))/2, where T(n) = tribonacci numbers A000073, S(n) = generalized tribonacci numbers A001644.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A075536 a(n) = ((1+(-1)^n)T(n+1) + (1-(-1)^n)S(n))/2, where T(n) = tribonacci numbers A000073, S(n) = generalized tribonacci numbers A001644.