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

Author

Alois P. Heinz, Oct 12 2017

Keywords

• nonn

Links

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

Crossrefs

Column k=2 of A261781.

Programs

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

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)