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,3

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

Links

Table of n, a(n) for n=1..23.

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

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

Example

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

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

Prog

(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

Crossrefs

Cf. A000111, A104854, A001250.

Sequence in context: A102206 A192856 A110886 * A226061 A294197 A030495

Adjacent sequences: A104851 A104852 A104853 * A104855 A104856 A104857

Keyword

nonn

Author

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

Extensions

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

Status

approved