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
Keywords
Examples
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}.
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.
Programs
-
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 *) -
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 */
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)))).
Extensions
Added more terms, Joerg Arndt, Apr 28 2013
Comments