Equivalence classes of nodes in trees and rational generating functions

2014/07/20 by Amritanshu Prasad, Prasad, Amritanshu
Mathematics · #05A15 #Combinatorics (math.CO) #FOS: Mathematics #G.2.1 #Representation Theory (math.RT) #acm:05A15 #math.CO #math.RT #msc:05A15

paper · pdf · doi:10.48550/arxiv.1407.5284

17 pages, 1 figure, 2 tables

arxiv created 2014/07/20 · arxiv updated 2014/07/22

Abstract

Let c_n denote the number of nodes at a distance n from the root of a rooted tree. A criterion for proving the rationality and computing the rational generating function of the sequence \c_n\ is described. This criterion is applied to counting the number of conjugacy classes of commuting tuples in finite groups and the number of isomorphism classes of representations of polynomial algebras over finite fields. The method for computing the rational generating functions, when applied to the study of point configurations in finite sets, gives rise to some classical combinatorial results on Bell numbers and Stirling numbers of the second kind. When applied to the study of vector configurations in a finite vector space, it reveals a connection between counting such configurations and Gaussian binomial coefficients.

Related

• Combinatorial Constructions for Sifting Primes and Enumerating the Rationals
• Orbit length generating functions of automorphisms of a rooted regular binary tree
• An arborist's guide to the rationals
• On rationality of generating function for the number of spanning trees in circulant graphs
• Automated Counting of Spanning Trees for Several Infinite Families of Graphs