This site is supported by donations to The OEIS Foundation.



Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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)



From Petros Hadjicostas, Aug 21 2018: (Start)

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.



Table of n, a(n) for n=1..27.

C. G. Bower, Transforms (2)


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


From Petros Hadjicostas, Aug 21 2018: (Start)

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.)



Cf. A000045, A001906.

Sequence in context: A053391 A183956 A221843 * A243797 A120896 A074801

Adjacent sequences:  A032096 A032097 A032098 * A032100 A032101 A032102




Christian G. Bower



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 07:18 EST 2019. Contains 319269 sequences. (Running on oeis4.)