cp's OEIS Frontend

A003242 Number of compositions of n such that no two adjacent parts are equal (these are sometimes called Carlitz compositions).

%I A003242 #126 Jan 05 2025 19:51:33
%S A003242 1,1,1,3,4,7,14,23,39,71,124,214,378,661,1152,2024,3542,6189,10843,
%T A003242 18978,33202,58130,101742,178045,311648,545470,954658,1670919,2924536,
%U A003242 5118559,8958772,15680073,27443763,48033284,84069952,147142465,257534928,450748483,788918212
%N A003242 Number of compositions of n such that no two adjacent parts are equal (these are sometimes called Carlitz compositions).
%D A003242 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 191.
%H A003242 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 A003242 L. Carlitz, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/14-3/carlitz2.pdf">Restricted Compositions</a>, Fibonacci Quarterly, 14 (1976) 254-264.
%H A003242 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 A003242 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 A003242 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 201
%H A003242 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 A003242 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 A003242 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 A003242 a(n) = Sum_{k=1..n} A048272(k)*a(n-k), n>1, a(0)=1. - _Vladeta Jovovic_, Feb 05 2002
%F A003242 G.f.: 1/(1 - Sum_{k>0} x^k/(1+x^k)).
%F A003242 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 A003242 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 A003242 G.f.: 1/(1 - x * (d/dx) log(Product_{k>=1} (1 + x^k)^(1/k))). - _Ilya Gutkovskiy_, Oct 18 2018
%F A003242 Moebius transform of A329738. - _Gus Wiseman_, Nov 27 2019
%F A003242 For n>=2, a(n) = A128695(n) - A091616(n). - _Vaclav Kotesovec_, Jul 07 2020
%e A003242 From _Joerg Arndt_, Oct 27 2012:  (Start)
%e A003242 The 23 such compositions of n=7 are
%e A003242 [ 1]  1 2 1 2 1
%e A003242 [ 2]  1 2 1 3
%e A003242 [ 3]  1 2 3 1
%e A003242 [ 4]  1 2 4
%e A003242 [ 5]  1 3 1 2
%e A003242 [ 6]  1 3 2 1
%e A003242 [ 7]  1 4 2
%e A003242 [ 8]  1 5 1
%e A003242 [ 9]  1 6
%e A003242 [10]  2 1 3 1
%e A003242 [11]  2 1 4
%e A003242 [12]  2 3 2
%e A003242 [13]  2 4 1
%e A003242 [14]  2 5
%e A003242 [15]  3 1 2 1
%e A003242 [16]  3 1 3
%e A003242 [17]  3 4
%e A003242 [18]  4 1 2
%e A003242 [19]  4 2 1
%e A003242 [20]  4 3
%e A003242 [21]  5 2
%e A003242 [22]  6 1
%e A003242 [23]  7
%e A003242 (End)
%p A003242 b:= proc(n, i) option remember; `if`(n=0, 1,
%p A003242       add(`if`(j=i, 0, b(n-j, `if`(j<=n-j, j, 0))), j=1..n))
%p A003242     end:
%p A003242 a:= n-> b(n, 0):
%p A003242 seq(a(n), n=0..50);  # _Alois P. Heinz_, Mar 27 2014
%t A003242 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 A003242 nmax = 50; CoefficientList[Series[1/(1 - Sum[x^k/(1 + x^k), {k, 1, nmax}]), {x, 0, nmax}], x] (* _Vaclav Kotesovec_, Jul 07 2020 *)
%t A003242 Table[Count[Flatten[Permutations/@IntegerPartitions[n],1],_?(FreeQ[Differences[#],0]&)],{n,0,20}] (* The program generates the first 21 terms of the sequence. *) (* _Harvey P. Dale_, Nov 23 2024 *)
%o A003242 (PARI) N = 66;  x = 'x + O('x^N);  p=2;
%o A003242 gf = 1/(1-sum(k=1,N, x^k/(1-x^k)-p*x^(k*p)/(1-x^(k*p))));
%o A003242 Vec(gf)  /* _Joerg Arndt_, Apr 28 2013 */
%o A003242 (Haskell)
%o A003242 a003242 n = a003242_list !! n
%o A003242 a003242_list = 1 : f [1] where
%o A003242    f xs = y : f (y : xs) where
%o A003242           y = sum $ zipWith (*) xs a048272_list
%o A003242 -- _Reinhard Zumkeller_, Nov 04 2015
%Y A003242 Cf. A106351, A114900, A114902.
%Y A003242 Cf. A096568, A011782, A106356. - _Franklin T. Adams-Watters_, May 27 2010
%Y A003242 Row sums of A232396, A241701.
%Y A003242 Cf. A241902.
%Y A003242 Column k=1 of A261960.
%Y A003242 Cf. A048272.
%Y A003242 Compositions with adjacent parts coprime are A167606.
%Y A003242 The complement is counted by A261983.
%Y A003242 Cf. A000740, A005251, A032020, A114901, A178470, A261041, A274174, A329738, A329863.
%K A003242 nonn,nice
%O A003242 0,4
%A A003242 E. Rodney Canfield
%E A003242 More terms from _David W. Wilson_