

A038718


Number of permutations P of {1,2,...,n} such that P(1)=1 and P^1(i+1)P^1(i) equals 1 or 2 for i=1,2,...,n1.


19



1, 1, 2, 4, 6, 9, 14, 21, 31, 46, 68, 100, 147, 216, 317, 465, 682, 1000, 1466, 2149, 3150, 4617, 6767, 9918, 14536, 21304, 31223, 45760, 67065, 98289, 144050, 211116, 309406, 453457, 664574, 973981, 1427439, 2092014, 3065996, 4493436, 6585451
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

This sequence is the number of digits of each term of A061583. [From Dmitry Kamenetsky, Jan 17 2009]


LINKS

Table of n, a(n) for n=1..41.
Index entries for linear recurrences with constant coefficients, signature (2, 1, 1, 1).


FORMULA

G.f.: (x^2x+1)/(x^4x^3+x^22x+1). a(n) = a(n1) + a(n3) + 1.  Joseph Myers, Feb 03 2004
a(n) = sum_{i=1..n} A058278(i) = A097333(n)1. [From R. J. Mathar, Oct 16 2010]


MATHEMATICA

Join[{a=1, b=1, c=2}, Table[d=a+c+1; a=b; b=c; c=d, {n, 100}]] (* Vladimir Joseph Stephan Orlovsky, Feb 26 2011*)
LinearRecurrence[{2, 1, 1, 1}, {1, 1, 2, 4}, 50] (* or *) CoefficientList[ Series[(x^2x+1)/(x^4x^3+x^22x+1), {x, 0, 50}], x] (* Harvey P. Dale, Apr 24 2011 *)


CROSSREFS

Cf. A003274.
Cf. A003410.
Sequence in context: A097197 A260600 A119737 * A042942 A256968 A005687
Adjacent sequences: A038715 A038716 A038717 * A038719 A038720 A038721


KEYWORD

nonn


AUTHOR

John W. Layman, May 02 2000


EXTENSIONS

More terms from Joseph Myers, Feb 03 2004


STATUS

approved



