login
A335548
Number of compositions of n with at least one non-contiguous value.
29
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).
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.
Sequence in context: A026534 A034920 A274597 * A203293 A111308 A348057
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jul 08 2020
EXTENSIONS
More terms from Alois P. Heinz, Jul 09 2020
STATUS
approved