The Use of S-Functions in Combinatorial Analysis

Read, Ronald C.

Canadian journal of mathematics, Tome 20 (1968) no. 1, pp. 808-841

Résumé

The aim of this paper is to present a unified treatment of certain theorems in Combinatorial Analysis (particularly in enumerative graph theory), and their relations to various results concerning symmetric functions and the characters of the symmetric groups. In particular, it treats of the simplification that is achieved by working with S-functions in preference to other symmetric functions when dealing with combinatorial problems. In this way it helps to draw closer together the two subjects of Combinatorial Analysis and the theory of Finite Groups. The paper is mainly expository; it contains little that is really new, though it displays several old results in a new setting.

Détail

DOI : 10.4153/CJM-1968-080-x

Bibliographie

[1] 1. Bivins, R. L., Metropolis, N., Stein, P. R., and Wells, M. B., Characters of the symmetric groups of degrees 15 and 16, Math. Tables and other aids to computing 8 (1954), 212–216. Google Scholar

[2] 2. Comet, S., On the machine calculation of characters of the symmetric group, Comptes Rendus du XIIe Congrès des Mathématiciens Scandinaves (1953), 18–23. Google Scholar

[3] 3. Comet, S., Improved methods to calculate the characters of the symmetric group, Math. Tables and other aids to computing 14, 70 (1960), 104–117. Google Scholar

[4] 4. Comet, S., Notations for partitions, Math. Tables and other aids to computing 9-52 (1955), 143–146. Google Scholar

[5] 5. De Bruijn, N. G. Generalization of Pôlya's fundamental theorem in enumerative combinatorial analysis, Nederl. Akad. Wetensch. Proc. Ser. A 62 = Indag. Math. 21 (1959), 59–69. Google Scholar

[6] 6. De Bruijn, N. G. Enumerative combinatorial problems concerning structures, Nieuw Arch. Wisk. (3) 11 (1963), 142–161. Google Scholar

[7] 7. Foulkes, H. O., Differential operator associated with S-functions, J. London Math. Soc. 24 (1949), 136-143. Google Scholar

[8] 8. Foulkes, H. O., Concomitants of the quintic and sextic, J. London Math. Soc. 25 (1950), 205–209. Google Scholar

[9] 9. Foulkes, H. O., Plethysms of S-functions, Philos. Trans. Roy. Soc. London Ser. A 246 (1954), 555–591. Google Scholar

[10] 10. Foulkes, H. O., On Redfteld's group reduction functions, Can. J. Math. 15 (1963), 272–284. Google Scholar

[11] 11. Harary, F., The number of linear, directed, rooted and connected graphs, Trans. Amer. Math. Soc. 78 (1955), 109–112. Google Scholar

[12] 12. Harary, F., Unsolved problems in the enumeration of graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 63–95. Google Scholar

[13] 13. Harary, F., Combinatorial problems in graphical enumeration, Applied Combinatorial Mathematics, ed. Beckenbach, E. F. (Wiley, New York, 1964). Google Scholar

[14] 14. Harary, F. and Palmer, E., The power group of two permutation groups, Proc. Nat. Acad. Sci. U.S.A. 54 (1965), 680–682. Google Scholar

[15] 15. Harary, F. and Palmer, E., The enumeration methods of Redfield, Amer. J. Math. 89 (1967), 373–384. Google Scholar

[16] 16. Kondo, K., Tables of characters of Su, Proc. Phys. Math. Soc. Japan (3) 22 (1940), 585–593. Google Scholar

[17] 17. Littlewood, D. E., Invariant theory, tensors and group characters, Philos. Trans. Roy. Soc. London Ser. A 298 (1944), 305–365. Google Scholar

[18] 18. Littlewood, D. E., The theory of group characters, 2nd ed. (Oxford Univ. Press, Oxford, 1950). Google Scholar

[19] 19. Littlewood, D. E., A university algebra (Heinemann, London, 1950). Google Scholar

[20] 20. Littlewood, D. E., Modular representations of symmetric groups, Proc. Roy. Soc. London Ser. A 209 (1951), 234–353. Google Scholar

[21] 21. Littlewood, D. E., The Kronecker product of symmetric group representations, J. London Math. Soc. 81 (1956), 89–93. Google Scholar

[22] 22. Littlewood, D. E., Plethysm and the inner product of S-j'unctions, J. London Math. Soc. 82 (1957), 18–22. Google Scholar

[23] 23. Littlewood, D. E., The inner plethysm of S-functions, Can. J. Math. 10 (1958), 1–16. Google Scholar

[24] 24. McMahon, Major P. A., Combinatory analysis, Vols. I and II (Reprinted, Chelsea, New York, 1960). Google Scholar

[25] 25. Nakayama, T., On some modular properties of irreducible representations of a symmetric group, Japan. J. Math. 17 (1941), 165-184; 411–423. Google Scholar

[26] 26. Pôlya, G., Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145–254. Google Scholar

[27] 27. Read, R. C., The enumeration of locally restricted graphs (I), J. London Math. Soc. 84 1959), 417–436. Google Scholar

[28] 28. Read, R. C., The enumeration of locally restricted graphs (II), J. London Math. Soc. 35 (1960), 344–351. Google Scholar

[29] 29. Read, R. C., On the number of self-complementary graphs and digraphs, J. London Math. Soc. 38 (1963), 99–104. Google Scholar

[30] 30. Read, R. C., Some applications of a theorem of De Bruijn, Graph Theory and Theoretical Physics Academic Press, (New York, 1967). Google Scholar

[31] 31. Redfield, J. H., The theory of group-reduced distributions, Amer. J. Math. 49 (1927), 433–455. Google Scholar

[32] 32. Riordan, J., An introduction to combinatorial analysis (Wiley, New York, 1958). Google Scholar

[33] 33. Robinson, G de B. and Taulbee, O. E., The reduction of the inner product of two irreducible representations of Sn, Proc. Nat. Acad. Sci. U.S.A. 40 (1954), 723–726. Google Scholar

[34] 34. Sheehan, J., The superposition of graphs (Doctoral Thesis, Swansea, 1966). Google Scholar

[35] 35. Todd, J., A note on the algebra of S-f unctions, Proc. Cambridge Philos. Soc. 45 (1949), 328. Google Scholar

[36] 36. Zia-ud-Din, M., Invariant matrices and S-f unctions, Proc. Edinburgh Math. Soc. 5 (1937), 43–45. Google Scholar

[37] 37. Zia-ud-Din, M., The characters of the symmetric group of order 11!, Proc. London Math. Soc. (2) 39 (1935), 200–204. Google Scholar

[38] 38. Zia-ud-Din, M., The characters of the symmetric groups of degrees 12 and 13, Proc. London Soc. (2) 42 (1937), 340–356. Google Scholar