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

1, 1, 3, 4, 12, 22, 51, 101, 225, 465, 1008, 2111, 4528, 9560, 20402, 43222, 92018, 195256, 415243, 881758, 1874288, 3981318, 8460906, 17975132, 38196045, 81152769, 172436680, 366376845, 778476016, 1654054258, 3514494256, 7467412436, 15866507485, 33712418692, 71630875356, 152198161794

Offset

0,3

Comments

For p=2, the sequence enumerates Carlitz compositions, A003242.

Links

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

Sylvie Corteel and Paweł Hitczenko, Generalizations of Carlitz Compositions, Journal of Integer Sequences, Vol. 10 (2007), Article 07.8.8.

Formula

G.f.: 1/(1 - Sum_{k>0} (z^k/(1-z^k) - 3*z^(k*3)/(1-z^(k*3)))).

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

Example

a(3)=4 because, for p=3, we can write:
  3^{1},
  1^{1} 2^{1},
  2^{1} 1^{1},
  1^{1} 1^{1} 1^{1}.

Maple

b:= proc(n, i, j) option remember;
     `if`(n=0, 1, add(add(`if`(k=i and m+j=3, 0,
      b(n-k*m, k, m)), m=1..min(2, n/k)), k=1..n))
    end:
a:= n-> b(n, 0$2):
seq(a(n), n=0..40);  # Alois P. Heinz, Jul 22 2017

Mathematica

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}]];
a[n_] := b[n, 0, 0];
a /@ Range[0, 40] (* Jean-François Alcover, Nov 10 2020, after Alois P. Heinz *)

Prog

(PARI) N = 66;  x = 'x + O('x^N);  p=3;
gf = 1/(1-sum(k=1, N, x^k/(1-x^k)-p*x^(k*p)/(1-x^(k*p))));
Vec(gf)  /* Joerg Arndt, Apr 28 2013 */

Crossrefs

Cf. A129921.

Cf. A003242.

Sequence in context: A075220 A075221 A295948 * A005221 A243391 A000206

Adjacent sequences: A129919 A129920 A129921 * A129923 A129924 A129925

Keyword

nonn

Author

Pawel Hitczenko (phitczenko(AT)math.drexel.edu), Jun 05 2007

Extensions

Added more terms, Joerg Arndt, Apr 28 2013

Status

approved