A260695
a(n) is the number of permutations p of {1,..,n} such that the minimum number of block interchanges required to sort the permutation p to the identity permutation is maximized.
Original entry on oeis.org
1, 1, 1, 5, 8, 84, 180, 3044, 8064, 193248, 604800, 19056960, 68428800, 2699672832, 10897286400, 520105017600, 2324754432000, 130859579289600, 640237370572800, 41680704936960000, 221172909834240000, 16397141420298240000, 93666727314800640000, 7809290721329061888000, 47726800133326110720000
Offset: 0
The next three lines illustrate applying block interchanges to [2 4 6 1 3 5 7], an element of S_7.
Step 1: [2 4 6 1 3 5 7]->[3 5 1 2 4 6 7]-interchange blocks 3 5 and 2 4 6.
Step 2: [3 5 1 2 4 6 7]->[4 1 2 3 5 6 7]-interchange blocks 3 5 and 4.
Step 3: [4 1 2 3 5 6 7]->[1 2 3 4 5 6 7]-interchange blocks 4 and 1 2 3.
As [2 4 6 1 3 5 7] requires 3 = floor(7/2) block interchanges, it is one of the a(7) = 3044.
Each of the 23 non-identity elements of S_4 requires at least 1 block interchange to sort to the identity. But only 8 of these require 2 block interchanges, the maximum number required for elements of S_4. They are: [4 3 2 1], [4 1 3 2], [4 2 1 3], [3 1 4 2], [3 2 4 1], [2 4 1 3], [2 1 4 3], [2 4 3 1]. So, a(4) = 8.
- D. A. Christie, Sorting Permutations by Block-Interchanges, Inf. Process. Lett. 60 (1996), 165-169.
- Robert Cori, Michel Marcus, and Gilles Schaeffer, Odd permutations are nicer than even ones, European Journal of Combinatorics 33:7 (2012), 1467-1478.
- M. Tikhomirov, A conjecture harmonic numbers, MathOverflow, 2020.
- D. Zagier, On the distribution of the number of cycles of elements in symmetric groups.
The number of elements of S_n that can be sorted by: a single block interchange (
A145126), two block interchanges (
A228401), three block interchanges (
A256181), context directed block interchanges (
A249165).
The number of signed permutations that can be sorted by: context directed reversals (
A260511), applying either context directed reversals or context directed block interchanges (
A260506).
-
a[n_]:=Abs[StirlingS1[n+2,Mod[n,2]+1]/Binomial[n+2,2]]; Array[a,25,0] (* Stefano Spezia, Apr 01 2024 *)
-
{ A260695(n) = abs(stirling(n+2, n%2+1)) / binomial(n+2, 2); } \\ Max Alekseyev, Nov 20 2020
Edited and extended by
Max Alekseyev incorporating comments from M. Tikhomirov, Nov 20 2020
A260509
Number of graphs on labeled vertices {x, y, 1, 2, ..., n}, such that there is a partition of the vertices into V_1 and V_2 with x in V_1, y in V_2, every v in V_1 adjacent to an even number of vertices in V_2, and every v in V_2 adjacent to an even number of vertices in V_1.
Original entry on oeis.org
1, 3, 23, 351, 11119, 703887, 89872847, 22945886799, 11740984910671, 12014755220129103, 24602393557227030863, 100754627840184914661711, 825349838279823049359417679, 13521969078301639826644261077327, 443083578482642171171990600910324047, 29037623349739387300519333731237743018319
Offset: 0
a(2) = 23 because there are 23 graphs on {x, y, 1, 2} that admit a vertex partition separating x and y, such that each vertex in one half of the partition is adjacent to an even number of vertices in the other half. For instance, the graph with four edges (x,y), (x,1), (y,2), (1,2) admits the partition {{x,2},{y,1}}.
Cf.
A260506 (counts the special case where the graph in question is required to be the overlap graph of some signed permutation).
Cf.
A006125 (the total number of graphs on n labeled vertices).
-
a(n) = sum(k=0, n, prod(i=1, k, 2^(i+1))*prod(i=k+1, n, 1 - 2^i)); \\ Michel Marcus, Sep 11 2015
-
# a_1(n) and a_2(n) both count the same sequence, in two different ways.
def a_1(n) :
# Output the number of 2-rooted graphs in (a) with n+2 vertices
if n == 0 :
return 1
else :
return 2**((n*n + 3*n) // 2) - (2**n - 1) * a_1(n-1)
def a_2(n) :
# Output the number of 2-rooted graphs in (a) with n+2 vertices
# Formula: \sum_{k=0}^n (\prod_{i=1}^k 2^{i+1}) (\prod_{i=k+1}^n (1 - 2^i))
curr_sum = 0
for k in range(0,n+1) :
curr_prod = 1
for i in range(1,k+1) :
curr_prod *= (2**(i+1))
for i in range(k+1,n+1) :
curr_prod *= (1 - (2**i))
curr_sum += curr_prod
return curr_sum
A260511
Number of signed permutations of length n that are sortable to the identity permutation by some sequence of cdr (context-directed reversal) moves.
Original entry on oeis.org
1, 3, 15, 120, 1227, 15188
Offset: 1
a(2) = 3 because [1,2], [-1,2], and [1,-2] are sortable to the identity [1,2] using only context-directed reversal moves.
- K. L. M. Adamyk, E. Holmes, G. R. Mayfield, D. J. Moritz, M. Scheepers, B. E. Tenner, and H. C. Wauck, Sorting permutations: games, genomes, and cycles, arXiv:1410.2353 [math.CO], 2014.
A249165 gives the number of unsigned permutations sortable by context-directed swaps; this is the analog for signed permutations and context-directed reversals.
A260506 gives the number of signed permutations sortable by both cdr and cds moves together. This sequence is therefore always bounded by
A260506.
A000165 counts the total number of signed permutations.
Showing 1-3 of 3 results.
Comments