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,6

Comments

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

Links

Table of n, a(n) for n=0..34.

Formula

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

Example

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

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

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.

Sequence in context: A026534 A034920 A274597 * A203293 A111308 A348057

Adjacent sequences: A335545 A335546 A335547 * A335549 A335550 A335551

Keyword

nonn

Author

Gus Wiseman, Jul 08 2020

Extensions

More terms from Alois P. Heinz, Jul 09 2020

Status

approved