cp's OEIS Frontend

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

%I A335548 #22 May 21 2021 04:17:02
%S A335548 0,0,0,0,1,4,10,28,68,159,350,770,1642,3468,7218,14870,30463,62044,
%T A335548 125818,254302,512690,1031284,2071858,4157214,8334742,16699103,
%U A335548 33442208,66947772,133986940,268107104,536404872,1073082978,2146555516,4293665006,8588112822
%N A335548 Number of compositions of n with at least one non-contiguous value.
%C A335548 Also the number of compositions of n matching the pattern (1,2,1) or (2,1,2).
%F A335548 a(n) = A011782(n) - A274174(n). - _Alois P. Heinz_, Jul 09 2020
%e A335548 The a(4) = 1 through a(6) = 10 compositions:
%e A335548   (121)  (131)   (141)
%e A335548          (212)   (1131)
%e A335548          (1121)  (1212)
%e A335548          (1211)  (1221)
%e A335548                  (1311)
%e A335548                  (2112)
%e A335548                  (2121)
%e A335548                  (11121)
%e A335548                  (11211)
%e A335548                  (12111)
%p A335548 b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
%p A335548        add(b(n-i*j, i-1, p+`if`(j=0, 0, 1)), j=0..n/i)))
%p A335548     end:
%p A335548 a:= n-> ceil(2^(n-1))-b(n$2, 0):
%p A335548 seq(a(n), n=0..50);  # _Alois P. Heinz_, Jul 09 2020
%t A335548 Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[Split[#]]>Length[Union[#]]&]],{n,0,10}]
%t A335548 (* Second program: *)
%t A335548 b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i<1, 0,
%t A335548      Sum[b[n-i*j, i-1, p + If[j == 0, 0, 1]], {j, 0, n/i}]]];
%t A335548 a[n_] := Ceiling[2^(n-1)] - b[n, n, 0];
%t A335548 a /@ Range[0, 50] (* _Jean-François Alcover_, May 21 2021, after _Alois P. Heinz_ *)
%Y A335548 The complement is A274174.
%Y A335548 The version for prime indices is A335460.
%Y A335548 Anti-run compositions are A003242.
%Y A335548 (1,2,1) and (2,1,2)-matching permutations of prime indices are A335462.
%Y A335548 (1,2,1)-matching compositions are A335470.
%Y A335548 (1,2,1)-avoiding compositions are A335471.
%Y A335548 (2,1,2)-matching compositions are A335472.
%Y A335548 (2,1,2)-avoiding compositions are A335473.
%Y A335548 Cf. A000670, A001339, A011782, A131044, A261983, A333175, A335451, A335460, A335463.
%K A335548 nonn
%O A335548 0,6
%A A335548 _Gus Wiseman_, Jul 08 2020
%E A335548 More terms from _Alois P. Heinz_, Jul 09 2020