login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(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)
OFFSET

1,2

COMMENTS

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.

(End)

LINKS

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

C. G. Bower, Transforms (2)

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

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

(End)

CROSSREFS

Cf. A000045, A001906.

Sequence in context: A053391 A183956 A221843 * A243797 A120896 A074801

Adjacent sequences:  A032096 A032097 A032098 * A032100 A032101 A032102

KEYWORD

nonn

AUTHOR

Christian G. Bower

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 06:02 EDT 2018. Contains 316432 sequences. (Running on oeis4.)