A207821
Number of permutations of [n] that either have a fixed point or a succession, but not both.
Original entry on oeis.org
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
a(4) = 12 because we have 1324, 1432, 2341, 2431, 3214, 3241, 3412, 3421, 4123, 4132, 4213 and 4312.
-
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
Values a(1) to a(10) double-checked by
M. F. Hasler, Jan 13 2013
A209322
Number of derangements of [n] with no succession.
Original entry on oeis.org
1, 0, 1, 0, 4, 14, 102, 682, 5484, 49288, 492812, 5418154, 64993966, 844658714, 11822116868, 177292309424, 2836140479376, 48206588630826, 867597809813018, 16482372327022854, 329612875955466784, 6921235129197714036, 152254880756288024536, 3501612401180417830334, 84033374067657870984810, 2100715696249652623708150
Offset: 0
For n=4 we have 2143, 2413, 3142 and 4321, so a(4) = 4.
-
F:= proc(S) add(G(S minus {s}, s-1), s = S minus {nops(S)}) end proc:
G:= proc(S,t) option remember;
if S = {} then return 1 fi;
add(procname(S minus {s},s-1), s = S minus {t, nops(S)})
end proc:
1,seq(F({$1..n}), n=1..19); # Robert Israel, Mar 02 2017
-
F[{}] = 1; F[S_] := Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {Length[S]}}];
G[{}, ] = 1; G[S, t_] := G[S, t] = Sum[G[S ~Complement~ {s}, s-1], {s, S ~Complement~ {t, Length[S]}}];
Table[a[n] = F[Range[n]]; Print[n, " ", a[n]]; a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 05 2019, after Robert Israel *)
-
{ a209322(n) = if(n==0, return(1)); my(A=matrix(n, n, i, j, i-j!=1 && i!=j)); parsum(s=1, 2^n-1, my(M=vecextract(A, s, s), d=matsize(M)[1], v=vectorv(d, i, 1), pos=bitand(s, 1)); if(pos, v[1]=0); for(k=1, n-1, v=M*v; if(bitand(s>>k, 1), v[pos++]=0)); (-1)^(n-d)*vecsum(v) ); } \\ Max Alekseyev, Apr 03 2025
A209325
Number of permutations of [n] with a succession but no fixed points.
Original entry on oeis.org
0, 0, 0, 2, 5, 30, 163, 1172, 9349, 84208, 842149, 9266416, 111220875, 1446134218, 20248984181, 303774206310, 4860923772369, 82643503648838, 1487703851220935, 28268359232622252, 565401755237435337, 11874072125853230504, 261241878854832755345, 6008813069875360106928, 144216837237680799509479, 3605539586383814138649074
Offset: 0
For n=4 we have 2341, 3412, 3421, 4123 and 4312.
Showing 1-3 of 3 results.
Comments