A207821 Number of permutations of [n] that either have a fixed point or a succession, but not both.

0, 1, 0, 5, 12, 69, 370, 2609, 20552, 183249, 1817794, 19867793, 237126320, 3068483277, 42788761294, 639619513669, 10202914060472, 172984071549421, 3106257794721534, 58892020126278457, 1175554242034515780, 24643158882899363129, 541279064964716455230, 12431122899361840993737, 297944099946417376956220, 7439329384072966947792437

Offset: 0

Author

Jon Perry, Jan 10 2013

Keywords

• nonn

Comments

A succession of a permutation p is the appearance of [k,k+1], e.g. in 23541, 23 is a succession.

Examples

			a(4) = 12 because we have 1324, 1432, 2341, 2431, 3214, 3241, 3412, 3421, 4123, 4132, 4213 and 4312.
		

Links

• Max Alekseyev, Table of n, a(n) for n = 0..30

Crossrefs

Cf. A000166, A002467, A180191, A201452, A207819.

Programs

PARI

A207821(n)=my(p,c);sum(k=1,n!,p=numtoperm(n,k);c=(p[1]==1);for(j=2,n,p[j]==j & c<=0 & !c++ & break; p[j]-1==p[j-1] & c>=0 & !c-- & break); c!=0) \\ M. F. Hasler, Jan 13 2013

Formula

a(n) = A209325(n) + A209326(n) = A000166(n) + A000255(n-1) - 2*A209322(n) = 2*A207819(n) - A180191(n) - A002467(n). - Max Alekseyev, Apr 03 2025

Extensions

Values a(1) to a(10) double-checked by M. F. Hasler, Jan 13 2013

Inserted a(0) and a(11)-a(13) from Alois P. Heinz, Jan 18 2013

a(14)-a(20) from Alois P. Heinz, Jul 05 2021

Terms a(21) onward from Max Alekseyev, Apr 03 2025