A056571 -id:A056571 - cp's OEIS frontend

A349817 Number of 4 X n Fibonacci minimal checkerboards.

1, 15, 50, 254, 1202, 5774, 27650, 132494, 634802, 3041534, 14572850, 69822734, 334540802, 1602881294, 7679865650, 36796446974, 176302369202, 844715399054, 4047274626050, 19391657731214, 92911014030002, 445163412418814, 2132906048064050, 10219366827901454, 48963928091443202

Offset: 1

N. J. A. Sloane, Dec 24 2021

nonn

a(n) is the number of tilings of a 4 X n board by monominoes and dominoes with all dominoes placed horizontally which cannot be decomposed into two or more such tilings placed end to end. - Andrew Howroyd, Feb 28 2023

			a(2) = 15. Each row of a 4 X 2 board can be tiled with either a domino or two monominoes giving a total of 2^4 = 16 tilings. The tiling consisting of all monominoes is not minimal so a(2) = 16 - 1 = 15. - _Andrew Howroyd_, Feb 28 2023

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Yifan Zhang and George Grossman, A Combinatorial Proof for the Generating Function of Powers of the Fibonacci Sequence, Fib. Q., 55:3 (2017), 235-242.

Cf. A056571.

\\ x*F(n,4) gives g.f. of A056571.
F(n,k)=sum(i=0, n, fibonacci(i+1)^k*x^i, O(x*x^n))
Vec(1 - 1/F(25,4)) \\ Andrew Howroyd, Feb 28 2023

Lemma 2.23 of Zhang-Grossman gives a formula.

G.f.: 1 - 1/B(x) where x*B(x) is the g.f. of A056571. - Andrew Howroyd, Feb 28 2023

Terms a(11) and beyond from Andrew Howroyd, Feb 28 2023

A358917 a(n) = Fibonacci(n+1)^4 - Fibonacci(n-1)^4.

Original entry on oeis.org

0, 1, 15, 80, 609, 4015, 27936, 190385, 1307775, 8956144, 61405905, 420831071, 2884553280, 19770670945, 135511114479, 928804587920, 6366127657281, 43634071586575, 299072419071840, 2049872742473489, 14050037090947935, 96300386075488816, 660052667580788145

Offset: 0

Feryal Alayont, Dec 05 2022

a(n) is the number of edge covers of a spider graph with four branches where each branch has n vertices besides the center vertex.
An edge cover of a graph is a subset of edges for which each vertex is incident to at least one edge in the subset.
The idea is each branch is treated as a path P_(n+2). Each branch acts independently then and has F(n+1) covers (P_n has F(n-1) covers), hence F(n+1)^4 total. Except we remove the cases where each branch is missing the connecting edge to the center, which is when that edge cover comes from P_n , hence the minus F(n-1)^4.

			Case n=1 is a star graph with four branches and one edge cover (all edges).
   *   *
    \ /
  *__C__*
For n=2, there are 15 edge covers of the graph obtained by gluing four P_3 paths at one single vertex. Each of the pendant edges of the P_3's have to be in the edge cover for the pendants to be incident with an edge. The middle vertices are then automatically incident with at least one edge. There remains the center vertex. We then need at least one of the remaining four edges to be in the subset, giving us 2^4-1 choices.
    *       *
     \     /
      *   *
       \ /
  *__*__C__*__*

Michael De Vlieger, Table of n, a(n) for n = 0..1196
Feryal Alayont and Evan Henning, Edge Covers of Caterpillars, Cycles with Pendants, and Spider Graphs, J. Int. Seq. (2023) Vol. 26, Art. 23.9.4.
Index entries for linear recurrences with constant coefficients, signature (4,19,4,-1).

Cf. A000032, A000045, A056571, A099014, A358934.

LinearRecurrence[{4, 19, 4, -1}, {0, 1, 15, 80}, 25] (* Amiram Eldar, Dec 06 2022 *)

from sympy import fibonacci
def a(n): return fibonacci(n+1)**4-fibonacci(n-1)**4

From Stefano Spezia, Dec 06 2022: (Start)
G.f.: x*(1 + 11*x + x^2)/((1 - 7*x + x^2)*(1 + 3*x + x^2)).
a(n) = 4*a(n-1) + 19*a(n-2) + 4*a(n-3) - a(n-4) for n > 3. (End)
5*a(n) = 9*A004187(n) + 4*(-1)^n*A001906(n) . - R. J. Mathar, May 07 2024
a(n) = L(n) * A099014(n). - Greg Dresden and Chuanqi Wei, Sep 04 2025

cp's OEIS Frontend

A349817 Number of 4 X n Fibonacci minimal checkerboards.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions