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
DOI: https://doi.org/10.1090/S0002-9939-1975-0429578-4
MathSciNet review: 0429578
Full-text PDF

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] L. Comtet, Analyse combinatoire. Tomes I, II, Collection SUP: Le Mathématicien, 4, 5, Presses Universitaires de France, Paris, 1970. MR 41 #6697. MR 0262087 (41:6697)
  • [2] D. C. Foata, Etude algébrique de certains problèmes d'analyse combinatoire et du calcul des probabilités, Publ. Inst. Statist. Univ. Paris 14 (1965), 81-241. MR 36 #3392. MR 0220327 (36:3392)
  • [3] D. C. Foata and M. P. Schützenberger, On the rook polynomials of Ferrers relations, Colloq. Math. Soc. Janos Bolyai, 4, Combinatorial Theory and its Applications, vol. 2 (P. Erdös et al., eds.), North-Holland, Amsterdam, 1970. 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] S. W. Golomb and L. D. Baumert, Backtrack programming, J. Assoc. Comput. Mach. 12 (1965), 516-524. MR 33 #3783. MR 0195585 (33:3783)
  • [6] D. E. Knuth, The art of computer programming. Vol. 3: Sorting and searching, Addison-Wesley, Reading, Mass., 1968. MR 0445948 (56:4281)
  • [7] R. C. Mullin and G.-C. Rota, On the foundations of combinatorial theory. III. Theory of binomial enumeration, Graph Theory and its Applications (Proc. Advanced Sem., Math. Res. Center, Univ. of Wisconsin, Madison, Wis., 1969), Academic Press, New York, 1970, pp. 167-213. MR 43 #65. MR 0274300 (43:65)
  • [8] J. Riordan, An introduction to combinatorial analysis, Wiley, New York; Chapman & Hall, London, 1958. MR 20 #3077. MR 0096594 (20:3077)
  • [9] G.-C. Rota, The number of partitions of a set, Amer. Math. Monthly 71 (1964), 498-504. MR 28 #5009. 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: https://doi.org/10.1090/S0002-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

American Mathematical Society