The cardinality of a sphere relative to an edit distance

Let Σ be an alphabet (a finite set). We denote by Σ* the set consisting of all finite words (or strings) that can be made from the letters (or phonemes). The set of all n-letter words over Σ will be denoted by Σ_n. Let w be an n-letter word in Σ_n. This paper deals with the cardinality of the sphere S_H(w, p):= {u ∈ Σ_n | H(w, u) = p} of center w and radius p (p ∈ N*) relatively to the Hamming distance H on Σ_n. A new distance T is defined on the language Σ* and the cardinality of the corresponding sphere S_T(w, p):= {u ∈ Σn | T(w, u) = p} is also computed. These cardinalities are showed to satisfy some curious recurrence relations. These recurrence relations incite us to introduce new types of binomial coefficients and binomial formula.