cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

A006245 Number of primitive sorting networks on n elements; also number of rhombic tilings of a 2n-gon.

Original entry on oeis.org

1, 1, 2, 8, 62, 908, 24698, 1232944, 112018190, 18410581880, 5449192389984, 2894710651370536, 2752596959306389652, 4675651520558571537540, 14163808995580022218786390, 76413073725772593230461936736
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Also the number of commutation classes of reduced words for the longest element of a Weyl group of type A_{n-1} (see Armstrong reference).
Also the number of signotopes of rank 3, i.e., mappings X:{{1..n} choose 3}->{+,-} such that for any four indices a < b < c < d, the sequence X(a,b,c), X(a,b,d), X(a,c,d), X(b,c,d) changes its sign at most once (see Felsner-Weil and Balko-Fulek-Kynčl reference). - Manfred Scheucher, Oct 20 2019
There is a relation to non-degenerate oriented matroids of rank 3 on n elements (see Folkman-Lawrence reference). - Manfred Scheucher, Feb 09 2022, based on comment by Matthew J. Samuel, Jan 19 2013
Also the number of tilings of the 2-dimensional zonotope constructed from D vectors. The zonotope Z(D,d) is the projection of the D-dimensional hypercube onto the d-dimensional space and the tiles are the projections of the d-dimensional faces of the hypercube. Here d=2 and D varies.
Also the number of simple arrangements of n pseudolines in the Euclidean plane. - Manfred Scheucher, Jun 22 2023

Examples

			This is a wiring diagram, one sample of the 62 objects that are counted for n=5:
  1-1-1-1 4-4 5-5
         X   X
  2 3-3 4 1 5 4-4
   X   X   X
  3 2 4 3 5 1 3-3
     X   X   X
  4-4 2 5 3-3 1 2
       X       X
  5-5-5 2-2-2-2 1
Each X denotes a comparator that exchanges the two incoming strands from the left. The whole network has n*(n-1)/2 such comparators and exchanges the order 12345 at the left edge into the reverse order 54321 at the right edge. It is also a pseudoline arrangement consisting of n x-monotone curves (from left to right), which pairwise cross exactly once.

References

  • Shin-ichi Minato, Counting by ZDD, Encyclopedia of Algorithms, 2014, pp. 1-6.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A006246. See A005118 for primitive sorting networks with exactly one comparator ("X") per column. See A060596-A060601 for higher dimensions. Cf. A006247.

Programs

  • Maple
    # classes: Wrapper for computing number of commutation classes;
#   pass a permutation as a list
# Returns number of commutation classes of reduced words
# Longest element is of the form [n, n-1, ..., 1] (see Comments)
classes:=proc(perm) option remember:
    RETURN(classesRecurse(Array(perm), 0, 1)):
end:
#classesRecurse: Recursive procedure for computing number of commutation classes
classesRecurse:=proc(perm, spot, negs) local swaps, i, sums, c, doneany:
    sums:=0:
    doneany:=0:
    for i from spot to ArrayNumElems(perm)-2 do
        if perm[i+1]>perm[i+2] then
            swaps:=perm[i+1]:
            perm[i+1]:=perm[i+2]:
            perm[i+2]:=swaps:
            c:=classes(convert(perm, `list`)):
            sums:=sums+negs*c+classesRecurse(perm, i+2, -negs):
            swaps:=perm[i+1]:
            perm[i+1]:=perm[i+2]:
            perm[i+2]:=swaps:
            doneany:=1:
        end:
    end:
    if spot=0 and doneany=0 then RETURN(1):
    else RETURN(sums):
    end:
end:
seq(classes([seq(n+1-i, i = 1 .. n)]), n = 1 .. 9)
# Matthew J. Samuel, Jan 23 2011, Jan 26 2011
  • Mathematica
    classes[perm_List] := classes[perm] = classesRecurse[perm, 0, 1];
classesRecurse[perm_List, spot_, negs_] := Module[{swaps, i, Sums, c, doneany, prm = perm}, Sums = 0; doneany = 0; For[i = spot, i <= Length[prm]-2, i++, If[prm[[i+1]] > prm[[i+2]], swaps = prm[[i+1]]; prm[[i+1]] = prm[[i+2]]; prm[[i+2]] = swaps; c = classes[prm]; Sums = Sums + negs*c + classesRecurse[prm, i+2, -negs]; swaps = prm[[i+1]]; prm[[i+1]] = prm[[i+2]]; prm[[i+2]] = swaps; doneany = 1]]; If[spot == 0 && doneany == 0, Return[1], Return[Sums]]];
a[n_] := a[n] = classes[Range[n] // Reverse];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 1, 9}] (* Jean-François Alcover, May 09 2017, translated from Maple *)

Formula

Felsner and Valtr show that 0.1887 <= log_2(a(n))/n^2 <= 0.6571 for sufficiently large n. - Jeremy Tan, Nov 20 2017
Dumitrescu and Mandal improved the lower bound to 0.2083 <= log_2(a(n))/n^2 for sufficiently large n. - Manfred Scheucher, Sep 13 2021

Extensions

More terms from Sebastien Veigneau (sv(AT)univ-mlv.fr), Jan 15 1997
a(10) confirmed by Katsuhisa Yamanaka(yamanaka(AT)hol.is.uec.ac.jp), May 06 2009. This value was also confirmed by Takashi Horiyama of Saitama Univ.
a(11) from Katsuhisa Yamanaka(yamanaka(AT)hol.is.uec.ac.jp), May 06 2009
Reference with formula that the Maple program implements added and a(11) verified by Matthew J. Samuel, Jan 25 2011
Removed invalid comment concerning the denominators of the indicated polynomials; added a(12). - Matthew J. Samuel, Jan 30 2011
a(13) from Toshiki Saitoh, Oct 17 2011
a(14) and a(15) from Yuma Tanaka, Aug 20 2013
a(16) by Günter Rote, Dec 01 2021

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.