cp's OEIS Frontend

A326118 a(n) is the largest number of squares of unit area connected only at corners and without holes that can be inscribed in an n X n square.

%I A326118 #68 Apr 23 2023 07:27:23
%S A326118 0,1,2,5,6,9,14,21,24,29,36,45,50,57,66,77,84,93,104,117,126,137,150,
%T A326118 165,176,189,204,221,234,249,266,285,300,317,336,357,374,393,414,437,
%U A326118 456,477,500,525,546,569,594,621,644,669,696,725,750,777,806,837,864,893
%N A326118 a(n) is the largest number of squares of unit area connected only at corners and without holes that can be inscribed in an n X n square.
%C A326118 a(n) is equal to h_4(n) as defined in A309038.
%C A326118 a(n) is the maximum size of an induced subtree in the graph of the black squares of an n X n checkerboard, where edges connect diagonally adjacent squares. - _Andrew Howroyd_, Sep 10 2019
%H A326118 Stefano Spezia, <a href="/A326118/b326118.txt">Table of n, a(n) for n = 0..10000</a>
%H A326118 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,0,1,-2,1).
%F A326118 O.g.f.: x*(1 + 2*x^2 - 2*x^3 + x^4 + 2*x^5 - 2*x^7)/((1 - x)^3*(1 + x)*(1 + x^2)).
%F A326118 E.g.f.: -3*exp(-x)/8 + (2 + x)^2 + exp(x)/8*(-29 + 2*x*(7 + x)) - 3*sin(x)/2.
%F A326118 a(n) = 2*a(n-1) - a(n-2) + a(n-4) - 2*a(n-5) + a(n-6) for n > 8.
%F A326118 a(n) = (1/8)*(-29 + 12*n + 2*n^2 - 3*(-1)^n - 12*sin(n*Pi/2)) for n > 2, a(0) = 0, a(1) = 1, a(2) = 2.
%F A326118 Limit_{n->oo} a(n)/A000290(n) = 1/4.
%e A326118 Illustrations for n = 1..7:
%e A326118      __              __              __    __
%e A326118     |__|            |__|__          |__|__|__|
%e A326118                        |__|          __|__|__
%e A326118                                     |__|  |__|
%e A326118     a(1) = 1        a(2) = 2         a(3) = 5
%e A326118      __    __                  __    __
%e A326118     |__|__|__|                |__|__|__|
%e A326118      __|__|__                  __|__|__    __
%e A326118     |__|  |__|__              |__|  |__|__|__|
%e A326118              |__|                    __|__|__
%e A326118                                     |__|  |__|
%e A326118         a(4) = 6                  a(5) = 9
%e A326118      __    __    __      __    __    __    __
%e A326118     |__|__|__|  |__|__  |__|__|__|  |__|__|__|
%e A326118      __|__|__    __|__|  __|__|__    __|__|__
%e A326118     |__|  |__|__|__|    |__|  |__|__|__|  |__|
%e A326118      __    __|__|__      __    __|__|__    __
%e A326118     |__|__|__|  |__|__  |__|__|__|  |__|__|__|
%e A326118        |__|        |__|  __|__|__    __|__|__
%e A326118                         |__|  |__|  |__|  |__|
%e A326118        a(6) = 14              a(7) = 21
%t A326118 Join[{0,1,2},Table[(1/8)*(-29+12*n+2*n^2-3(-1)^n-12*Sin[n*Pi/2]),{n,3,57}]]
%o A326118 (Magma) I:=[0, 1, 2, 5, 6, 9, 14, 21, 24]; [n le 9 select I[n] else 2*Self(n-1)-Self(n-2)+Self(n-4)-2*Self(n-5)+Self(n-6): n in [1..58]];
%o A326118 (PARI) concat([0], Vec(x*(-1-2*x^2+2*x^3-x^4-2*x^5+2*x^7)/((-1+x)^3*(1+x)*(1+x^2))+O(x^58)))
%Y A326118 Cf. A000290, A309038, A338329 (1st differences).
%K A326118 nonn,easy
%O A326118 0,3
%A A326118 _Stefano Spezia_, Sep 10 2019