Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

Rook theory. I. Rook equivalence of Ferrers boards


Authors: Jay R. Goldman, J. T. Joichi and Dennis E. White
Journal: Proc. Amer. Math. Soc. 52 (1975), 485-492
MSC: Primary 05A15
MathSciNet review: 0429578
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We introduce a new tool, the factorial polynomials, to study rook equivalence of Ferrers boards. We provide a set of invariants for rook equivalence as well as a very simple algorithm for deciding rook equivalence of Ferrers boards. We then count the number of Ferrers boards rook equivalent to a given Ferrers board.


References [Enhancements On Off] (What's this?)

  • [1] Louis Comtet, Analyse combinatoire. Tomes I, II, Collection SUP: “Le Mathématicien”, 4, vol. 5, Presses Universitaires de France, Paris, 1970 (French). MR 0262087 (41 #6697)
  • [2] Dominique Foata, Étude algébrique de certains problèmes d’analyse combinatoire et du calcul des probabilités, Publ. Inst. Statist. Univ. Paris 14 (1965), 81–241 (French). MR 0220327 (36 #3392)
  • [3] D. Foata and M. P. Schützenberger, On the rook polynomials of Ferrers relations, Combinatorial theory and its applications, II (Proc. Colloq., Balatonfüred, 1969), North-Holland, Amsterdam, 1970, pp. 413–436. MR 0360288 (50 #12738)
  • [4] -, Théorie géométrique des polynômes eulériens, Lecture Notes in Math., vol. 138, Springer-Verlag, Berlin and New York, 1970. MR 42 #7523.
  • [5] Solomon W. Golomb and Leonard D. Baumert, Backtrack programming, J. Assoc. Comput. Mach. 12 (1965), 516–524. MR 0195585 (33 #3783)
  • [6] Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching; Addison-Wesley Series in Computer Science and Information Processing. MR 0445948 (56 #4281)
  • [7] Ronald Mullin and Gian-Carlo Rota, On the foundations of combinatorial theory. III. Theory of binomial enumeration, Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969), Academic Press, New York, 1970, pp. 167–213 (loose errata). MR 0274300 (43 #65)
  • [8] John Riordan, An introduction to combinatorial analysis, Wiley Publications in Mathematical Statistics, John Wiley & Sons Inc., New York, 1958. MR 0096594 (20 #3077)
  • [9] Gian-Carlo Rota, The number of partitions of a set, Amer. Math. Monthly 71 (1964), 498–504. MR 0161805 (28 #5009)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05A15

Retrieve articles in all journals with MSC: 05A15


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9939-1975-0429578-4
PII: S 0002-9939(1975)0429578-4
Keywords: Rook numbers, rook equivalence, rook polynomials, Ferrers board, permutations with restricted positions, binomial type, enumeration
Article copyright: © Copyright 1975 American Mathematical Society