%I #22 May 21 2021 04:17:02

%S 0,0,0,0,1,4,10,28,68,159,350,770,1642,3468,7218,14870,30463,62044,

%T 125818,254302,512690,1031284,2071858,4157214,8334742,16699103,

%U 33442208,66947772,133986940,268107104,536404872,1073082978,2146555516,4293665006,8588112822

%N Number of compositions of n with at least one non-contiguous value.

%C Also the number of compositions of n matching the pattern (1,2,1) or (2,1,2).

%F a(n) = A011782(n) - A274174(n). - _Alois P. Heinz_, Jul 09 2020

%e The a(4) = 1 through a(6) = 10 compositions:

%e (121) (131) (141)

%e (212) (1131)

%e (1121) (1212)

%e (1211) (1221)

%e (1311)

%e (2112)

%e (2121)

%e (11121)

%e (11211)

%e (12111)

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

%p add(b(n-i*j, i-1, p+`if`(j=0, 0, 1)), j=0..n/i)))

%p end:

%p a:= n-> ceil(2^(n-1))-b(n$2, 0):

%p seq(a(n), n=0..50); # _Alois P. Heinz_, Jul 09 2020

%t Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[Split[#]]>Length[Union[#]]&]],{n,0,10}]

%t (* Second program: *)

%t b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i<1, 0,

%t Sum[b[n-i*j, i-1, p + If[j == 0, 0, 1]], {j, 0, n/i}]]];

%t a[n_] := Ceiling[2^(n-1)] - b[n, n, 0];

%t a /@ Range[0, 50] (* _Jean-François Alcover_, May 21 2021, after _Alois P. Heinz_ *)

%Y The complement is A274174.

%Y The version for prime indices is A335460.

%Y Anti-run compositions are A003242.

%Y (1,2,1) and (2,1,2)-matching permutations of prime indices are A335462.

%Y (1,2,1)-matching compositions are A335470.

%Y (1,2,1)-avoiding compositions are A335471.

%Y (2,1,2)-matching compositions are A335472.

%Y (2,1,2)-avoiding compositions are A335473.

%Y Cf. A000670, A001339, A011782, A131044, A261983, A333175, A335451, A335460, A335463.

%K nonn

%O 0,6

%A _Gus Wiseman_, Jul 08 2020

%E More terms from _Alois P. Heinz_, Jul 09 2020