|
%I #16 Mar 29 2019 04:16:28
%S 2,6,22,54,132,292,626,1290,2594,5102,9864,18792,35362,65838,121454,
%T 222246,403788,728972,1308562,2336946,4154170,7353310,12965904,
%U 22781520,39897410,69662166,121292998,210642966,364928532,630794356
%N a(n) is the first Zagreb index of the Fibonacci cube Gamma(n).
%C The Fibonacci cube Gamma(n) can be defined as the graph whose vertices are the binary strings of length n without two consecutive 1's and in which two vertices are adjacent when their Hamming distance is exactly 1.
%C The first Zagreb index of a simple connected graph is the sum of the squared degrees of its vertices. Alternatively, it is the sum of the degree sums d(i)+d(j) over all edges ij of the graph.
%C In the Maple program, T(n,k) gives the number of vertices of degree k in the Fibonacci cube Gamma(n) (see A245825).
%H S. Klavžar, <a href="http://dx.doi.org/10.1007/s10878-011-9433-z">Structure of Fibonacci cubes: a survey</a>, J. Comb. Optim., 25, 2013, 505-522.
%H S. Klavžar, M. Mollard and M. Petkovšek, <a href="https://doi.org/10.1016/j.disc.2011.03.019">The degree sequence of Fibonacci and Lucas cubes</a>, Discrete Mathematics, Vol. 311, No. 14 (2011), 1310-1322.
%F a(n) = Sum_{k=1..n} T(n,k)*k^2, where T(n,k) = Sum_{i=0..k} binomial(n-2*i, k-i) * binomial(i+1, n-k-i+1).
%F Conjectures from _Colin Barker_, Mar 28 2019: (Start)
%F G.f.: 2*x*(1 + 2*x^2 - x^3) / (1 - x - x^2)^3.
%F a(n) = 3*a(n-1) - 5*a(n-3) + 3*a(n-5) + a(n-6) for n>6.
%F (End)
%e a(2) = 6 because the Fibonacci cube Gamma(2) is the path-tree P_3 having 2 vertices of degree 1 and 1 vertex of degree 2; consequently, the Zagreb index is 1^2 + 1^2 + 2^2 = 6 (or (1 + 2) + (2 + 1) = 6).
%p T:=(n,k) -> sum(binomial(n - 2*i, k - i) * binomial(i + 1, n - k - i + 1), i = 0..k): seq(add(T(n, k)*k^2, k=1..n), n=1..30);
%Y Cf. A245825.
%K nonn
%O 1,1
%A _Emeric Deutsch_, Mar 26 2019
|
