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

Author

Geoffrey Critzer, Apr 06 2014

Keywords

• nonn

Comments

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

Examples

			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.
		

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

Programs

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

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)