login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of chordless cycles in the complete tripartite graph K_{n,n,n}.
0

%I #13 Oct 30 2024 11:30:52

%S 0,3,27,108,300,675,1323,2352,3888,6075,9075,13068,18252,24843,33075,

%T 43200,55488,70227,87723,108300,132300,160083,192027,228528,270000,

%U 316875,369603,428652,494508,567675,648675,738048,836352,944163,1062075,1190700

%N Number of chordless cycles in the complete tripartite graph K_{n,n,n}.

%C The only chordless cycles in a complete tripartite graph are cycles of length 4 confined to two of the partitions. - _Andrew Howroyd_, Jan 03 2018

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ChordlessCycle.html">Chordless Cycle</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CompleteTripartiteGraph.html">Complete Tripartite Graph</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (5, -10, 10, -5, 1).

%F a(n) = 3*n^2*(n-1)^2/4 = 3*A000537(n). - _Andrew Howroyd_, Jan 03 2018

%F a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5).

%F G.f.: -3*x^2*(1 + 4*x + x^2)/(-1 + x)^5.

%t Table[3 Binomial[n, 2]^2, {n, 20}]

%t 3 Binomial[Range[20], 2]^2

%t LinearRecurrence[{5, -10, 10, -5, 1}, {0, 3, 27, 108, 300}, 20]

%t SeriesCoefficient[Series[-3 x (1 + 4 x + x^2)/(-1 + x)^5, {x, 0, 20}], x]

%o (PARI) a(n) = 3*n^2*(n-1)^2/4; \\ _Andrew Howroyd_, Jan 03 2018

%Y Cf. A000537, A234616.

%K nonn,easy

%O 1,2

%A _Eric W. Weisstein_, Jan 02 2018

%E a(6)-a(36) from _Andrew Howroyd_, Jan 03 2018