login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A297670 Number of chordless cycles in the n-triangular graph. 2
0, 0, 3, 27, 177, 1137, 7962, 62730, 555894, 5487894, 59740389, 710770989, 9174169647, 127661751951, 1904975487876, 30341995264356, 513771331466556, 9215499383108604, 174548332364310423, 3481204991988350223, 72920994844093190013, 1600596371590399670013 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,3

LINKS

Andrew Howroyd, Table of n, a(n) for n = 2..200

Eric Weisstein's World of Mathematics, Chordless Cycle

Eric Weisstein's World of Mathematics, Johnson Graph

Eric Weisstein's World of Mathematics, Triangular Graph

FORMULA

a(n) = Sum_{k=4..n} n!/(2*k*(n-k)!). - Andrew Howroyd, Jan 04 2018

a(n) = n*((3 - 2*n)*n + 6*Hypergeometric3F1[1, 1, 1 - n; 2; -1] - 7)/12. - Eric W. Weisstein, Jan 05 2018

-(-1 + n)*n*(1 + n) + (4 + 2*(-1 + n))*a(n) + (-6 - 2*(-1 + n))*a(n + 1) + 2*a(n + 2) = 0. - Eric W. Weisstein, Jan 07 2018

EXAMPLE

From Andrew Howroyd, Jan 04 2018: (Start)

Vertices can be represented by a pair of integers with 12 being the same as 21.

a(4) = 3 because the possible cycles are: -12-23-34-41-, -12-24-43-31-, -13-32-24-41-.

a(5) = 27 because there are 15 cycles of length 4 and 12 cycles of length 5.

(End)

MAPLE

A297670List := proc(n) local A, R, f, i; A:=[0, 0, 0, 6, 54, 354, 2274]; R:=NULL;

f := i -> (24*(12*A[1]-33*A[2]+23*A[3]+3*A[4]-5*A[5])-(4*(90*A[1]-255*A[2]

+212*A[3]-26*A[4]-31*A[5]+16*A[6])+(-208*A[1]+618*A[2]-604*A[3]+197*A[4]

+15*A[5]-35*A[6]+(82*A[1]-257*A[2]+285*A[3]-137*A[4]+27*A[5]+6*A[6]+

(-20*A[1]+66*A[2]-83*A[3]+52*A[4]-18*A[5]+2*A[6]+(+2*A[1]-7*A[2]+10*A[3]

-8*A[4]+4*A[5]-A[6])*i)*i)*i)*i)*i)/((-24+(17+(i-6)*i)*i)*i);

for i from 1 to n do if i<7 then R:=R, A[i+1]/2 else A[1]:=A[2]; A[2]:=A[3];

A[3]:=A[4]; A[4]:=A[5]; A[5]:=A[6]; A[6]:=A[7]; A[7]:=f(i); R:=R, A[7]/2 fi od;

R end: A297670List(22); # Peter Luschny, Jan 06 2018

MATHEMATICA

Table[Sum[n!/(2 k (n - k)!), {k, 4, n}], {n, 2, 20}]

Table[n ((3 - 2 n) n + 6 HypergeometricPFQ[{1, 1, 1 - n}, {2}, -1] - 7)/12, {n, 2, 20}]

RecurrenceTable[{-(-1 + n) n (1 + n) + (4 + 2 (-1 + n)) a[n] + (-6 - 2 (-1 + n)) a[n + 1] + 2 a[n + 2] == 0, a[1] == 0, a[2] == 0}, a[n], {n, 2, 20}]

PROG

(PARI) a(n)={sum(k=4, n, n!/(2*k*(n-k)!))} \\ Andrew Howroyd, Jan 04 2018

CROSSREFS

Cf. A129349, A234629.

Sequence in context: A141442 A053932 A027507 * A220820 A241271 A222015

Adjacent sequences:  A297667 A297668 A297669 * A297671 A297672 A297673

KEYWORD

nonn

AUTHOR

Eric W. Weisstein, Jan 02 2018

EXTENSIONS

Terms a(8) and beyond from Andrew Howroyd, Jan 04 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 10:31 EDT 2020. Contains 337166 sequences. (Running on oeis4.)