A297670 Number of chordless cycles in the n-triangular graph.

0, 0, 3, 27, 177, 1137, 7962, 62730, 555894, 5487894, 59740389, 710770989, 9174169647, 127661751951, 1904975487876, 30341995264356, 513771331466556, 9215499383108604, 174548332364310423, 3481204991988350223, 72920994844093190013, 1600596371590399670013

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

a(n) = A002807(n) - A000292(n-2). - Pontus von Brömssen, Apr 29 2023

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. A000292, A002807, A129349, A234629.

Sequence in context: A141442 A053932 A027507 * A220820 A370710 A241271

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