login
A107668
Column 0 of triangle A107667.
10
1, 4, 45, 816, 20225, 632700, 23836540, 1048592640, 52696514169, 2976295383100, 186548057815801, 12845016620629488, 963644465255618276, 78224633235142116240, 6830914919397129328500, 638477522900795994967040, 63599377775480137499907561, 6725771848938288950491594140
OFFSET
0,2
COMMENTS
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
LINKS
FORMULA
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
EXAMPLE
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)
PROG
(PARI) {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), ", "))
(PARI) /* 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
(PARI) /* 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
(Haskell) -- 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
(Haskell) -- 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
KEYWORD
nonn,changed
AUTHOR
Paul D. Hanna, Jun 07 2005
STATUS
approved