A107668 - OEIS

%I #58 Jun 07 2026 18:46:38

%S 1,4,45,816,20225,632700,23836540,1048592640,52696514169,

%T 2976295383100,186548057815801,12845016620629488,963644465255618276,

%U 78224633235142116240,6830914919397129328500,638477522900795994967040,63599377775480137499907561,6725771848938288950491594140

%N Column 0 of triangle A107667.

%C Shift right of column 1 of triangle A107670, which is the matrix square of triangle A107667.

%C 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.

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

%C 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

%H Vaclav Kotesovec, <a href="/A107668/b107668.txt">Table of n, a(n) for n = 0..300</a>

%H John Tromp, <a href="https://doi.org/10.20944/preprints202603.1897.v1">The Largest Number Representable in 64 Bits</a>, Preprints.org (2026). See p. 8.

%F 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

%F a(n) = (n+1)^2 * A107669(n).

%F 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

%F 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

%F 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

%F Conjecture: a(n) = (n+1) * P(n+1, n+1) where P(n, k) = P(n-1, k) + n * P(n, k-1) for 1 < k < n with P(n, 1) = 1, P(n, n) = n * P(n, n-1). - _Mikhail Kurkov_, Jun 01 2026

%e 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 + ...

%e From _Petros Hadjicostas_, Mar 10 2021: (Start)

%e We illustrate the above formula for a(n) with the compositions of n + 1 for n = 2.

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

%e The value of the denominator Product_{j=1..r} s_j! for these four terms is 6, 2, 2, and 1, respectively.

%e 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.

%e Thus a(2) = 729/6 - 81/2 - 144/2 + 36/1 = 45. (End)

%o (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))}

%o for(n=0,30, print1(a(n),", "))

%o (PARI) /* From formula: [x^n] exp( n^2*x ) * (1 - x*A(x)) = 0 */

%o {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]}

%o for(n=0,25, print1( a(n),", ")) \\ _Paul D. Hanna_, May 12 2018

%o (PARI) /* From Recurrence: */

%o {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) ))}

%o for(n=0,25, print1( a(n),", ")) \\ _Paul D. Hanna_, May 12 2018

%o (Haskell) -- using program for A107667

%o 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

%o (Haskell) -- low memory version

%o 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

%Y Cf. A107667, A107669, A107670, A052200.

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

%K nonn

%O 0,2

%A _Paul D. Hanna_, Jun 07 2005