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

Author

Alois P. Heinz, Apr 30 2017

Keywords

• nonn

Comments

No two adjacent parts of a Carlitz composition are equal.

Examples

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

Links

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

Crossrefs

Cf. A003242, A241701.

Programs

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

Formula

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