Metric intersection problems in Cayley graphs and the Stirling recursion

In Sym(n) with n = 5 let H be a conjugacy class of elements of order 2 and let G be the Cayley graph whose vertex set is the group G generated by H (so G = Sym(n) or Alt(n)) and whose edge set is determined by H. We are interested in the metric structure of this graph. In particular, for g?G let B r (g) be the metric ball in G of radius r and centre g. We show that the intersection numbers F(G;r,g):=|Br(e)nBr(g)| are generalized Stirling functions in n and r. The results are motivated by the study of error graphs in Levenshtein (Dokl Akad Nauk 354:593–596, 1997; IEEE Trans Inform Theory 47(1):2–22, 2001; (J Comb Theory Ser A 93(2):310–332, 2001) and related reconstruction problems.