A187804 Number of circular permutations of length n whose n flattenings are all not derangements.
1, 0, 3, 0, 19, 0, 0, 0
Offset: 3
A181566 Minimum number of random elements such that their orders allow identification of an abelian group of order n (sampled uniformly) with probability greater than 1/2.
0, 0, 0, 2, 0, 0, 0, 4, 3, 0, 0, 3, 0, 0, 0, 8, 0, 3, 0, 4, 0, 0, 0, 7, 5, 0, 8, 5, 0, 0, 0, 16, 0, 0, 0, 9, 0, 0, 0, 12, 0, 0, 0, 5, 4, 0, 0, 19, 7, 5, 0, 6, 0, 12, 0, 16, 0, 0, 0, 6, 0, 0, 5, 37, 0, 0, 0, 6, 0, 0, 0, 20, 0, 0, 5, 6, 0, 0, 0, 32, 27, 0, 0, 6, 0, 0, 0, 26, 0, 5, 0, 7, 0, 0, 0
Offset: 1
Keywords
Examples
For n=4, by the fundamental theorem of finite abelian groups, the group is either Z4 or Z2 x Z2. When you choose 2 random elements, if 1 element comes out of the 2 elements of order 4, you will know you have Z4. If the 2 elements are of order 2 in Z2 x Z2, you will know you have Z2 x Z2. Calculating the probabilities, when you choose 2 random elements, if the group is Z4, there is a 5/6 chance of knowing it. If it is Z2 x Z2, there is a 1/2 chance of knowing it. Since we assume each non-isomorphic abelian group of order n has the same probability of being the group, averaging 5/6 and 1/2 we get a 2/3 chance that the group is known after choosing 2 elements. Since the probability that a single random element will allow us to identify the group is 1/4, which is not greater than 1/2, a(4) = 2.
Crossrefs
Cf. A181189.
Extensions
Edited and terms a(16) onward added by Max Alekseyev, Oct 07 2023
A181189 Maximal number of elements needed to identify an abelian group of order n by testing the order of random elements.
0, 0, 0, 3, 0, 0, 0, 5, 4, 0, 0, 7, 0, 0, 0, 13, 0, 7, 0, 11, 0, 0, 0, 13, 6, 0, 10, 15, 0, 0, 0, 29, 0, 0, 0, 19, 0, 0, 0, 21, 0, 0, 0, 23, 16, 0, 0, 37, 8, 11, 0, 27, 0, 19, 0, 29, 0, 0, 0, 31, 0, 0, 22, 61, 0, 0, 0, 35, 0, 0, 0, 37, 0, 0, 16, 39, 0, 0, 0, 61, 64, 0, 0, 43, 0, 0, 0, 45, 0, 31
Offset: 1
Keywords
Examples
For n=20, by the fundamental theorem of finite abelian groups, the group is either Z20 or Z10 x Z2. At worst, you could choose the identity, 1 element of order 2, 4 elements of order 5, and 4 elements of order 10. Then you still wouldn't know which group you have. But the order of the next element you choose will determine the group you have. So a(20)=11.
The previous value was a(16) = 9; It should be 13. Two of the size-16 groups have shapes [4,2,2] and [4,4], with element-orders:quantities
[4,2,2] 1:1 2:7 4:8
[4,4] 1:1 2:3 4:12
The sample 1:1, 2:3, 4:8 (12 in total) won't distinguish those two. - _Don Reble_, Oct 04 2023
Links
- Max Alekseyev, Table of n, a(n) for n = 1..10000
- R. J. Mathar, List of element order statistics for n <= 64.
Formula
For all squarefree n, a(n)=0, since there is only one abelian group of order n. Hence the group is trivially known without any checking.
Extensions
Corrected and extended by Don Reble - N. J. A. Sloane, Oct 04 2023
a(1)=0 prepended by Max Alekseyev, Oct 07 2023
A174078 Number of circular permutations of length n with no consecutive triples i,i+2,i+4 or i,i-2,i-4.
20, 100, 600, 4244, 34264, 311424, 3143912, 34833964, 420917638, 5513592091, 77715460917
Offset: 5
Keywords
Comments
Circular permutations are permutations whose indices are from the ring of integers modulo n.
Examples
For n=5 there are (5-1)!-a(5)=4 circular permutations with i,i+2,i+4 or i,i-2,i-4 triples. They are (0,2,4,1,3), (0,2,4,3,1), (0,1,3,4,2), and (0,3,1,4,2).
Extensions
a(10)-a(15) from Donovan Johnson, Sep 24 2010
A174079 Number of circular permutations of length n with no consecutive triples i,i+2,i+4 (mod n) or i,i-2,i-4 (mod n).
12, 84, 494, 3696, 30574
Offset: 5
Keywords
Comments
Circular permutations are permutations whose indices are from the ring of integers modulo n.
Examples
For n=5 there are (5-1)!-a(5)=12 circular permutations with triples i,i+2,i+4 (mod 5) or triples i,i-2,i-4 (mod 5). An example of one is (0,3,1,2,4) because of the progression 0,3,1 (mod 5).
A165961 Number of circular permutations of length n without 3-sequences.
1, 5, 20, 102, 627, 4461, 36155, 328849, 3317272, 36757822, 443846693, 5800991345, 81593004021, 1228906816941, 19733699436636, 336554404751966, 6075478765948135, 115734570482611885, 2320148441078578447, 48827637296350480457, 1076313671861962141616
Offset: 3
Keywords
Comments
Circular permutations are permutations whose indices are from the ring of integers modulo n. 3-sequences are of the form i,i+1,i+2. Sequence gives number of permutations of [n] starting with 1 and having no 3-sequences.
a(n) is also the number of permutations of length n-1 without consecutive fixed points (cf. A180187). - David Scambler, Mar 27 2011
Examples
For n=4 the a(4)=5 solutions are (0,1,3,2), (0,2,1,3), (0,2,3,1), (0,3,1,2) and (0,3,2,1).
References
- Wayne M. Dymacek, Isaac Lambert and Kyle Parsons, Arithmetic Progressions in Permutations, http://math.ku.edu/~ilambert/CN.pdf, 2012. - From N. J. A. Sloane, Sep 15 2012 [broken link]
Links
- Michael De Vlieger, Table of n, a(n) for n = 3..450
- Wayne M. Dymacek and Isaac Lambert, Permutations Avoiding Runs of i, i+1, i+2 or i, i-1, i-2, Journal of Integer Sequences, Vol. 14 (2011), Article 11.1.6.
- Kyle Parsons, Arithmetic progressions in permutations, Thesis, 2011.
Crossrefs
A column of A216718. - N. J. A. Sloane, Sep 15 2012
Programs
-
Maple
d[0] := 1: for n to 51 do d[n] := n*d[n-1]+(-1)^n end do: a := proc (n) options operator, arrow: sum(binomial(n-k, k)*d[n-k-1], k = 0 .. floor((1/2)*n)) end proc: seq(a(n), n = 3 .. 23); # Emeric Deutsch, Sep 07 2010
-
Mathematica
a[n_] := Sum[Binomial[n-k, k] Subfactorial[n-k-1], {k, 0, n/2}]; a /@ Range[3, 21] (* Jean-François Alcover, Oct 29 2019 *)
Formula
Let b(n) be the sequence A002628. Then for n > 5, this sequence satisfies a(n) = b(n-1) - b(n-3) + a(n-3).
a(n) = Sum_{k=0..n/2} binomial(n-k,k)*d(n-k-1), where d(j)=A000166(j) are the derangement numbers. - Emeric Deutsch, Sep 07 2010
Extensions
More terms from Emeric Deutsch, Sep 07 2010
Edited by N. J. A. Sloane, Apr 04 2011
A165960 Number of permutations of length n without modular 3-sequences.
1, 1, 2, 3, 20, 100, 612, 4389, 35688, 325395, 3288490, 36489992, 441093864, 5770007009, 81213878830, 1223895060315, 19662509071056, 335472890422812, 6057979285535388, 115434096553014565, 2314691409652237700, 48723117262650147387, 1074208020519710570054
Offset: 0
Keywords
Comments
Modular 3-sequences are of the following form: i,i+1,i+2, where arithmetic is modulo n.
Examples
For n=3 the a(3) = 3 solutions are (0,2,1), (1,0,2) and (2,1,0).
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..450
Formula
a(n) = n * A165961(n).
Extensions
a(0)-a(2) and a(15)-a(22) from Alois P. Heinz, Apr 14 2021
A174076 Number of permutations of length n with no consecutive triples i,i+2,i+4 or i,i-2,i-4.
1, 1, 2, 6, 24, 108, 632, 4408, 35336, 319056, 3205824, 35451984, 427683560, 5588310904, 78615281768, 1184587864512, 19033796498496, 324852522308160, 5868833343451592, 111889157407344424
Offset: 0
Comments
Note for n<5 there are no such subsequences, so those values are trivially n!. Also note it is possible for a permutation to have both i,i+2,i+4 and i,i-2,i-4 triples, as in an example from n=7: (2,4,6,5,3,1,0). This permutation is not counted by a(7).
Examples
For n=5 there are 5!-a(5)=12 permutations with i,i+2,i+4 or i,i-2,i-4 triples. An examples of one is (4,2,0,1,3).
Extensions
a(0)-a(4) and a(10)-a(19) from Alois P. Heinz, Apr 14 2021
A174077 Number of permutations of length n with no consecutive triples i,i+2,i+4 (mod n) or i,i-2,i-4 (mod n).
1, 1, 2, 0, 24, 80, 504, 3794, 31616, 290970, 2973600, 33311520, 405781344, 5342413414, 75612197528, 1144942063230, 18471128518656, 316309310084728, 5730646943736936
Offset: 0
Examples
As an example, (0,4,1,2,3) is counted by a(5), but (0,4,1,3,2) is not because it has the progression 4,1,3.
Extensions
Definition corrected by Isaac Lambert, Mar 15 2010
a(0)-a(4) and a(10)-a(18) from Alois P. Heinz, Apr 15 2021
A174087 Number of circular permutations with no arithmetic progressions i, ..., i+r, ..., i+2r (mod n) of any equal spacings d.
4, 0, 12, 0, 96, 1296, 1520, 23540, 101472, 686724
Offset: 4
Comments
Circular permutations are permutations whose indices are from the ring of integers modulo n. Here we count both the sequence 1,2,3 (r=1) as a progression in 1,2,3,0,4,5, (note d=1) and in 1,0,2,4,3,5 (here, d=2).
Examples
a(4) has the same value as A078628(4) since the only possible distance is 1.
Links
- Peter Hegarty, Permutations avoiding arithmetic patterns, The Electronic Journal of Combinatorics, 11 (2004), #R39 (includes this sequence times n).
Comments
Examples