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, 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

Links

Table of n, a(n) for n=0..34.

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

Cf. A000045, A029907, A239242.

Sequence in context: A281283 A281638 A281100 * A123247 A212444 A112306

Adjacent sequences: A276126 A276127 A276128 * A276130 A276131 A276132

Keyword

nonn

Author

Gregory L. Simay, Aug 21 2016

Extensions

More terms from Alois P. Heinz, Aug 29 2016

Status

approved