|
| |
|
|
A032099
|
|
"BHK" (reversible, identity, unlabeled) transform of 1,2,3,4,...
|
|
0
|
|
|
|
1, 2, 5, 10, 27, 66, 181, 470, 1263, 3310, 8767, 22980, 60449, 158354, 415353, 1087690, 2849675, 7461318, 19539429, 51156950, 133944931, 350677822, 918123935, 2403693960, 6293050657, 16475457986, 43133566061
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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 not only is reversible but palindromic as well.)
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 (a(m): m >= 1) = 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.)
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).
For the current sequence, c(n) = n for all n >= 1, and thus, C(x) = x/(1-x)^2. Substituting into the above formula for A(x), and doing the algebra, we get A(x) = x*(1-3*x+5*x^3-3*x^5+x^6)/((1-x)^2*(1-x-x^2)*(1+x-x^2)*(1-3*x+x^2)), which is the g.f. given by Christian G. Bower below.
Using partial fraction decomposition, we get A(x) = (x/(1-x)^2)+ (1/2)*(x/(x^2-3*x+1) + (2*x+1)/(1+x-x^2) - (x+1)/(1-x-x^2)), from which we can prove the formula for a(n) below.
(End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: x*(1-3x+5x^3-3x^5+x^6)/((1-x)^2(1-x-x^2)(1+x-x^2)(1-3x+x^2)).
a(n) = n + (1/2)*(Fibonacci(2*n) + (-1)^(n+1)*Fibonacci(n-2) - Fibonacci(n+2)) for n >= 2. - Petros Hadjicostas, Aug 21 2018
|
|
|
EXAMPLE
|
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(n) = n, each box of size n can have one of n colors, say A, B, etc. (The colors for a box of size n are not necessarily the same as the colors for a box of size m <> n, but, for simplicity, we denote the colors by A, B, etc. for all box sizes.)
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).
Hence, for n=1, there is only a(1) = 1 possible array, which is 1_A (since no other colors are allowed for a box of size 1).
For n=2, the a(2) = 2 possible arrays for the boxes are: 2_A and 2_B (since a single box by itself is not consider a palindrome by Bower).
For n=3, the a(3) = 5 possible arrays for the boxes are: 3_A, 3_B, 3_C, 1+2_A, 1+2_B. (Here, 1+2_A = 2_A+1 and 1+2_B = 2_B+1 since the arrays are reversible. Also, by writing 1, we mean 1_A.)
For n=4, the a(4) = 10 possible arrays for the boxes are: 4_A, 4_B, 4_C, 4_D, 1+3_A, 1+3_B, 1+3_C, 2_A+2_B, 1+1+2_A, 1+1+2_B. (Note that 2_A+2_B = 2_B+2_A, 1+1+2_A = 2_A+1+1, and 1+1+2_B = 2_B+1+1. The arrays 1+2_A+1 and 1+2_B+1 are not allowed because they are palindromic.)
(End)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
