A293579 - OEIS

%I #11 Oct 14 2017 09:26:31

%S 3,16,66,248,892,3136,10888,37536,128880,441472,1510176,5161856,

%T 17635264,60233728,205697152,702386688,2398283520,8188622848,

%U 27958448640,95457597440,325915589632,1112751357952,3799182641152,12971244625920,44286646775808,151204164960256

%N 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.

%H Alois P. Heinz, <a href="/A293579/b293579.txt">Table of n, a(n) for n = 2..1000</a>

%F From _Vaclav Kotesovec_, Oct 14 2017: (Start)

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

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

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

%F (End)

%p b:= proc(n, k) option remember; `if`(n=0, 1,

%p       add(b(n-j, k)*binomial(j+k-1, k-1), j=1..n))

%p     end:

%p a:= n-> (k->add(b(n, k-i)*(-1)^i*binomial(k, i), i=0..k))(2):

%p seq(a(n), n=2..30);

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

%Y Column k=2 of A261781.

%K nonn

%O 2,1

%A _Alois P. Heinz_, Oct 12 2017