A293579 Number of compositions of n where each part i is marked with a word of length i over a binary alphabet whose letters appear in alphabetical order and both letters occur at least once in the composition.

3, 16, 66, 248, 892, 3136, 10888, 37536, 128880, 441472, 1510176, 5161856, 17635264, 60233728, 205697152, 702386688, 2398283520, 8188622848, 27958448640, 95457597440, 325915589632, 1112751357952, 3799182641152, 12971244625920, 44286646775808, 151204164960256

Offset

2,1

Links

Alois P. Heinz, Table of n, a(n) for n = 2..1000

Formula

From Vaclav Kotesovec, Oct 14 2017: (Start)

a(n) = 6*a(n-1) - 10*a(n-2) + 4*a(n-3).

a(n) ~ 2^(n/2 - 2) * (1+sqrt(2))^(n+1).

a(n) = 2^(n/2 - 2) * ((sqrt(2)+1)^(n+1) - (sqrt(2)-1)^(n+1)) - 2^n.

(End)

Maple

b:= proc(n, k) option remember; `if`(n=0, 1,
      add(b(n-j, k)*binomial(j+k-1, k-1), j=1..n))
    end:
a:= n-> (k->add(b(n, k-i)*(-1)^i*binomial(k, i), i=0..k))(2):
seq(a(n), n=2..30);

Mathematica

Table[Simplify[2^(n/2 - 2)*((Sqrt[2]+1)^(n+1) - (Sqrt[2]-1)^(n+1)) - 2^n], {n, 2, 20}] (* Vaclav Kotesovec, Oct 14 2017 *)

Crossrefs

Column k=2 of A261781.

Sequence in context: A007143 A359176 A062960 * A044046 A179600 A278089

Adjacent sequences: A293576 A293577 A293578 * A293580 A293581 A293582

Keyword

nonn

Author

Alois P. Heinz, Oct 12 2017

Status

approved