A285994 Number of increasing runs in all Carlitz compositions of n.

0, 1, 1, 4, 6, 11, 26, 46, 84, 167, 313, 576, 1086, 2016, 3710, 6876, 12660, 23196, 42542, 77798, 141910, 258648, 470558, 854644, 1550588, 2809620, 5084588, 9192349, 16601714, 29953754, 53997062, 97257129, 175033355, 314771224, 565664138, 1015841191

Offset

0,4

Comments

No two adjacent parts of a Carlitz composition are equal.

Links

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

Formula

a(n) = Sum_{k=0..floor(n/3)} (k+1) * A241701(n,k) for n>0, a(0) = 0.

Example

a(1) = 1: (1).
a(2) = 1: (2).
a(3) = 4: (12), (2)(1), (3).
a(4) = 6: (12)(1), (13), (3)(1), (4).
a(5) = 11: (2)(12), (13)(1), (23), (3)(2), (14), (4)(1), (5).

Maple

b:= proc(n, l) option remember; `if`(n=0, [1, 0], add(`if`(j=l, 0,
      (p-> p+`if`(j>l, [0, p[1]], 0))(b(n-j, j))), j=1..n))
    end:
a:= n-> b(n, 0)[2]:
seq(a(n), n=0..40);

Mathematica

b[n_, l_] := b[n, l] = If[n == 0, {1, 0}, Sum[If[j == l, {0, 0}, Function[p, p + If[j > l, {0, p[[1]]}, 0]][b[n - j, j]]], {j, 1, n}]];
a[n_] := b[n, 0][[2]];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 05 2022, after Alois P. Heinz *)

Crossrefs

Cf. A003242, A241701.

Sequence in context: A219520 A336343 A330459 * A290651 A358913 A066155

Adjacent sequences: A285991 A285992 A285993 * A285995 A285996 A285997

Keyword

nonn

Author

Alois P. Heinz, Apr 30 2017

Status

approved