A304394 -id:A304394 - cp's OEIS frontend

A107668 Column 0 of triangle A107667.

1, 4, 45, 816, 20225, 632700, 23836540, 1048592640, 52696514169, 2976295383100, 186548057815801, 12845016620629488, 963644465255618276, 78224633235142116240, 6830914919397129328500, 638477522900795994967040, 63599377775480137499907561, 6725771848938288950491594140

Offset: 0

Paul D. Hanna, Jun 07 2005

nonn

Shift right of column 1 of triangle A107670, which is the matrix square of triangle A107667.
The o.g.f. A(x) = Sum_{m >= 0} a(m)*x^m is such that, for each integer n > 0, the coefficient of x^n in the expansion of exp(n^2*x)*(1 - x*A(x)) is equal to 0.
Given the o.g.f. A(x), the o.g.f. of A304322 equals 1/(1 - x*A(x)).
Also, a(n) is the number of 2-symbol Turing Machine state graphs in which n states are reached in canonical order. A canonical TM state graph lists for each state 1..n, and each of 2 symbols 0,1 in lexicographic order, a next state that is either the halt state, an already listed state, or the least unlisted state, as in the Haskell program below. Multiplied by 4^(2*n), this gives a much smaller number of TMs to be considered for the Busy Beaver function than given by A052200. - John Tromp, Oct 15 2024

			O.g.f.: A(x) = 1 + 4*x + 45*x^2 + 816*x^3 + 20225*x^4 + 632700*x^5 + 23836540*x^6 + 1048592640*x^7 + 52696514169*x^8 + 2976295383100*x^9 + ...
From _Petros Hadjicostas_, Mar 10 2021: (Start)
We illustrate the above formula for a(n) with the compositions of n + 1 for n = 2.
The compositions of n + 1 = 3 are 3, 1 + 2, 2 + 1, and 1 + 1 + 1.  Thus the above sum has four terms with (r = 1, s_1 = 3), (r = 2, s_1 = 1, s_2 = 2), (r = 2, s_1 = 2, s_2 = 1), and (r = 3, s_1 = s_2 = s_3 = 1).
The value of the denominator Product_{j=1..r} s_j! for these four terms is 6, 2, 2, and 1, respectively.
The value of the numerator Product_{j=1..r} (Sum_{i=1..j} s_i)^(2*s_j) for these four terms is 729, 81, 144, and 36.
Thus a(2) = 729/6 - 81/2 - 144/2 + 36/1 = 45. (End)

Vaclav Kotesovec, Table of n, a(n) for n = 0..300

Cf. A107667, A107669, A107670, A052200.

Cf. A304322, A107675, A304394, A304395, A342202.

-- using program for A107667
a107668 = map head a where a = [[sum [a!!n!!i * a!!i!!(k+1) | i<-[k+1..n]] | k <- [0..n-1]] ++ [fromIntegral n+1] | n <- [0..]] -- John Tromp, Oct 21 2024

