|
%I #120 Oct 27 2023 18:27:45
%S 1,1,1,3,4,7,14,23,39,71,124,214,378,661,1152,2024,3542,6189,10843,
%T 18978,33202,58130,101742,178045,311648,545470,954658,1670919,2924536,
%U 5118559,8958772,15680073,27443763,48033284,84069952,147142465,257534928,450748483,788918212
%N Number of compositions of n such that no two adjacent parts are equal (Carlitz compositions).
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 191.
%H Alois P. Heinz, <a href="/A003242/b003242.txt">Table of n, a(n) for n = 0..4100</a> (first 501 terms from Christian G. Bower)
%H L. Carlitz, <a href="http://www.fq.math.ca/Scanned/14-3/carlitz2.pdf">Restricted Compositions</a>, Fibonacci Quarterly, 14 (1976) 254-264.
%H Sylvie Corteel, 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
%H Steven R. Finch, <a href="http://arxiv.org/abs/2001.00578">Errata and Addenda to Mathematical Constants</a>, arXiv:2001.00578 [math.HO], 2020-2022, p. 42 and 117.
%H P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 201
%H F. Harary & R. W. Robinson, <a href="/A000108/a000108_18.pdf">The number of achiral trees</a>, Jnl. Reine Angewandte Mathematik 278 (1975), 322-335. (Annotated scanned copy)
%H A. Knopfmacher and H. Prodinger, <a href="http://dx.doi.org/10.1006/eujc.1998.0216">On Carlitz compositions</a>, European Journal of Combinatorics, Vol. 19, 1998, pp. 579-589.
%H E. Munarini, M. Poneti, S. Rinaldi, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Rinaldi/rinaldi.html">Matrix compositions</a>, JIS 12 (2009) 09.4.8, Chapter 8.
%F a(n) = Sum_{k=1..n} A048272(k)*a(n-k), n>1, a(0)=1. - _Vladeta Jovovic_, Feb 05 2002
%F G.f.: 1/(1 - Sum_{k>0} x^k/(1+x^k)).
%F 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
%F 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
%F G.f.: 1/(1 - x * (d/dx) log(Product_{k>=1} (1 + x^k)^(1/k))). - _Ilya Gutkovskiy_, Oct 18 2018
%F Moebius transform of A329738. - _Gus Wiseman_, Nov 27 2019
%F For n>=2, a(n) = A128695(n) - A091616(n). - _Vaclav Kotesovec_, Jul 07 2020
%e From _Joerg Arndt_, Oct 27 2012: (Start)
%e The 23 such compositions of n=7 are
%e [ 1] 1 2 1 2 1
%e [ 2] 1 2 1 3
%e [ 3] 1 2 3 1
%e [ 4] 1 2 4
%e [ 5] 1 3 1 2
%e [ 6] 1 3 2 1
%e [ 7] 1 4 2
%e [ 8] 1 5 1
%e [ 9] 1 6
%e [10] 2 1 3 1
%e [11] 2 1 4
%e [12] 2 3 2
%e [13] 2 4 1
%e [14] 2 5
%e [15] 3 1 2 1
%e [16] 3 1 3
%e [17] 3 4
%e [18] 4 1 2
%e [19] 4 2 1
%e [20] 4 3
%e [21] 5 2
%e [22] 6 1
%e [23] 7
%e (End)
%p b:= proc(n, i) option remember; `if`(n=0, 1,
%p add(`if`(j=i, 0, b(n-j, `if`(j<=n-j, j, 0))), j=1..n))
%p end:
%p a:= n-> b(n, 0):
%p seq(a(n), n=0..50); # _Alois P. Heinz_, Mar 27 2014
%t 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_ *)
%t nmax = 50; CoefficientList[Series[1/(1 - Sum[x^k/(1 + x^k), {k, 1, nmax}]), {x, 0, nmax}], x] (* _Vaclav Kotesovec_, Jul 07 2020 *)
%o (PARI) N = 66; x = 'x + O('x^N); p=2;
%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 */
%o (Haskell)
%o a003242 n = a003242_list !! n
%o a003242_list = 1 : f [1] where
%o f xs = y : f (y : xs) where
%o y = sum $ zipWith (*) xs a048272_list
%o -- _Reinhard Zumkeller_, Nov 04 2015
%Y Cf. A106351, A114900, A114902.
%Y Cf. A096568, A011782, A106356. - _Franklin T. Adams-Watters_, May 27 2010
%Y Row sums of A232396, A241701.
%Y Cf. A241902.
%Y Column k=1 of A261960.
%Y Cf. A048272.
%Y Compositions with adjacent parts coprime are A167606.
%Y The complement is counted by A261983.
%Y Cf. A000740, A005251, A032020, A114901, A178470, A261041, A274174, A329738, A329863.
%K nonn,nice
%O 0,4
%A E. Rodney Canfield
%E More terms from _David W. Wilson_
|
