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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A155822 Number of compositions of n with no part greater than 3 such that no two adjacent parts are equal. 1
1, 1, 1, 3, 3, 4, 8, 9, 12, 21, 27, 37, 58, 78, 109, 164, 227, 319, 467, 656, 928, 1341, 1896, 2689, 3859, 5477, 7782, 11126, 15817, 22496, 32103, 45679, 65003, 92668, 131912, 187777, 267556, 380941, 542363, 772581, 1100098, 1566414, 2230997 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

Carlitz compositions with no part greater than 3.

LINKS

D. I. Bevan, Table of n, a(n) for n = 0..5000

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 206.

Index entries for linear recurrences with constant coefficients, signature (1,-1,2,-1,2).

FORMULA

From David Bevan, Feb 02 2009: (Start)

For n>5, a(n) = a(n-1) - a(n-2) + 2*a(n-3) - a(n-4) + 2*a(n-5).

For n>6, a(n) = a(n-3) + a(n-4) + a(n-5) + 2*a(n-6). (End)

G.f.: -(x+1)*(x^2-x+1)*(x^2+1) / (2*x^5-x^4+2*x^3-x^2+x-1). - Colin Barker, Feb 13 2013

G.f.: 1/(1 - Sum_{j=1..3} x^j/(1 + x^j) ) and generally for Carlitz compositions with no part greater than r the o.g.f. is 1/(1 - Sum_{j=1..r} x^j/(1 + x^j) ). - Geoffrey Critzer, Nov 21 2013

EXAMPLE

a(5) = 4 because we have 5 = 1 + 3 + 1 = 2 + 1 + 2 = 2 + 3 = 3+2.

MAPLE

From David Bevan, Feb 02 2009: (Start)

a := proc(k) if k=0 then 1 else b(1, k)+b(2, k)+b(3, k) fi end;

b := proc(r, k) option remember; if k<r then 0 elif k=r then 1 else b(1, k-r)+b(2, k-r)+b(3, k-r)-b(r, k-r) fi end; (End)

MATHEMATICA

nn=20; CoefficientList[Series[1/(1-Sum[z^j/(1+z^j), {j, 1, 3}]), {z, 0, nn}], z] (* Geoffrey Critzer, Nov 21 2013 *)

CROSSREFS

Cf. A000073, A003242.

Sequence in context: A137417 A137418 A285445 * A160646 A019466 A111573

Adjacent sequences:  A155819 A155820 A155821 * A155823 A155824 A155825

KEYWORD

nonn,easy

AUTHOR

David Bevan, Jan 28 2009

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 September 22 00:25 EDT 2017. Contains 292326 sequences.