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

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2017 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

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

LINKS

Christian G. Bower and Alois P. Heinz, Table of n, a(n) for n = 0..4100 (first 501 terms from Christian G. Bower)

L. Carlitz, Restricted Compositions, Fibonacci Quarterly, 14 (1976) 254-264.

Sylvie Corteel, Paweł Hitczenko, Generalizations of Carlitz Compositions, Journal of Integer Sequences, Vol. 10 (2007), Article 07.8.8

Steven R. Finch, Errata and Addenda to Mathematical Constants, p. 42 and 117.

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 201

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.

E. Munarini, M. Poneti, S. Rinaldi, Matrix compositions, JIS 12 (2009) 09.4.8, Chapter 8.

FORMULA

a(n) = Sum_{k=1..n} A048272(k)*a(n-k), n>1, a(0)=1. - Vladeta Jovovic, Feb 05 2002

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

From Joerg Arndt, Oct 27 2012:  (Start)

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):

seq(a(n), n=0..50);  # Alois P. Heinz, Mar 27 2014

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

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))));

Vec(gf)  /* Joerg Arndt, Apr 28 2013 */

(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

-- Reinhard Zumkeller, Nov 04 2015

CROSSREFS

Cf. A106351, A114900, A114902.

Cf. A096568, A011782, A106356. - Franklin T. Adams-Watters, May 27 2010

Row sums of A232396, A241701.

Cf. A241902.

Column k=1 of A261960.

Cf. A048272.

Sequence in context: A041002 A062203 A095063 * A073728 A132753 A132407

Adjacent sequences:  A003239 A003240 A003241 * A003243 A003244 A003245

KEYWORD

nonn,nice

AUTHOR

erc(AT)pollux.cs.uga.edu (E Rodney Canfield)

EXTENSIONS

More terms from David W. Wilson

STATUS

approved

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 December 10 03:07 EST 2018. Contains 318044 sequences. (Running on oeis4.)