|
%I #12 Dec 25 2017 04:09:42
%S 0,1,4,16,32,69,108,184,256,385,500,696,864,1141,1372,1744,2048,2529,
%T 2916,3520,4000,4741,5324,6216,6912,7969,8788,10024,10976,12405,13500,
%U 15136,16384,18241,19652,21744,23328,25669,27436,30040,32000,34881,37044,40216
%N Maximum detour index of any bipartite graph on n nodes.
%H Andrew Howroyd, <a href="/A296819/b296819.txt">Table of n, a(n) for n = 1..1000</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BipartiteGraph.html">Bipartite Graph.</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/DetourIndex.html">Detour Index</a>
%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (1,3,-3,-3,3,1,-1).
%F a(2*n-1) = 4*(n-1)^3, a(2*n) = n*(4*n^2 - 5*n + 2).
%F a(n^2) = A296779(n), a(n^3) = A296780(n), a(n!) = A296785(n), a(2^n) = A288720(n).
%F From _Colin Barker_, Dec 21 2017: (Start)
%F G.f.: x^2*(1 + 3*x + 9*x^2 + 7*x^3 + 4*x^4) / ((1 - x)^4*(1 + x)^3).
%F a(n) = a(n-1) + 3*a(n-2) - 3*a(n-3) - 3*a(n-4) + 3*a(n-5) + a(n-6) - a(n-7) for n>7.
%F (End)
%t Rest@ CoefficientList[Series[x^2*(1 + 3 x + 9 x^2 + 7 x^3 + 4 x^4)/((1 - x)^4*(1 + x)^3), {x, 0, 44}], x] (* _Michael De Vlieger_, Dec 24 2017 *)
%o (PARI)
%o MaxBipartiteDetourIndex(a,b) = { a*(a-1)*min(a-1,b) + b*(b-1)*min(b-1,a) + a*b*(2*min(a,b)-1) }
%o a(n) = MaxBipartiteDetourIndex(floor(n/2), ceil(n/2));
%o (PARI) concat(0, Vec(x^2*(1 + 3*x + 9*x^2 + 7*x^3 + 4*x^4) / ((1 - x)^4*(1 + x)^3) + O(x^40))) \\ _Colin Barker_, Dec 21 2017
%Y Cf. A288720, A296779, A296780, A296785.
%K nonn,easy
%O 1,3
%A _Andrew Howroyd_, Dec 21 2017
|
