A383751 Number of Carlitz compositions of n with parts in standard order.
1, 1, 0, 1, 1, 0, 2, 3, 2, 5, 8, 10, 19, 31, 44, 73, 123, 193, 315, 524, 847, 1392, 2317, 3810, 6303, 10506, 17451, 29066, 48603, 81223, 135965, 228153, 383014, 643756, 1083693, 1825640, 3078574, 5197246, 8780823, 14847669, 25128385, 42558687, 72131730, 122343844
Offset: 0
Examples
a(9) = 5 counts: (1,2,1,2,1,2), (1,2,1,2,3), (1,2,1,3,2), (1,2,3,1,2), (1,2,3,2,1).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..4135
Crossrefs
Programs
-
Maple
b:= proc(n, l, i) option remember; `if`(n=0, 1, add( `if`(j=l, 0, b(n-j, j, max(i, j))), j=1..min(n, i+1))) end: a:= n-> b(n, 0$2): seq(a(n), n=0..43); # Alois P. Heinz, May 09 2025
-
PARI
G(k,N) = {my(x='x+O('x^N)); if(k<1,1, G(k-1,N) * x^k * (1 + (1/(1 - sum(j=1,k, x^j/(1+x^j)))) * sum(j=1,k-1, x^j/(1+x^j))))} A_x(N) = {my(x='x+O('x^N)); Vec(sum(i=0,N/2+1, G(i,N+1)))} A_x(50)
Formula
G.f.: Sum_{i>=0} G(i) where G(k) = G(k-1) * x*k * (1 + 1/(1 - Sum_{j=1..k} ( x^j/(1+x^j) )) * Sum_{j=1..k-1} ( x^j/(1+x^j) )) and G(0) = 1.
Comments