cp's OEIS Frontend

A032097 "BHK" (reversible, identity, unlabeled) transform of 2,1,1,1,...

%I A032097 #60 May 25 2024 19:35:48
%S A032097 2,2,5,14,39,107,289,772,2047,5402,14213,37325,97905,256622,672337,
%T A032097 1760998,4611643,12075527,31617521,82781216,216732891,567428402,
%U A032097 1485570025,3889310329,10182407329,26657986682,69791674109,182717232062,478360339887
%N A032097 "BHK" (reversible, identity, unlabeled) transform of 2,1,1,1,...
%C A032097 First five terms match the total dominating number of the n-Sierpinski sieve graph. - _Eric W. Weisstein_, Apr 18 2018
%C A032097 From _Petros Hadjicostas_, May 20 2018: (Start)
%C A032097 Using the formulae in C. B. Bower's web link below about transforms, it can be proved that, for k >= 2, the BHK[k] transform of sequence (c(n): n >= 1), which has g.f. C(x) = Sum_{n >= 1} c(n)*x^n, has generating function B_k(x) = (1/2)*(C(x)^k - C(x^2)^{k/2}) if k is even, and B_k(x) = C(x)*B_{k-1}(x) = (C(x)/2)*(C(x)^{k-1} - C(x^2)^{(k-1)/2}) if k is odd. For k=1, Bower assumes that the BHK[k=1] transform of (c(n): n >= 1) is itself, which means that the g.f. of the output sequence is C(x). (This assumption is not accepted by all mathematicians because a sequence of length 1 is not only reversible but palindromic as well.)
%C A032097 Since a(m) = BHK(c(n): n >= 1)(m) = Sum_{k=1..m} BHK[k](c(n): n >= 1)(m) for m = 1,2,3,..., it can be easily proved (using sums of infinite geometric series) that the g.f. of BHK(c(n): n >= 1) is A(x) = (C(x)^2 - C(x^2))/(2*(1-C(x))*(1-C(x^2))) + C(x). (The extra C(x) is due of course to the special assumption made for the BHK[k=1] transform.)
%C A032097 Here, BHK(c(n): n >= 1)(m) indicates the m-th element of the output sequence when the transform is BHK and the input sequence is (c(n): n >= 1). Similarly, BHK[k](c(n): n >= 1)(m) indicates the m-th element of the output sequence when the transform is BHK[k] (i.e., with k boxes) and the input sequence is (c(n): n >= 1).
%C A032097 For the current sequence, c(1) = 2 and c(n) = 1 for all n >= 2, and thus, C(x) = x + x/(1-x). Substituting into the above formula for A(x), and doing the algebra, we get A(x) = x*(x^5-4*x^4+x^3+9*x^2-8*x+2)/((x-1)*(x^2-3*x+1)*(x^2+x-1)), which is the formula given by _Colin Barker_ below.
%C A032097 (End)
%H A032097 Vincenzo Librandi, <a href="/A032097/b032097.txt">Table of n, a(n) for n = 1..1000</a>
%H A032097 C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H A032097 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (5,-7,1,3,-1).
%F A032097 For n > 1, a(n) = (1/2)*(F(2n+1) - F(n+2) + 2), where F(n) = A000045(n). - _Ralf Stephan_, May 04 2004
%F A032097 G.f.: x*(x^5-4*x^4+x^3+9*x^2-8*x+2)/((x-1)*(x^2-3*x+1)*(x^2+x-1)). - _Colin Barker_, Sep 22 2012
%e A032097 From _Petros Hadjicostas_, May 20 2018: (Start)
%e A032097 According to C. G. Bower, in his website above, we have boxes of different colors and sizes (the size of the box is determined by the number of balls it can hold). Since c(1) = 2, each box of size 1 can have one of two colors, say A and B. On the other hand, since c(n) = 1 for n >= 2, each box of size >= 2 can be of one color only (and there is no need to specify it). Then a(n) = BHK(c(n): n >= 1)(n) = number of ways we can have boxes on a line such that the total number of balls is n and the array of boxes is reversible but not palindromic (with the exception when having only one box on the line).
%e A032097 Hence, for n=1, the a(1) = 2 possible arrays are 1_A and 1_B. For n=2, the a(2) = 2 possible arrays for the boxes are 1_A 1_B and 2. (Note that 1_A 1_B is not palindromic because the boxes have different colors even though each one has only 1 ball.)
%e A032097 For n=3, the a(3) = 5 possible arrays for the boxes are:
%e A032097   3 (one box on the line);
%e A032097   1_A 2, 1_B 2 (two boxes on the line);
%e A032097   1_A 1_B 1_B, 1_A 1_A 1_B (three boxes on the line).
%e A032097 For n=4, the a(4) = 14 possible arrays for the boxes are:
%e A032097   4 (one box on the line);
%e A032097   1_A 3, 1_B 3 (two boxes on the line);
%e A032097   1_A 1_A 2, 1_A 1_B 2, 1_B 1_A 2, 1_B 1_B 2, 1_A 2 1_B (three boxes on the line);
%e A032097   1_A 1_A 1_A 1_B, 1_A 1_A 1_B 1_A, 1_A 1_A 1_B 1_B, 1_A 1_B 1_B 1_B,
%e A032097     1_B 1_A 1_B 1_B, 1_A 1_B 1_A 1_B (four boxes on the line).
%e A032097 (End)
%t A032097 CoefficientList[Series[(x^5 - 4 x^4 + x^3 + 9 x^2 - 8 x + 2)/((x - 1) (x^2 - 3 x + 1) (x^2 + x - 1)), {x, 0, 40}], x] (* _Vincenzo Librandi_, Oct 19 2013 *)
%t A032097 Join[{2}, Table[(Fibonacci[2 n + 1] - Fibonacci[n + 2])/2 + 1, {n, 2, 20}]] (* _Eric W. Weisstein_, Apr 18 2018 *)
%t A032097 Join[{2}, LinearRecurrence[{5, -7, 1, 3, -1}, {2, 5, 14, 39, 107}, 20]] (* _Eric W. Weisstein_, Apr 18 2018 *)
%o A032097 (Magma) [2] cat [1/2*(Fibonacci(2*n+1) - Fibonacci(n+2) + 2): n in [2..30]]; // _Vincenzo Librandi_, Oct 19 2013
%K A032097 nonn,easy
%O A032097 1,1
%A A032097 _Christian G. Bower_
%E A032097 More terms from _Vincenzo Librandi_, Oct 19 2013