login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003242 Number of compositions of n such that no two adjacent parts are equal (Carlitz compositions). 63

%I

%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 Christian G. Bower and 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="http://www.emis.ams.org/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://www.people.fas.harvard.edu/~sfinch/csolve/erradd.pdf">Errata and Addenda to Mathematical Constants</a>, 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

%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_ *)

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

%K nonn,nice

%O 0,4

%A E. Rodney Canfield

%E More terms from _David W. Wilson_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 16 15:31 EST 2019. Contains 319195 sequences. (Running on oeis4.)