|
|
A003242
|
|
Number of compositions of n such that no two adjacent parts are equal (Carlitz compositions).
|
|
349
|
|
|
1, 1, 1, 3, 4, 7, 14, 23, 39, 71, 124, 214, 378, 661, 1152, 2024, 3542, 6189, 10843, 18978, 33202, 58130, 101742, 178045, 311648, 545470, 954658, 1670919, 2924536, 5118559, 8958772, 15680073, 27443763, 48033284, 84069952, 147142465, 257534928, 450748483, 788918212
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
REFERENCES
|
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 191.
|
|
LINKS
|
F. Harary & R. W. Robinson, The number of achiral trees, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)
A. Knopfmacher and H. Prodinger, On Carlitz compositions, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.
|
|
FORMULA
|
G.f.: 1/(1 - Sum_{k>0} x^k/(1+x^k)).
a(n) ~ c r^n where c is approximately 0.456387 and r is approximately 1.750243. (Formula from Knopfmacher and Prodinger reference.) - Franklin T. Adams-Watters, May 27 2010. With better precision: r = 1.7502412917183090312497386246398158787782058181381590561316586... (see A241902), c = 0.4563634740588133495321001859298593318027266156100046548066205... - Vaclav Kotesovec, Apr 30 2014
G.f. is the special case p=2 of 1/(1 - Sum_{k>0} (z^k/(1-z^k) - p*z^(k*p)/(1-z^(k*p)))), see A129922. - Joerg Arndt, Apr 28 2013
G.f.: 1/(1 - x * (d/dx) log(Product_{k>=1} (1 + x^k)^(1/k))). - Ilya Gutkovskiy, Oct 18 2018
|
|
EXAMPLE
|
The 23 such compositions of n=7 are
[ 1] 1 2 1 2 1
[ 2] 1 2 1 3
[ 3] 1 2 3 1
[ 4] 1 2 4
[ 5] 1 3 1 2
[ 6] 1 3 2 1
[ 7] 1 4 2
[ 8] 1 5 1
[ 9] 1 6
[10] 2 1 3 1
[11] 2 1 4
[12] 2 3 2
[13] 2 4 1
[14] 2 5
[15] 3 1 2 1
[16] 3 1 3
[17] 3 4
[18] 4 1 2
[19] 4 2 1
[20] 4 3
[21] 5 2
[22] 6 1
[23] 7
(End)
|
|
MAPLE
|
b:= proc(n, i) option remember; `if`(n=0, 1,
add(`if`(j=i, 0, b(n-j, `if`(j<=n-j, j, 0))), j=1..n))
end:
a:= n-> b(n, 0):
|
|
MATHEMATICA
|
A048272[n_] := Total[If[OddQ[#], 1, -1]& /@ Divisors[n]]; a[n_] := a[n] = Sum[A048272[k]*a[n-k], {k, 1, n}]; a[0] = 1; Table[a[n], {n, 0, 38}](* Jean-François Alcover, Nov 25 2011, after Vladeta Jovovic *)
nmax = 50; CoefficientList[Series[1/(1 - Sum[x^k/(1 + x^k), {k, 1, nmax}]), {x, 0, nmax}], x] (* Vaclav Kotesovec, Jul 07 2020 *)
|
|
PROG
|
(PARI) N = 66; x = 'x + O('x^N); p=2;
gf = 1/(1-sum(k=1, N, x^k/(1-x^k)-p*x^(k*p)/(1-x^(k*p))));
(Haskell)
a003242 n = a003242_list !! n
a003242_list = 1 : f [1] where
f xs = y : f (y : xs) where
y = sum $ zipWith (*) xs a048272_list
|
|
CROSSREFS
|
Compositions with adjacent parts coprime are A167606.
The complement is counted by A261983.
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
E. Rodney Canfield
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|