| Displaying 1-8 of 8 results found.
page
1
1, 2, 6, 24, 114, 674, 4714, 37754, 340404, 3412176, 37631268
Number of circular permutations of length n without consecutive triples i,i+2,i+4.
+10
8
1, 1, 1, 2, 6, 22, 109, 657, 4625, 37186, 336336, 3379058, 37328103, 449669577, 5866178493, 82387080624, 1239364493118, 19881771085788, 338797668091565, 6111688544942463, 116354993433563797, 2331395107113471188, 49042688584011866880, 1080639600739277669092, 24891049832682424745839
COMMENTS
Circular permutations are permutations whose indices are from the ring of integers modulo n.
REFERENCES
Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012.
EXAMPLE
Since a(5)=22, there are (5-1)!-22=2 circular permutations with consecutive triples i,i+2,i+4 in all circular permutations of length 5. They are exactly (0,2,4,1,3) and (0,2,4,3,1).
EXTENSIONS
a(0)-a(2) prepended and terms a(16) onward added by Max Alekseyev, Feb 04 2024
Number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> acb where a<b<c.
+10
8
1, 1, 2, 5, 20, 102, 626, 4458, 36144, 328794, 3316944, 36755520, 443828184, 5800823880, 81591320880, 1228888215960, 19733475278880, 336551479543440, 6075437671458000, 115733952138747600, 2320138519554562560, 48827468196234035280, 1076310620915575933440
COMMENTS
Also the number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> bac where a<b<c.
Also the number of equivalence classes of S_n under transformations of positionally and numerically adjacent elements of the form abc <--> cba where a<b<c.
Also the number of permutations of [n] avoiding consecutive triples j, j+1, j-1. a(4) = 20 = 4! - 4 counts all permutations of [4] except 1342, 2314, 3421, 4231. - Alois P. Heinz, Apr 14 2021
FORMULA
G.f.: Sum_{k>=0} k! * ( x * (1-x^2) )^k.
a(n) = Sum_{k=0..floor(n/3)} (-1)^k * (n-2*k)! * binomial(n-2*k,k). (End)
EXAMPLE
a(3) = 5: {123, 132}, {213}, {231}, {312}, {321}.
a(4) = 20: {1234, 1243, 1324}, {1342}, {1423}, {1432}, {2134}, {2143}, {2314}, {2341, 2431}, {2413}, {3124}, {3142}, {3214}, {3241}, {3412}, {3421}, {4123, 4132}, {4213}, {4231}, {4312}, {4321}. (End)
MAPLE
b:= proc(s, x, y) option remember; `if`(s={}, 1, add(
`if`(x=0 or x-y<>1 or j-x<>1, b(s minus {j}, y, j), 0), j=s))
end:
a:= n-> b({$1..n}, 0$2):
# second Maple program:
a:= proc(n) option remember; `if`(n<5, [1$2, 2, 5, 20][n+1],
n*a(n-1)+3*a(n-2)-(2*n-2)*a(n-3)+(n-2)*a(n-5))
end:
MATHEMATICA
a[n_] := a[n] = If[n < 5, {1, 1, 2, 5, 20}[[n+1]],
n*a[n-1] + 3*a[n-2] - (2n - 2)*a[n-3] + (n-2)*a[n-5]];
PROG
(PARI) my(N=30, x='x+O('x^N)); Vec(sum(k=0, N, k!*(x*(1-x^2))^k)) \\ Seiichi Manyama, Feb 20 2024
Triangle read by rows: number of permutations of [1..n] with k progressions of rise 2, distance 1 and length 3 (n >= 0, k >= 0).
+10
8
1, 1, 2, 6, 24, 114, 6, 674, 44, 2, 4714, 294, 30, 2, 37754, 2272, 276, 16, 2, 340404, 20006, 2236, 216, 16, 2, 3412176, 193896, 20354, 2200, 156, 16, 2, 37631268, 2056012, 206696, 20738, 1908, 160, 16, 2, 452745470, 23744752, 2273420, 215024, 21136, 1616, 164, 16, 2
EXAMPLE
Triangle begins:
1
1
2
6 [this is for n=3]
24
114 6
674 44 2
4714 294 30 2
37754 2272 276 16 2
340404 20006 2236 216 16 2
3412176 193896 20354 2200 156 16 2
37631268 2056012 206696 20738 1908 160 16 2
...
MAPLE
b:= proc(s, x, y) option remember; expand(`if`(s={}, 1, add(
`if`(x>0 and x-y=2 and y-j=2, z, 1)*b(s minus {j}, y, j), j=s)))
end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b({$1..n}, 0$2)):
MATHEMATICA
b[s_, x_, y_] := b[s, x, y] = Expand[If[s == {}, 1, Sum[
If[x > 0 && x - y == 2 && y - j == 2, z, 1]*
b[s ~Complement~ {j}, y, j], {j, s}]]];
T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 0,
Exponent[p, z]}]][b[Range[n], 0, 0]];
Number of permutations of length n without modular consecutive triples i,i+2,i+4.
+10
7
1, 1, 2, 3, 24, 100, 594, 4389, 35744, 325395, 3288600, 36489992, 441091944, 5770007009, 81213883898, 1223895060315, 19662509172096, 335472890422812, 6057979283966814, 115434096553014565, 2314691409661484600, 48723117262650147387, 1074208020519754180896, 24755214452825129257168
REFERENCES
Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012.
EXAMPLE
For example, a(5) does not count the permutation (0,4,1,3,2) since 4,1,3 is an arithmetic progression of 2 mod(5).
Number of circular permutations of length n without modular consecutive triples i,i+2,i+4.
+10
7
1, 6, 18, 93, 600, 4320, 35168, 321630, 3257109, 36199458, 438126986, 5736774869, 80808984725, 1218563192160, 19587031966352, 334329804180135, 6039535339644630, 115118210695441900, 2308967760171049528, 48613722701440862328, 1072008447320752890459
COMMENTS
Circular permutations are permutations whose indices are from the ring of integers modulo n.
EXAMPLE
Since a(5)=18, there are (5-1)!-18=4 circular permutations with modular consecutive triples i,i+2,i+4 in all circular permutations of length 5. These are exactly (0,2,4,1,3), (0,2,4,3,1), (0,4,2,1,3), and (0,3,2,4,1). Note some have more than one modular progression.
MATHEMATICA
f[i_, n_, k_]:=If[i==0 && k==0, 1, If[i==n && n==k, 1, Binomial[k-1, k-i]*Binomial[n-k-1, k-i-1] + 2*Binomial[k-1, k-i-1]*Binomial[n-k-1, k-i-1]+Binomial[k-1, k-i-1]*Binomial[n-k-1, k-i]]];
w1[i_, n_, k_]:=If[n-2k+i<0, 0, If[n-2k+i==0, 1, (n-2k+i-1)!]];
a[n_, k_]:=Sum[f[i, n, k]*w1[i, n, k], {i, 0, k}];
A165962[n_]:=(n-1)!+Sum[(-1)^k*a[n, k], {k, 1, n}];
b[n_, k_]:=Sum[Sum[Sum[f[j, n/2, p]*f[i-j, n/2, k-p]*w2[i, j, n, k, p], {p, 0, k}], {j, 0, i}], {i, 0, k-1}];
w2[i_, j_, n_, k_, p_]:=If[n/2-2p+j<=0 || n/2-2(k-p)+(i-j)<=0, 0, (n-2k+i-1)!];
A216727[n_?EvenQ]:=(n-1)!+Sum[(-1)^k*b[n, k], {k, 1, n}];
Triangle read by rows: number of circular permutations of [1..n] with k progressions of rise 1, distance 1 and length 3 (n >= 3, k >= 0).
+10
6
1, 1, 1, 5, 0, 1, 20, 3, 0, 1, 102, 14, 3, 0, 1, 627, 72, 17, 3, 0, 1, 4461, 468, 87, 20, 3, 0, 1, 36155, 3453, 582, 103, 23, 3, 0, 1, 328849, 28782, 4395, 704, 120, 26, 3, 0, 1, 3317272, 267831, 37257, 5435, 834, 138, 29, 3, 0, 1
REFERENCES
Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012.
EXAMPLE
Triangle begins:
1;
1, 1; [this is row n=3]
5, 0, 1;
20, 3, 0, 1;
102, 14, 3, 0, 1;
627, 72, 17, 3, 0, 1;
4461, 468, 87, 20, 3, 0, 1;
36155, 3453, 582, 103, 23, 3, 0, 1;
328849, 28782, 4395, 704, 120, 26, 3, 0, 1;
3317272, 267831, 37257, 5435, 834, 138, 29, 3, 0, 1;
...
Number of permutations of length n with no consecutive triples i,i+d,i+2d for all d>0.
+10
5
1, 1, 2, 5, 21, 100, 597, 4113, 32842, 292379, 2925367, 31983248, 383514347, 4966286235, 69508102006, 1039315462467, 16627618496319, 282023014602100, 5075216962675445, 96263599713301975, 1925002914124917950
EXAMPLE
For n=4, there are 4!-a(4)=3 permutations with some consecutive triple i,i+d,i+2d. Note for n=4, only d=1 applies. Hence those three permutations are (0,1,2,3), (1,2,3,0), and (3,0,1,2). Since here only d=1, this is the same value of a(4) in A002628.
MAPLE
b:= proc(s, x, y) option remember; `if`(s={}, 1, add(
`if`(x=0 or x<y or x-y<>y-j,
b(s minus {j}, y, j), 0), j=s))
end:
a:= n-> b({$1..n}, 0$2):
MATHEMATICA
b[s_, x_, y_] := b[s, x, y] = If[s == {}, 1, Sum[If[x == 0 || x < y || x-y != y-j, b[s~Complement~{j}, y, j], 0], {j, s}]];
a[n_] := b[Range[n], 0, 0];
Search completed in 0.008 seconds
|