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

Author

Petros Hadjicostas, Mar 04 2021

Keywords

• nonn
• tabl

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.

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

Cf. A027834, A027835, A059153 (shifted column 2), A342405 (column 3).

Shifted rows: A000007 (row 1), A107668 (row 2), A107675 (row 3), A304394 (row 4), A304395 (row 5).

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=1) = 1 and T(n,k=2) = 2^n*(2^(n-1) - 1) = A059153(n-2) (with A059153(-1) := 0).

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.