A307157 a(n) is the Narumi-Katayama index of the Fibonacci cube Gamma(n).

1, 2, 24, 1152, 1399680, 290237644800, 520105859481600000000, 3435834286784202670080000000000000000, 3045775242579858715944293498880000000000000000000000000000000000

Offset

1,2

Comments

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.

The Narumi-Katayama index of a connected graph is the product of the degrees of the vertices of the graph.

Links

Table of n, a(n) for n=1..9.

I. Gutman and M. Ghorbani, Some properties of the Narumi-Katayama index, Applied Mathematics Letters, Vol. 25, No. 10 (2012), 1435-1438.

S. Klavžar, Structure of Fibonacci cubes: a survey, Journal of Combinatorial Optimization, Vol. 25, No. 4 (2013), 505-522.

S. Klavžar, M. Mollard and M. Petkovšek, The degree sequence of Fibonacci and Lucas cubes, Discrete Mathematics, Vol. 311, No. 14 (2011), 1310-1322.

Formula

a(n) = Product_{k=1..n} k^T(n, k), where T(n, k) = Sum_{i=0..k} binomial(n-2*i, k-i)*binomial(i+1, n-k-i+1). T(n,k) gives the number of vertices of degree k in the Fibonacci cube Gamma(n) (see A245825).

Example

a(2)=2 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 Narumi-Katayama index is 1*1*2=2.

Maple

T := (n, k) -> add(binomial(n-2*i, k-i)*binomial(i+1, n-k-i+1), i=0..k):
seq(mul(j^T(n, j), j=1..n), n=1..10);

Crossrefs

Cf. A000045, A245825.

Sequence in context: A362091 A330087 A357827 * A354557 A137887 A232310

Adjacent sequences: A307154 A307155 A307156 * A307158 A307159 A307160

Keyword

nonn,easy

Author

Emeric Deutsch, Mar 27 2019

Status

approved