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

 

Logo


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). 49
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

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

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified April 24 00:59 EDT 2017. Contains 285338 sequences.