A240506 Number of length-n gap-free words on {1,2,3}.

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, 2541798719467, 7625463267261

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

Prog

(PARI) a(n)=if(n, 3^n-2^n+2, 1) \\ Charles R Greathouse IV, May 31 2026

Crossrefs

Sequence in context: A130380 A097147 A148677 * A037127 A105795 A394441

Adjacent sequences: A240503 A240504 A240505 * A240507 A240508 A240509

Keyword

nonn,easy

Author

Geoffrey Critzer, Apr 06 2014

Status

approved