Remote Access Proceedings of the American Mathematical Society
Green Open Access

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
  • [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
  • [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
  • [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
  • [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
  • [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
  • [8] John Riordan, An introduction to combinatorial analysis, Wiley Publications in Mathematical Statistics, John Wiley & Sons, Inc., New York; Chapman & Hall, Ltd., London, 1958. MR 0096594
  • [9] Gian-Carlo Rota, The number of partitions of a set, Amer. Math. Monthly 71 (1964), 498–504. MR 0161805

Similar Articles

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

Retrieve articles in all journals with MSC: 05A15

Additional Information

Keywords: Rook numbers, rook equivalence, rook polynomials, Ferrers board, permutations with restricted positions, binomial type, enumeration
Article copyright: © Copyright 1975 American Mathematical Society