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