A207819
Number of permutations of [n] with a fixed point and/or a succession.
Original entry on oeis.org
0, 1, 1, 6, 20, 106, 618, 4358, 34836, 313592, 3135988, 34498646, 414007634, 5382362086, 75356174332, 1130382058576, 18086649408624, 307480839465174, 5534775895914982, 105162728081809146, 2103289132221173216, 44169707042511725964, 971745847021319655464, 22350404337704558809666, 536415027665581568375190, 13410494347081333360291850
Offset: 0
For n=4 the only permutations that do not count are 2143, 2413, 3142 and 4321, so a(4) = 4!-4 = 20.
-
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] = n! - F[Range[n]]; Print[n, " ", a[n]]; a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 05 2019, using Robert Israel's code for A209322 *)
-
A207819(n)={my(p,c);sum(k=1,n!,p=numtoperm(n,k);(c=(p[1]==1)) || for(j=2,n,p[j]!=j & p[j]-1!=p[j-1] & next; c++; break);c)} \\ 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.
A209326
Number of permutations of [n] with a fixed point but no succession.
Original entry on oeis.org
0, 1, 0, 3, 7, 39, 207, 1437, 11203, 99041, 975645, 10601377, 125905445, 1622349059, 22539777113, 335845307359, 5341990288103, 90340567900583, 1618553943500599, 30623660893656205, 610152486797080443, 12769086757046132625, 280037186109883699885, 6422309829486480886809, 153727262708736577446741, 3833789797689152809143363
Offset: 0
For n=4 we have 1324, 1432, 2431, 3214, 3241, 4132 and 4213.
A201452
Number of permutations of [n] with both a fixed point and a succession.
Original entry on oeis.org
0, 0, 1, 1, 8, 37, 248, 1749, 14284, 130343, 1318194, 14630853, 176881314, 2313878809, 32567413038, 490762544907, 7883735348152, 134496767915753, 2428518101193448, 46270707955530689, 927734890186657436
Offset: 0
a(4) = 8 because we have 1234, 1243, 1342, 1423, 2134, 2314, 3124 and 4231.
-
A201452(n)=my(p,c);sum(k=1,n!,p=numtoperm(n,k);c=(p[1]==1);for(j=2,n,p[j]==j&c!=1&c++==3&break;p[j]-1==p[j-1]&c!=2&(c+=2)==3&break);c==3) \\ - M. F. Hasler, Jan 13 2013
A209256
Number of permutations of [n] that contain at least two fixed points in a succession.
Original entry on oeis.org
0, 0, 1, 1, 4, 18, 93, 579, 4165, 34031, 311528, 3158978, 35154907, 426029455, 5585287179, 78767551059, 1189090451364, 19133023344034, 326894939779865, 5910529926220115, 112753567098061553, 2263304875358959543, 47687055915645538384, 1052290471481700378570
Offset: 0
For n=4 we have 1234, 1243, 4231 and 2134 so a(4) = 4.
-
a:= proc(n) option remember; `if`(n<6, [0, 0, 1, 1, 4, 18][n+1],
((2*n^3-43-17*n^2+47*n) *a(n-1)
-(n-2)*(n^3-13*n^2+50*n-59) *a(n-2)
-(n-3)*(3*n^3-28*n^2+82*n-78) *a(n-3)
+(-219*n^2-4*n^4+49*n^3-305+425*n) *a(n-4)
-(n-4)*(3*n^3-25*n^2+66*n-57) *a(n-5)
-(n-4)*(n-5)*(n-2)^2 *a(n-6)) / (n-3)^2)
end:
seq(a(n), n=0..25); # Alois P. Heinz, Jan 15 2013
-
a[n_] := a[n] = If[n<6, {0, 0, 1, 1, 4, 18}[[n+1]],
((2n^3 - 43 - 17n^2 + 47n) a[n-1]
-(n-2)(n^3 - 13n^2 + 50n - 59) a[n-2]
-(n-3)(3n^3 - 28n^2 + 82n - 78) a[n-3]
+(-219n^2 - 4n^4 + 49n^3 - 305 + 425n) a[n-4]
-(n-4)(3n^3 - 25n^2 + 66n - 57) a[n-5]
-(n-4)(n-5)(n-2)^2 a[n-6])/(n-3)^2];
a /@ Range[0, 25] (* Jean-François Alcover, Mar 15 2021, after Alois P. Heinz *)
Showing 1-6 of 6 results.
Comments