%I #18 Nov 10 2020 12:35:59
%S 1,1,3,4,12,22,51,101,225,465,1008,2111,4528,9560,20402,43222,92018,
%T 195256,415243,881758,1874288,3981318,8460906,17975132,38196045,
%U 81152769,172436680,366376845,778476016,1654054258,3514494256,7467412436,15866507485,33712418692,71630875356,152198161794
%N Number of 3-Carlitz compositions of n (or, more generally p-Carlitz compositions, p > 1), i.e., words b_1^{i_1}b_2^{i_2}...b_k^{i_k} such that the b_j's and i_j's are positive integers for which Sum_{j=1..k} i_j * b_j = n and, for all j, i_j < p and if b_j = b_(j+1) then i_j + i_(j+1) is not equal to p.
%C For p=2, the sequence enumerates Carlitz compositions, A003242.
%H Alois P. Heinz, <a href="/A129922/b129922.txt">Table of n, a(n) for n = 0..1000</a>
%H Sylvie Corteel and Paweł Hitczenko, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL10/Hitczenko/hitczenko4.html">Generalizations of Carlitz Compositions</a>, Journal of Integer Sequences, Vol. 10 (2007), Article 07.8.8.
%F G.f.: 1/(1 - Sum_{k>0} (z^k/(1-z^k) - 3*z^(k*3)/(1-z^(k*3)))).
%F For general p the generating function is 1/(1 - Sum_{k>0}(z^k/(1-z^k) - p*z^(k*p)/(1-z^(k*p)))).
%e a(3)=4 because, for p=3, we can write:
%e 3^{1},
%e 1^{1} 2^{1},
%e 2^{1} 1^{1},
%e 1^{1} 1^{1} 1^{1}.
%p b:= proc(n, i, j) option remember;
%p `if`(n=0, 1, add(add(`if`(k=i and m+j=3, 0,
%p b(n-k*m, k, m)), m=1..min(2, n/k)), k=1..n))
%p end:
%p a:= n-> b(n, 0$2):
%p seq(a(n), n=0..40); # _Alois P. Heinz_, Jul 22 2017
%t b[n_, i_, j_] := b[n, i, j] = If[n == 0, 1, Sum[Sum[If[k == i && m + j == 3, 0, b[n - k m, k, m]], {m, 1, Min[2, n/k]}], {k, 1, n}]];
%t a[n_] := b[n, 0, 0];
%t a /@ Range[0, 40] (* _Jean-François Alcover_, Nov 10 2020, after _Alois P. Heinz_ *)
%o (PARI) N = 66; x = 'x + O('x^N); p=3;
%o gf = 1/(1-sum(k=1,N, x^k/(1-x^k)-p*x^(k*p)/(1-x^(k*p))));
%o Vec(gf) /* _Joerg Arndt_, Apr 28 2013 */
%Y Cf. A129921.
%Y Cf. A003242.
%K nonn
%O 0,3
%A Pawel Hitczenko (phitczenko(AT)math.drexel.edu), Jun 05 2007
%E Added more terms, _Joerg Arndt_, Apr 28 2013