A396818 Total number of separating two-component spanning forests over all unordered pairs of vertices in the wheel graph W_n.

48, 240, 1045, 4128, 15225, 53424, 180576, 592900, 1902241, 5989248, 18564793, 56791280, 171782160, 514566528, 1528298725, 4505245344, 13192832001, 38403822600, 111195838656, 320408071588, 919203450913, 2626517214720, 7477481038225, 21216084771128, 60009979734000, 169250827737264

Offset

4,1

Comments

Here F_G(u|v) denotes the number of spanning forests of G with exactly two connected components such that u and v belong to different components.

This sequence is defined by a(n) = Sum F_{W_n}(u|v), where the sum is over all unordered pairs {u,v} of vertices of the wheel graph W_n.

Equivalently, a(n) = b(n) + (n-1)*F_{2n-2}, where b(n) is the corresponding sum over all unordered pairs of rim vertices, F_n is the n-th Fibonacci number, and W_n has n-1 rim vertices.

Links

Table of n, a(n) for n=4..29.

Formula

a(n) = m*((L_{2m}-2)*(F_{2q+1}-1) - F_{2m}*(L_{2q+1}-2q-1)) - e_m*m/2*(F_m*(L_{2m}-2) - F_{2m}*(L_m-2)) + m*F_{2m}, where m = n-1, q = floor(m/2), and e_m = (1+(-1)^m)/2, and where F_n is the n-th Fibonacci number and L_n is the n-th Lucas number.

Example

For n=4, the graph W_4 has four vertices. The sum over all unordered pairs of rim vertices is 24, and the three center-rim pairs each contribute F_6=8. Hence a(4)=24+3*8=48.

Crossrefs

Cf. A396817, A000045, A000032.

Sequence in context: A230136 A157913 A181773 * A052683 A206054 A206047

Adjacent sequences: A396815 A396816 A396817 * A396819 A396820 A396821

Keyword

nonn

Author

Shunya Tamura, Jun 06 2026

Status

approved