|
%I #69 Mar 11 2021 17:43:42
%S 1,1,0,1,4,0,1,24,45,0,1,112,2268,816,0,1,480,76221,461056,20225,0,1,
%T 1984,2245320,152978176,160977375,632700,0,1,8064,62858025,
%U 43083161600,673315202500,85624508376,23836540,0,1,32512,1723364748,11442561314816,2331513459843750,5508710472669120,64363893844726,1048592640,0
%N T(n,k) = V(n,k)/k!, where V(n,k) = k^(n*k) - Sum_{t=1..k-1} binomial(k,t)*k^(n*(k-t))*V(n,t) for n, k >= 1; square array T read by upwards antidiagonals.
%C 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.
%C 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.
%C 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).
%C 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.
%H Michael A. Harrison, <a href="https://doi.org/10.4153/CJM-1965-010-9">A census of finite automata</a>, Canadian Journal of Mathematics, 17 (1965), 100-113.
%H Valery A. Liskovets [ Liskovec ], <a href="https://www.researchgate.net/publication/268532943_Enumeration_of_non-isomorphic_strongly_connected_automata">Enumeration of nonisomorphic strongly connected automata</a>, (in Russian); Vesti Akad. Nauk. Belarus. SSR, Ser. Phys.-Mat., No. 3, 1971, pp. 26-30, esp. p. 30 (Math. Rev. 46 #5081; <a href="https://www.zbmath.org/?q=an%3A0224.94053">Zentralblatt 224 #94053</a>).
%H Valery A. Liskovets [ Liskovec ], <a href="https://www.researchgate.net/publication/246994823_ON_A_GENERAL_ENUMERATIVE_SCHEME_FOR_LABELED_GRAPHS">A general enumeration scheme for labeled graphs</a>, (in Russian); Dokl. Akad. Nauk. Belarus. SSR, Vol. 21, No. 6 (1977), pp. 496-499 (Math. Rev. 58 #21797; <a href="https://www.zbmath.org/?q=an%3A0412.05052">Zentralblatt 412 #05052</a>).
%H Michel Marcus, <a href="/A342202/a342202.txt">PARI program that implements the formula for T(n,k) that involves compositions of k</a>, 2021.
%H Robert W. Robinson, <a href="https://oeis.org/A006689/a006689_1.pdf">Counting strongly connected finite automata</a>, in: Graph Theory with Applications to Graph Theory and Computer Science, Wiley, 1985, pp. 671-685.
%F T(n,k) = k^(n*k)/k! - Sum_{s=1..k-1} k^(n*s)/s! * T(n,k-s).
%F 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.)
%F 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.)
%F 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.)
%F T(n,k=1) = 1 and T(n,k=2) = 2^n*(2^(n-1) - 1) = A059153(n-2) (with A059153(-1) := 0).
%F T(n,k=3) = (27^n - 3*9^n - 3*12^n)/6 + 6^n.
%F 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.
%e Square array T(n,k) (n, k >= 1) begins:
%e 1, 0, 0, 0, 0, ...
%e 1, 4, 45, 816, 20225, ...
%e 1, 24, 2268, 461056, 160977375, ...
%e 1, 112, 76221, 152978176, 673315202500, ...
%e 1, 480, 2245320, 43083161600, 2331513459843750, ...
%e 1, 1984, 62858025, 11442561314816, 7570813415735296875, ...
%e ...
%o (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_. */
%o V(n,k) = k^(n*k) - sum(t=1, k-1, binomial(k, t)*k^(n*(k-t))*V(n,t));
%o T(n,k) = V(n,k)/k!
%Y Cf. A027834, A027835, A059153 (shifted column 2), A342405 (column 3).
%Y Shifted rows: A000007 (row 1), A107668 (row 2), A107675 (row 3), A304394 (row 4), A304395 (row 5).
%K nonn,tabl
%O 1,5
%A _Petros Hadjicostas_, Mar 04 2021
|
