login
The OEIS is supported by the many generous donors 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). 349
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
REFERENCES
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 191.
LINKS
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, arXiv:2001.00578 [math.HO], 2020-2022, 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
Moebius transform of A329738. - Gus Wiseman, Nov 27 2019
For n>=2, a(n) = A128695(n) - A091616(n). - Vaclav Kotesovec, Jul 07 2020
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 *)
nmax = 50; CoefficientList[Series[1/(1 - Sum[x^k/(1 + x^k), {k, 1, nmax}]), {x, 0, nmax}], x] (* Vaclav Kotesovec, Jul 07 2020 *)
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
Row sums of A232396, A241701.
Cf. A241902.
Column k=1 of A261960.
Cf. A048272.
Compositions with adjacent parts coprime are A167606.
The complement is counted by A261983.
Sequence in context: A062203 A319548 A095063 * A073728 A132753 A132407
KEYWORD
nonn,nice
AUTHOR
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:34 EDT 2024. Contains 370951 sequences. (Running on oeis4.)