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

0, 0, 0, 0, 1, 4, 10, 28, 68, 159, 350, 770, 1642, 3468, 7218, 14870, 30463, 62044, 125818, 254302, 512690, 1031284, 2071858, 4157214, 8334742, 16699103, 33442208, 66947772, 133986940, 268107104, 536404872, 1073082978, 2146555516, 4293665006, 8588112822

Offset: 0

Author

Gus Wiseman, Jul 08 2020

Keywords

• nonn

Comments

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

Examples

			The a(4) = 1 through a(6) = 10 compositions:
  (121)  (131)   (141)
         (212)   (1131)
         (1121)  (1212)
         (1211)  (1221)
                 (1311)
                 (2112)
                 (2121)
                 (11121)
                 (11211)
                 (12111)
		

Crossrefs

The complement is A274174.

The version for prime indices is A335460.

Anti-run compositions are A003242.

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

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

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

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

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

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

Programs

Maple

b:= proc(n, i, p) option remember; `if`(n=0, p!, `if`(i<1, 0,
       add(b(n-i*j, i-1, p+`if`(j=0, 0, 1)), j=0..n/i)))
    end:
a:= n-> ceil(2^(n-1))-b(n$2, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Jul 09 2020

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],Length[Split[#]]>Length[Union[#]]&]],{n,0,10}]
(* Second program: *)
b[n_, i_, p_] := b[n, i, p] = If[n == 0, p!, If[i<1, 0,
     Sum[b[n-i*j, i-1, p + If[j == 0, 0, 1]], {j, 0, n/i}]]];
a[n_] := Ceiling[2^(n-1)] - b[n, n, 0];
a /@ Range[0, 50] (* Jean-François Alcover, May 21 2021, after Alois P. Heinz *)

Formula

a(n) = A011782(n) - A274174(n). - Alois P. Heinz, Jul 09 2020

Extensions

More terms from Alois P. Heinz, Jul 09 2020