OFFSET
1,5
COMMENTS
To prove Paul D. Hanna's formula for the row n o.g.f. A(x,n) = Sum_{m >= 1} T(n,m)*x^m, we use Leibniz's rule for the k-th derivative of a product of functions: dx^k(exp(k^n*x) * (1 - A(x,n)))/dx = Sum_{s=0..k} binomial(k,s) * d^s(exp(k^n*x))/dx^s * d^(k-s) (1 - A(x,n))/dx^(k-s) = k^(n*k) * exp(k^n*x) * (1 - Sum_{m>=1} T(n,m) * x^m) - Sum_{s=0..k-1} binomial(k,s) * k^(n*s) * exp(k^n*x) * (Sum_{m>=1} (m!/(m-(k-s))!) * T(n,m) * x^(m-(k-s))). The coefficient of x^k for exp(k^n*x) * (1 - A(x,n)) is obtained by setting x = 0 in the k-the derivative, and it is equal to k^(n*k) - Sum_{s=0..k-1} binomial(k,s) * k^(n*s) * (k-s)! * T(n,k-s) = k! * (k^(n*k)/k! - Sum_{s=0..k-1} k^(n*s)/s! * T(n,k-s)) = 0 because of the recurrence that T(n,k) satisfies.
To prove the formula below for T(n,k) that involves the compositions of k, we use mathematical induction on k. For k = 1, it is obvious. Assume it is true for all n and all m < k. Consider the compositions of k.
There is only one of size r = 1, namely k, and corresponds to the term k^(n*k)/k! in the recurrence T(n,k) = k^(n*k)/k! - Sum_{s=1..k-1} k^(n*s)/s! * T(n,k-s).
For the other compositions (s_1, ..., s_r) of k (of any size r >= 2), we group them according to the their last element s_r = s in {1, 2, ..., k - 1}, which gives rise to the factor k^(n*s)/s! = (Sum_{i=1..r} s_i)^(n*s_r)/s_r!. Using the inductive hypothesis, we substitute the expression for T(n,k-s) in the recurrence T(n,k) = k^(n*k)/k! - Sum_{s=1..k-1} k^(n*s)/s! * T(n,k-s). Each term in the expression for T(n,k-s) corresponds to a composition of k - s and is postmultiplied by k^(n*s)/s! = (Sum_{i=1..r} s_i)^(n*s_r)/s_r!. We thus get a term in the expression for T(n,k) that corresponds to a composition of the form (composition of k - s) + s, and the sign of this term is (-1)^((size of composition of k - s) + 1). The rest of the proof follows easily.
LINKS
Michael A. Harrison, A census of finite automata, Canadian Journal of Mathematics, 17 (1965), 100-113.
Valery A. Liskovets [ Liskovec ], Enumeration of nonisomorphic strongly connected automata, (in Russian); Vesti Akad. Nauk. Belarus. SSR, Ser. Phys.-Mat., No. 3, 1971, pp. 26-30, esp. p. 30 (Math. Rev. 46 #5081; Zentralblatt 224 #94053).
Valery A. Liskovets [ Liskovec ], A general enumeration scheme for labeled graphs, (in Russian); Dokl. Akad. Nauk. Belarus. SSR, Vol. 21, No. 6 (1977), pp. 496-499 (Math. Rev. 58 #21797; Zentralblatt 412 #05052).
Michel Marcus, PARI program that implements the formula for T(n,k) that involves compositions of k, 2021.
Robert W. Robinson, Counting strongly connected finite automata, in: Graph Theory with Applications to Graph Theory and Computer Science, Wiley, 1985, pp. 671-685.
FORMULA
T(n,k) = k^(n*k)/k! - Sum_{s=1..k-1} k^(n*s)/s! * T(n,k-s).
For each n >= 1, the row n o.g.f. A(x,n) = Sum_{k >= 1} T(n,k)*x^k satisfies [x^k] (exp(k^n*x) * (1 - A(x,n))) = 0 for each k >= 1. (This is Paul D. Hanna's formula from the shifted rows 2-5: A107668, A107675, A304394, A304395.)
A027834(k) = T(2, k)*k! + Sum_{t=1..k-1} binomial(k-1, t-1) * T(2, k-t) * (k-t)! * A027834(t), where A027834(k) = number of strongly connected k-state 2-input automata. (See Theorem 2 in Valery A. Liskovets's 1971 paper.)
T(n,k) = Sum_{r=1..k} (-1)^(r-1) * Sum_{s_1, ..., s_r} (1/(Product_{j=1..r} s_j!)) * Product_{j=1..r} (Sum_{i=1..j} s_i)^(n*s_j)), where the second sum is over lists (s_1, ..., s_r) of positive integers s_i such that Sum_{i=1..r} s_i = k. (Thus the second sum is over all ordered partitions (i.e., compositions) of k.)
T(n,k=3) = (27^n - 3*9^n - 3*12^n)/6 + 6^n.
T(n,k=4) = 256^n/24 - (5/12)*64^n - 108^n/6 + 32^n/2 + 36^n/2 + 48^n/2 - 24^n.
EXAMPLE
Square array T(n,k) (n, k >= 1) begins:
1, 0, 0, 0, 0, ...
1, 4, 45, 816, 20225, ...
1, 24, 2268, 461056, 160977375, ...
1, 112, 76221, 152978176, 673315202500, ...
1, 480, 2245320, 43083161600, 2331513459843750, ...
1, 1984, 62858025, 11442561314816, 7570813415735296875, ...
...
PROG
(PARI) /* The recurrence for V(n, k) is due to Valery A. Liskovets. See his 1971 paper. A second program that implements the formula above involving the compositions of k appears in the links and was written by Michel Marcus. */
V(n, k) = k^(n*k) - sum(t=1, k-1, binomial(k, t)*k^(n*(k-t))*V(n, t));
T(n, k) = V(n, k)/k!
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Petros Hadjicostas, Mar 04 2021
STATUS
approved