A060595
Number of tilings of the 3-dimensional zonotope constructed from D vectors.
Original entry on oeis.org
1, 2, 10, 148, 7686, 1681104, 1881850464, 13227777493060
Offset: 3
Matthieu Latapy (latapy(AT)liafa.jussieu.fr), Apr 12 2001
Z(3,3) is simply a cube and the only possible tile is Z(3,3) itself, therefore the first term of the series is 1. It is well known that there are always two d-tilings of Z(d+1,d), therefore the second term is 2. More examples are available on my web page.
- A. Bjorner, M. Las Vergnas, B. Sturmfels, N. White and G.M. Ziegler, Oriented Matroids, Encyclopedia of Mathematics 46, Second Edition, Cambridge University Press, 1999
- V. Reiner, The generalized Baues problem, in New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996-1997), 293-336, Math. Sci. Res. Inst. Publ., 38, Cambridge Univ. Press, Cambridge, 1999.
- Helena Bergold, Stefan Felsner, and Manfred Scheucher, Extendability of higher dimensional signotopes, Proc. 38th Eur. Wksp. Comp. Geom. (EuroCG), 2022. See also arXiv:2303.04079 [math.CO], 2023.
- N. Destainville, R. Mosseri and F. Bailly, Fixed-boundary octagonal random tilings: a combinatorial approach, arXiv:cond-mat/0004145 [cond-mat.stat-mech], 2000.
- N. Destainville, R. Mosseri and F. Bailly, Fixed-boundary octagonal random tilings: a combinatorial approach, Journal of Statistical Physics, 102 (2001), no. 1-2, 147-190.
- S. Felsner and H. Weil, Sweeps, arrangements and signotopes, Discrete Applied Mathematics, Volume 109, Issues 1-2, 2001, Pages 67-94.
- M. Latapy, Generalized Integer Partitions, Tilings of Zonotopes and Lattices, arXiv:math/0008022 [math.CO], 2000.
- J. A. Olarte and F. Santos, Hypersimplicial subdivisions, arXiv:1906.05764 [math.CO], 2019.
- Manfred Scheucher, C program for enumeration
- G. M. Ziegler, Higher Bruhat Orders and Cyclic Hyperplane Arrangements, Topology, Volume 32, 1993.
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
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.
- 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).
- D. Armstrong, The sorting order on a Coxeter group, Journal of Combinatorial Theory 116 (2009), no. 8, 1285-1305.
- M. Balko, R. Fulek, and J. Kynčl, Crossing Numbers and Combinatorial Characterization of Monotone Drawings of K_n, Discrete & Computational Geometry, Volume 53, Issue 1, 2015, Pages 107-143.
- Helena Bergold, Stefan Felsner, and Manfred Scheucher, Extendability of higher dimensional signotopes, Proc. 38th Eur. Wksp. Comp. Geom. (EuroCG), 2022. See also arXiv:2303.04079 [math.CO], 2023.
- Herman Chau, On Enumerating Higher Bruhat Orders Through Deletion and Contraction, arXiv:2412.10532 [math.CO], 2024. See p. 2.
- Yunhyung Cho, Jang Soo Kim, and Eunjeong Lee, Enumerate of Gelfand-Cetlin type reduced words, arXiv:2009.06906 [math.CO], 2020. Mentions this sequence.
- Fernando Cortés Kühnast, Justin Dallant, Stefan Felsner, and Manfred Scheucher, An Improved Lower Bound on the Number of Pseudoline Arrangements, arXiv:2402.13107 [math.CO], 2024. See p. 2.
- H. Denoncourt, D. C. Ernst, and D. Story, On the number of commutation classes of the longest element in the symmetric group, arXiv:1602.08328 [math.HO], 2016.
- Adrian Dumitrescu and Ritankar Mandal, New Lower Bounds for the Number of Pseudoline Arrangements, arXiv:1809.03619 [math.CO], 2018.
- Stefan Felsner, On the number of arrangements of pseudolines, Proceedings of the twelfth annual symposium on Computational geometry. ACM, 1996. Also Discrete and Computational Geometry, 18 (1997),257-267. Gives a(10).
- Stefan Felsner and Jacob E. Goodman, Pseudoline Arrangements, Chapter 5 of Handbook of Discrete and Computational Geometry, CRC Press, 2017, see Table 5.6.1. [Specific reference for this sequence] - _N. J. A. Sloane_, Nov 14 2023
- S. Felsner and P. Valtr, Coding and Counting Arrangements of Pseudolines, Discrete and Computational Geometry, 46(3) (2011), 405-416.
- S. Felsner and H. Weil, Sweeps, arrangements and signotopes, Discrete Applied Mathematics Volume 109, Issues 1-2, 2001, Pages 67-94.
- J. Folkman and J. Lawrence, Oriented matroids, Journal of Combinatorial Theory, Series B 25 (1978), no. 2, 199-236.
- Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry, CRC Press, 2017, see Table 5.6.1. [General reference for 2017 edition of the Handbook] - _N. J. A. Sloane_, Nov 14 2023
- M. J. Hay, J. Schiff, and N. J. Fisch, Available free energy under local phase space diffusion, arXiv preprint arXiv:1604.08573 [math-ph], 2016, see Footnote 27.
- J. Kawahara, T. Saitoh, R. Yoshinaka, and S. Minato, Counting Primitive Sorting Networks by PiDDs, Hokkaido University, Division of Computer Science, TCS Technical Reports, TCS-TR-A-11-54, Oct. 2011.
- D. E. Knuth, Axioms and Hulls, Lect. Notes Comp. Sci., Vol. 606 (1992) p. 35. [From _R. J. Mathar_, Apr 02 2009]
- Ricardo Mamede, The commutation classes of a permutation, 14th Comb. Days, Univ. Coimbra (Portugal, 2024). See slide 10.
- S. Minato, Techniques of BDD/ZDD: Brief History and Recent Activity, IEICE Transactions on Information and Systems, Vol. E96-D, No. 7, pp.1419-1429.
- Yan Alves Radtke, Stefan Felsner, Johannes Obenaus, Sandro Roch, Manfred Scheucher, and Birgit Vogtenhuber, Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles, arXiv:2310.19711 [math.CO], 2023. See p. 41.
- Matthew J. Samuel, Word posets, complexity, and Coxeter groups, arXiv:1101.4655 [math.CO], 2011.
- M. J. Samuel, Word posets, with applications to Coxeter groups, arXiv preprint arXiv:1108.3638 [cs.DM], 2011.
- Manfred Scheucher, C++ program for enumeration
- B. E. Tenner, Tiling-based models of perimeter and area, arXiv:1811.00082 [math.CO], 2018.
- M. Widom, N. Destainville, R. Mosseri, and F. Bailly, Two-dimensional random tilings of large codimension, Proceedings of the 7th International Conference on Quasicrystals (ICQ7, Stuttgart), arXiv:cond-mat/9912275 [cond-mat.stat-mech], 1999.
- M. Widom, N. Destainville, R. Mosseri, and F. Bailly, Two-dimensional random tilings of large codimension, Materials Science and Engineering: A, Volumes 294-296, 15 December 2000, Pages 409-412.
- Katsuhisa Yamanaka, Takashi Horiyama, Takeaki Uno, and Kunihiro Wasa, Ladder-Lottery Realization, 30th Canadian Conference on Computational Geometry (CCCG 2018) Winnipeg.
- K. Yamanaka, S. Nakano, Y. Matsui, R. Uehara, and K. Nakada, Efficient enumeration of all ladder lotteries and its application, Theoretical Computer Science, Vol. 411, pp. 1714-1722, 2010.
- G. M. Ziegler, Higher Bruhat Orders and Cyclic Hyperplane Arrangements, Topology, Volume 32, 1993.
- Index entries for sequences related to sorting.
-
# 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
-
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 *)
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
Showing 1-2 of 2 results.
Comments