A193284 Number of allowed patterns of length n of the map f(x) = 4x(1-x) on the unit interval. A permutation pi is an allowed pattern if there exists x in [0,1] such that the values x,f(x),f(f(x)),...,f^{n-1}(x) are different and in the same relative order as pi_1,pi_2,...,pi_n.

1, 1, 2, 5, 12, 31, 75, 178, 414, 949, 2137, 4767

Offset

0,3

Comments

a(n) is also the number of allowed patterns of length n of the tent map x -> 1-|1-2x| in [0,1].

Links

Table of n, a(n) for n=0..11.

S. Elizalde and Y. Liu, On basic forbidden patterns of functions, Discrete Appl. Math. 159 (2011), 1207-1216.

Formula

a(n) = n! - A193285(n).

Example

a(3) = 5 because the allowed patterns of length 3 are 123, 132, 213, 231, 312.

Crossrefs

Cf. A000142, A193285 (forbidden patterns).

Sequence in context: A261937 A305311 A291239 * A238829 A125023 A129804

Adjacent sequences: A193281 A193282 A193283 * A193285 A193286 A193287

Keyword

nonn,more

Author

Sergi Elizalde, Jul 20 2011

Extensions

a(0)=1 prepended by Alois P. Heinz, Mar 02 2020

Status

approved