A274174 Number of compositions of n if all summand runs are kept together.

1, 1, 2, 4, 7, 12, 22, 36, 60, 97, 162, 254, 406, 628, 974, 1514, 2305, 3492, 5254, 7842, 11598, 17292, 25294, 37090, 53866, 78113, 112224, 161092, 230788, 328352, 466040, 658846, 928132, 1302290, 1821770, 2537156, 3536445, 4897310, 6777806, 9341456, 12858960, 17625970, 24133832, 32910898, 44813228, 60922160, 82569722

Offset

0,3

Comments

a(n^2) is odd. - Gregory L. Simay, Jun 23 2019

Also the number of compositions of n avoiding the patterns (1,2,1) and (2,1,2). - Gus Wiseman, Jul 07 2020

Links

Alois P. Heinz, Table of n, a(n) for n = 0..5000

Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

Formula

a(n) = Sum_{k>=0} k! * A116608(n,k). - Joerg Arndt, Jun 12 2016

Example

If the summand runs are blocked together, there are 22 compositions of a(6): 6; 5+1, 1+5, 4+2, 2+4, (3+3), 4+(1+1), (1+1)+4, 1+2+3, 1+3+2, 2+1+3, 2+3+1, 3+1+2, 3+2+1, (2+2+2), 3+(1+1+1), (1+1+1)+3, (2+2)+(1+1), (1+1)+(2+2), 2+(1+1+1+1), (1+1+1+1)+2, (1+1+1+1+1+1).
a(0)=1; a(1)= 1; a(4) = 7; a(9) = 97; a(16) = 2305; a(25) = 78113 and a(36) = 3536445. - Gregory L. Simay, Jun 23 19

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-> b(n$2, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Jun 12 2016

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], Length[Split[#]]==Length[Union[#]]&]], {n, 0, 10}] (* Gus Wiseman, Jul 07 2020 *)
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_] := b[n, n, 0];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Jul 11 2021, after Alois P. Heinz *)

Crossrefs

Cf. A000070, A101880, A116608.

The version for patterns is A001339.

The version for prime indices is A333175.

The complement (i.e., the matching version) is A335548.

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, A056986, A181796, A335451, A335452, A335460, A335463.

Sequence in context: A054151 A018176 A135460 * A089259 A309733 A289107

Adjacent sequences: A274171 A274172 A274173 * A274175 A274176 A274177

Keyword

nonn

Author

Gregory L. Simay, Jun 12 2016

Extensions

Terms a(9) and beyond from Joerg Arndt, Jun 12 2016

Status

approved