-- low memory version
a107668 n = (foldl' (\r i->sum r`seq`listArray(0,n)(0:[if i+1<2*j then 0 else r!j*(n+2-j)+r!(j-1)|j<-[1..n]])) (listArray(0,n)(0:repeat 1)) [1..2*n])!n -- John Tromp, Oct 15 2024

{a(n)=local(A);if(n==0,n+1,A=(n+1)*x+x*O(x^n); for(k=0,n,A+=polcoeff(A,k)*x^k*(n+1-prod(i=0,k,1+(i-n-1)*x))); polcoeff(A,n))}
for(n=0,30, print1(a(n),", "))

/* From formula: [x^n] exp( n^2*x ) * (1 - x*A(x)) = 0 */
{a(n) = my(A=[1]); for(i=0, n, A=concat(A, 0); m=#A; A[m] = Vec( exp(x*m^2 +x^2*O(x^m)) * (1 - x*Ser(A)) )[m+1] ); A[n+1]}
for(n=0,25, print1( a(n),", ")) \\ Paul D. Hanna, May 12 2018

/* From Recurrence: */
{a(n) = if(n==0,1, (n+1)^(2*n+2)/(n+1)! - sum(k=1,n, (n+1)^(2*k)/k! * a(n-k) ))}
for(n=0,25, print1( a(n),", ")) \\ Paul D. Hanna, May 12 2018

O.g.f. A(x) satisfies: [x^n] exp( n^2*x ) * (1 - x*A(x)) = 0 for n > 0. - Paul D. Hanna, May 12 2018
a(n) = (n+1)^2 * A107669(n).
a(n) = (n+1)^(2*n+2)/(n+1)! - Sum_{k=1..n} (n+1)^(2*k)/k! * a(n-k) for n > 0 with a(0) = 1. - Paul D. Hanna, May 12 2018
a(n) = A342202(2,n+1) = Sum_{r=1..(n+1)} (-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)^(2*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 = n+1. (Thus the second sum is over all ordered partitions (i.e., compositions) of n+1. See Michel Marcus's PARI program in A342202.) - Petros Hadjicostas, Mar 10 2021
a(n) ~ sqrt(1-c) * 2^(2*n + 3/2) * n^(n + 1/2) / (sqrt(Pi) * exp(n) * c^(n+1) * (2-c)^(n+1)), where c = -A226775 = -LambertW(-2*exp(-2)). - Vaclav Kotesovec, Oct 18 2024

A304324 O.g.f. A(x) satisfies: [x^n] exp( n^4 * x ) / A(x) = 0 for n>0.

Original entry on oeis.org

1, 1, 113, 76446, 153143499, 673638499100, 5510097691767062, 75312181798660695788, 1595682359653020033714019, 49564410138113345565513815041, 2161639124039437373346491749452440, 127889301139607880711208251726358504898, 9979766671875039854419652569806336108694074

Offset: 0

Paul D. Hanna, May 11 2018

nonn

It is conjectured that the coefficients of o.g.f. A(x) consist entirely of integers.
Equals row 4 of table A304320.
O.g.f. A(x) = 1/(1 - x*B(x)), where B(x) is the o.g.f. of A304394.
Logarithmic derivative of o.g.f. A(x), A'(x)/A(x), equals o.g.f. of A304314.
Conjecture: given o.g.f. A(x), the coefficient of x^n in A'(x)/A(x) is the number of connected n-state finite automata with 4 inputs.

			O.g.f.: A(x) = 1 + x + 113*x^2 + 76446*x^3 + 153143499*x^4 + 673638499100*x^5 + 5510097691767062*x^6 + 75312181798660695788*x^7 + ...
ILLUSTRATION OF DEFINITION.
The table of coefficients of x^k/k! in exp(n^4*x) / A(x) begins:
n=0: [1, -1, -224, -457326, -3671476224, -80797824300000, ...];
n=1: [1, 0, -225, -458000, -3673306875, -80816186256624, ...];
n=2: [1, 15, 0, -464750, -3701040000, -81092721606624, ...];
n=3: [1, 80, 6175, 0, -3787546875, -82312696206624, ...];
n=4: [1, 255, 64800, 15951250, 0, -84756571206624, ...];
n=5: [1, 624, 389151, 242091424, 146271536901, 0, ...];
n=6: [1, 1295, 1676800, 2170415250, 2804103120000, 3524906587193376, 0, ...]; ...
in which the main diagonal is all zeros after the initial term, illustrating that [x^n] exp( n^4*x ) / A(x) = 0 for n>=0.
LOGARITHMIC DERIVATIVE.
The logarithmic derivative of A(x) yields the o.g.f. of A304314:
A'(x)/A(x) = 1 + 225*x + 229000*x^2 + 612243125*x^3 + 3367384031526*x^4 + 33056423981177346*x^5 + 527146092112494861420*x^6 + ... + A304314(n)*x^n + ...
INVERT TRANSFORM.
1/A(x) = 1 - x*B(x), where B(x) is the o.g.f. of A304394:
B(x) = 1 + 112*x + 76221*x^2 + 152978176*x^3 + 673315202500*x^4 + 5508710472669120*x^5 + 75300988091046198131*x^6 + ... + A304394(n)*x^n + ...

Paul D. Hanna, Table of n, a(n) for n = 0..200

Cf. A304320, A304314, A304321, A304322, A304323, A304325.

Cf. A304394.

{a(n) = my(A=[1]); for(i=1, n, A=concat(A, 0); m=#A; A[m] = Vec( exp(x*(m-1)^4 +x*O(x^m)) / Ser(A) )[m] ); A[n+1]}
for(n=0,25, print1( a(n),", "))

a(n) ~ sqrt(1-c) * 4^(4*n) * n^(3*n - 1/2) / (sqrt(2*Pi) * c^n * (4-c)^(3*n) * exp(3*n)), where c = -LambertW(-4*exp(-4)). - Vaclav Kotesovec, Aug 31 2020

A107675 Column 0 of triangle A107674.

Original entry on oeis.org

1, 24, 2268, 461056, 160977375, 85624508376, 64363893844726, 64928246784463872, 84623205378726331245, 138408056280920732755000, 277597038523589348539241112, 670011760601512512626484887040

Offset: 0

Paul D. Hanna, Jun 07 2005

nonn

The o.g.f. A(x) = Sum_{m >= 0} a(m)*x^m is such that, for each integer n > 0, the coefficient of x^n in the expansion of exp(n^3*x)*(1 - x*A(x)) is equal to 0.

Given the o.g.f. A(x), the o.g.f. of A304323 equals 1/(1 - x*A(x)).

			O.g.f.: A(x) = 1 + 24*x + 2268*x^2 + 461056*x^3 + 160977375*x^4 + 85624508376*x^5 + 64363893844726*x^6 + 64928246784463872*x^7 + ...

Cf. A107671, A107674, A107676.

Cf. A304323, A107668, A304394, A304395, A342202.

{a(n)=local(P=matrix(n+1,n+1,r,c,if(r>=c,(r^3)^(r-c)/(r-c)!)), D=matrix(n+1,n+1,r,c,if(r==c,r)));(P^-1*D^2*P)[n+1,1]}
for(n=0,20, print1(a(n),", "))

/* From formula: [x^n] exp( n^3*x ) * (1 - x*A(x)) = 0 */
{a(n) = my(A=[1]); for(i=0, n, A=concat(A, 0); m=#A; A[m] = Vec( exp(x*m^3 +x^2*O(x^m)) * (1 - x*Ser(A)) )[m+1] ); A[n+1]}
for(n=0, 25, print1( a(n), ", ")) \\ Paul D. Hanna, May 12 2018

/* From Recurrence: */
{a(n) = if(n==0,1, (n+1)^(3*n+3)/(n+1)! - sum(k=1,n, (n+1)^(3*k)/k! * a(n-k) ))}
for(n=0,25, print1( a(n),", ")) \\ Paul D. Hanna, May 12 2018

O.g.f. A(x) satisfies: [x^n] exp(n^3*x) * (1 - x*A(x)) = 0 for n > 0. - Paul D. Hanna, May 12 2018
a(n) = (n+1)^(3*n+3)/(n+1)! - Sum_{k=1..n} (n+1)^(3*k)/k! * a(n-k) for n > 0 with a(0) = 1. - Paul D. Hanna, May 12 2018
a(n) = A342202(3,n+1) = Sum_{r=1..(n+1)} (-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)^(3*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 = n+1. (Thus the second sum is over all compositions of n+1. See Michel Marcus's PARI program in A342202.) - Petros Hadjicostas, Mar 10 2021

A304395 O.g.f. A(x) satisfies: [x^n] exp( n^5 * x ) * (1 - x*A(x)) = 0 for n > 0.

Original entry on oeis.org

1, 480, 2245320, 43083161600, 2331513459843750, 287128730182879382976, 69929145078323834449039740, 30496052356323314014140611297280, 22113924320024426907851753695581691875, 25177421842925471123473548283955430812500000, 42994775028354266041451477298870703788676694998956, 106089234738948935762581435147478647028049918327743508480

Offset: 0

Paul D. Hanna, May 12 2018

nonn

The o.g.f. A(x) = Sum_{m >= 0} a(m)*x^m is such that, for each integer n > 0, the coefficient of x^n in the expansion of exp(n^5*x) * (1 - x*A(x)) is equal to 0.

			O.g.f.: A(x) = 1 + 480*x + 2245320*x^2 + 43083161600*x^3 + 2331513459843750*x^4 + 287128730182879382976*x^5 + 69929145078323834449039740*x^6 + ...

Cf. A304325, A304397, A107668, A107675, A304394.

INVERT transform of A304325.

/* From formula: [x^n] exp( n^5*x ) * (1 - x*A(x)) = 0 */
{a(n) = my(A=[1]); for(i=0, n, A=concat(A, 0); m=#A; A[m] = Vec( exp(x*m^5 +x^2*O(x^m)) * (1 - x*Ser(A)) )[m+1] ); A[n+1]}
for(n=0, 20, print1( a(n), ", "))

a(n) = (n+1)^(5*n+5)/(n+1)! - Sum_{k=1..n} (n+1)^(5*k)/k! * a(n-k) for n > 0 with a(0) = 1.

a(n) = A342202(5,n+1) = Sum_{r=1..(n+1)} (-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)^(5*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 = n+1. (Thus, the second sum is over all compositions of n+1. See Michel Marcus's PARI program in A342202.) - Petros Hadjicostas, Mar 10 2021

A342202 T(n,k) = V(n,k)/k!, where V(n,k) = k^(nk) - 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.

Original entry on oeis.org

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

Petros Hadjicostas, Mar 04 2021

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.

			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, ...
  ...

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.

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).

/* 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!

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.

cp's OEIS Frontend

A304396 a(n) = A304394(n) / (n+1)^4.

Views

Author

Keywords

Crossrefs

Programs

PARI

Formula

A107668 Column 0 of triangle A107667.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Haskell

PARI

PARI

PARI

Formula

A304324 O.g.f. A(x) satisfies: [x^n] exp( n^4 * x ) / A(x) = 0 for n>0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A107675 Column 0 of triangle A107674.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

PARI

Formula

A304395 O.g.f. A(x) satisfies: [x^n] exp( n^5 * x ) * (1 - x*A(x)) = 0 for n > 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A342202 T(n,k) = V(n,k)/k!, where V(n,k) = k^(nk) - 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.