login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A240506 Number of length-n gap-free words on {1,2,3}. 2
1, 3, 7, 21, 67, 213, 667, 2061, 6307, 19173, 58027, 175101, 527347, 1586133, 4766587, 14316141, 42981187, 129009093, 387158347, 1161737181, 3485735827, 10458256053, 31376865307, 94134790221, 282412759267, 847255055013 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

A word is gap-free if it contains all the letters between the smallest and the largest element in the word.

REFERENCES

S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Chapman and Hall, 2009 page 86, Exercise 3.16.

LINKS

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (6,-11,6).

FORMULA

E.g.f.: 1 + Sum_{k=1..3} (3 - k + 1)*(exp(x) - 1)^k. Generally for gap free words on {1,2,...m} the e.g.f. is: 1 + Sum_{k=1..m} (m - k + 1)*(exp(x) - 1)^k.

From Colin Barker, Apr 07 2014 (conjectured): (Start)

a(n) = 2-2^n+3^n for n>0.

a(n) = 6*a(n-1)-11*a(n-2)+6*a(n-3) for n>3.

G.f.: -(6*x^3-3*x+1) / ((x-1)*(2*x-1)*(3*x-1)). (End)

EXAMPLE

a(3)=21 because there are 27 length 3 words on alphabet {1,2,3} but we don't count 113, 131, 133, 311, 313, or 331.

MATHEMATICA

nn=25; Range[0, nn]!CoefficientList[Series[1+Sum[(3-k+1)(Exp[x]-1)^k, {k, 1, 3}], {x, 0, nn}], x]

LinearRecurrence[{6, -11, 6}, {1, 3, 7, 21}, 30] (* Harvey P. Dale, Dec 09 2015 *)

CROSSREFS

Sequence in context: A130380 A097147 A148677 * A037127 A105795 A322459

Adjacent sequences:  A240503 A240504 A240505 * A240507 A240508 A240509

KEYWORD

nonn

AUTHOR

Geoffrey Critzer, Apr 06 2014

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 February 29 09:35 EST 2020. Contains 332355 sequences. (Running on oeis4.)