A342202 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.
1, 1, 0, 1, 4, 0, 1, 24, 45, 0, 1, 112, 2268, 816, 0, 1, 480, 76221, 461056, 20225, 0, 1, 1984, 2245320, 152978176, 160977375, 632700, 0, 1, 8064, 62858025, 43083161600, 673315202500, 85624508376, 23836540, 0, 1, 32512, 1723364748, 11442561314816, 2331513459843750, 5508710472669120, 64363893844726, 1048592640, 0
Offset: 1
Examples
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, ... ...
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.
Crossrefs
Programs
-
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!
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.
Comments