login
A276129
a(n) is the number of ordered ways to tile a strip of length n+2 with white tiles of odd lengths summing to length n and two red squares.
1
1, 3, 6, 13, 27, 54, 106, 204, 387, 725, 1344, 2469, 4500, 8145, 14652, 26213, 46665, 82704, 145982, 256722, 449937, 786109, 1369494, 2379447, 4123944, 7130895, 12303714, 21186013, 36411399, 62466906, 106987282, 182946888, 312367887, 532587461, 906840060
OFFSET
0,2
COMMENTS
a(n) is a specific case of b(r,n), the number of ordered ways to rearrange a tiling of length n + r, with odd(1,3,5...) white tiles summing to n and r red squares.
Define the following summation: b(0,r,n) = b(r,n); b(1,r,n) = b(r, n-2) + b(r, n-4) + b(r, n-6) + ..; b(s, r, n) = b(s-1, r, n-2) + b(s-1, r, n-4) + b(r-1, s, n-6) + ...
The number of compositions of n with exactly r even numbers is b(r, r, n-2r).
Except for the initial 1, this is the p-INVERT transform of (1,0,1,0,1,0,...) for p(S) = (1 - S)^3. See A291219. - Clark Kimberling, Sep 04 2017
FORMULA
a(n) = Sum_{k=0..floor((n-1)/2)} binomial(n-2*k+2, 2)*binomial(n-k-1, k)) for n > 0. - Andrew Howroyd, Dec 26 2017
b(0,0)=1. For n>=1, b(0,n) = b(0,0,n) = the n-th Fibonacci number, A000045(n).
b(1,0)=1. For n>=1, b(1,n) = A239342(n+1).
b(2,n) = a(n) = a(n-1) + a(n-2) + A239342(n+1) + A239342(n-1).
G.f. for b(2,n): ((1-x^2)/(1-x-x^2))^3.
G.f. for b(r,n): ((1-x^2)/(1-x-x^2))^(r+1).
b(1,1,n) = A029907(n+1).
b(r,n) = b(r, n-1) + b(r, n-2) + b(r-1, n) - b(r-1, n-2).
b(r,r,n) = b(r-1, r-1, n) + b(r, r, n-1) + b(r, r, n-2).
G.f. for b(r,r,n): (1-x^2)/((1-x-x^2)^(r+1)).
EXAMPLE
Let 1,3 be the lengths of the odd tiles summing to 3 and let r,r be the two odd squares. Then the resulting number of compositions is a(3) = 13. The 6 compositions are 3,r,r; r,3,r; r,r,3; 1,1,1,r,r; 1,1,r,r,1; 1,r,r,1,1; r,r,1,1,1; 1,1,r,1,r; 1,r,1,r,1; r,1,r,1,1; r,1,1,r,1; 1,r,1,1,r; r,1,1,1,r.
MAPLE
b:= proc(n, m) option remember;
`if`(n+m=0, 1, `if`(m>0, b(n, m-1), 0)+
add(`if`(j::odd, b(n-j, m), 0), j=1..n))
end:
a:= n-> b(n, 2):
seq(a(n), n=0..50); # Alois P. Heinz, Aug 29 2016
MATHEMATICA
a[0] = 1; a[n_] := Sum[Binomial[n - 2*k + 2, 2]*Binomial[n - k - 1, k], {k, 0, (n - 1)/2}];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Dec 27 2017, after Andrew Howroyd *)
PROG
(PARI) a(n)={if(n<=0, n==0, sum(k=0, (n-1)\2, binomial(n-2*k+2, 2)*binomial(n-k-1, k)))} \\ Andrew Howroyd, Dec 26 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
Gregory L. Simay, Aug 21 2016
EXTENSIONS
More terms from Alois P. Heinz, Aug 29 2016
STATUS
approved