A104854 Number of n-digit numbers using digits 0 to n-1 each exactly once and containing no 3-digit sequence in increasing or decreasing order.

1, 1, 3, 8, 27, 106, 483, 2498, 14487, 93106, 657063, 5051738, 42033747, 376353706, 3608153643, 36879266978, 400339173807, 4599894007906, 55772890550223, 711653491362218, 9532624918010667, 133746250733151706, 1961498898620566803

Offset: 1

Author

Michel Criton (mcriton(AT)wanadoo.fr), Apr 23 2005 and May 29 2005

Keywords

• nonn

Comments

Leading zeros are not allowed, but digits > 9 are permitted.

Derived from A001250: 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042, 707584, 5405530, ... giving 1, 1 and 4-2/2, 10-4/2, 32-10/2, 122-32/2=106, 544-122/2=483, ...

Examples

			The n-digit numbers contributing to the counts are:
n=1: 0;
n=2: 10;
n=3: 102, 120, 201;
n=4: 1032, 1203, 1302, 2031, 2130, 2301, 3021, 3120;
n=5: 10324, 10423, 12043,...,41302, 42301;
G.f.: 1 + x + 3*x^2 + 8*x^3 + 27*x^4 + 106*x^5 + 483*x^6 + 2498*x^7 + ...
		

Links

• D. Berry, J. Broom, D. Dixon, and A. Flaherty, Umbral Calculus and the Boustrophedon Transform, 2013.

Crossrefs

Cf. A000111, A104854, A001250.

Programs

Maple

A001250 := proc(n) local x; if n = 1 then 1; else n!*coeftayl( 2*(tan(x)+sec(x)),x=0,n) ; fi ; end: A104854 := proc(n) if n <= 2 then 1; else A001250(n)-A001250(n-1)/2 ; fi ; end: seq(A104854(n),n=1..30) ; # R. J. Mathar, Feb 14 2008

Mathematica

m = 23;
CoefficientList[1 + (Sec[x] + Tan[x] - 1)(Sec[x] + Tan[x]) + O[x]^m, x]* Range[0, m - 1]! (* Jean-François Alcover, Mar 31 2020 *)

Python

from itertools import accumulate, islice
def A104854_gen(): # generator of terms
    yield 1
    blist = (0,1)
    while True:
        yield -blist[-1]+2*(blist := tuple(accumulate(reversed(blist),initial=0)))[-1]
A104854_list = list(islice(A104854_gen(),40)) # Chai Wah Wu, Jun 14 2022

Formula

For n>2, a(n) = A001250(n) - A001250(n-1)/2 = A001250(n) - A000111(n).

a(n) = 2*A000111(n+1)-A000111(n) [Berry et al., 2013] (but compare A231895). - N. J. A. Sloane, Nov 18 2013

E.g.f: 1+(sec(x)+tan(x)-1)*(sec(x)+tan(x)). - Sergei N. Gladkovskii, Nov 07 2014

Extensions

More terms from R. J. Mathar, Feb 14 2008