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
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
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.
A288208
Number of permutations of a sequence of length n such that there are no fixed points, and no term is next to a term it was next to originally.
Original entry on oeis.org
1, 0, 0, 0, 2, 2, 27, 214, 1695, 15482, 159019, 1775664, 21542628, 282722448, 3989526469, 60239477384, 969280731152, 16558273230450, 299319139977198, 5708394302035014, 114547714715532531, 2412649672553637772, 53220018152831892175, 1227013593901474460674, 29512839964990444892407
Offset: 0
For n = 4 the a(4) = 2 solutions are [2,4,1,3] and [3,1,4,2].
For n = 5 the a(5) = 2 solutions are [3,1,5,2,4] and [2,4,1,5,3].
a(6) = 27: 241635, 246135, 246315, 251364, 264135, 314625, 315264, 351624, 351642, 352614, 352641, 361524, 362514, 415263, 415362, 462513, 462531, 514263, 531624, 531642, 536142, 536241, 631524, 635142, 635241, 642513, 642531.
Cf.
A002464 is analogous without the fixed point restriction.
-
pairs l = zip l (drop 1 l)
d n = filter (all (uncurry (/=)) . zip [1..]) $ Data.List.permutations [1..n]
a n = length $ filter (all ((1<) . abs . uncurry (-)) . pairs) $ d n
-
b:= proc(s, l) option remember; (n-> `if`(n=0, 1, add(
`if`(j=n or abs(l-j)<2, 0, b(s minus {j}, j)), j=s)))(nops(s))
end:
a:= n-> b({$1..n}, -1):
seq(a(n), n=0..17); # Alois P. Heinz, Feb 08 2025
-
Clear[permCount]; permCount[s_, last_] := permCount[s, last] = Module[{n, j}, n = Length[s]; If[n == 0, 1, Total[Table[If[j == n || Abs[last - j] < 2, 0, permCount[Complement[s, {j}], j]], {j, s}]]]]; Table[permCount[Range[n], -2], {n, 0, 12}] (* Robert P. P. McKone, Mar 22 2025 *)
-
{ a288208(n) = my(A = matrix(n,n,i,j,abs(i-j)>1)); 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, Feb 08 2025
Showing 1-5 of 5 results.
Comments