A107668 -id:A107668 - cp's OEIS frontend

A107669 a(n) = A107668(n)/(n+1)^2.

1, 1, 5, 51, 809, 17575, 486460, 16384260, 650574249, 29762953831, 1541719486081, 89201504309927, 5702038255950404, 399105271607867940, 30359621863987241460, 2494052823831234355340, 220067051126228849480649

Offset: 0

Paul D. Hanna, Jun 07 2005

nonn

Cf. A107667, A107668, A107670.

{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)/(n+1)^2)}

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

Original entry on oeis.org

1, 1, 5, 54, 935, 22417, 685592, 25431764, 1106630687, 55174867339, 3097872254493, 193283918695494, 13260815963831108, 991928912663646012, 80325879518096889760, 7000127337189146831092, 653156403671376068448047, 64963788042207845593775999, 6861040250464949653809027311, 766815367797924824316405828466, 90417908118862070187113849296815

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 2 of table A304320.
O.g.f. A(x) = 1/(1 - x*B(x)), where B(x) is the o.g.f. of A107668.
Logarithmic derivative of o.g.f. A(x), A'(x)/A(x), equals o.g.f. of A304312.
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 2 inputs (A006691).

			O.g.f.: A(x) = 1 + x + 5*x^2 + 54*x^3 + 935*x^4 + 22417*x^5 + 685592*x^6 + 25431764*x^7 + 1106630687*x^8 + 55174867339*x^9 + 3097872254493*x^10 + ...
ILLUSTRATION OF DEFINITION.
The table of coefficients of x^k/k! in exp(n^2*x) / A(x) begins:
n=0: [1, -1, -8, -270, -19584, -2427000, -455544000, -120136161600, ...];
n=1: [1, 0, -9, -296, -20715, -2527704, -470405285, -123376631664, ...];
n=2: [1, 3, 0, -350, -24672, -2867256, -518870528, -133753337280, ...];
n=3: [1, 8, 55, 0, -29547, -3559056, -614943333, -153534305160, ...];
n=4: [1, 15, 216, 2674, 0, -4291704, -783235520, -187656684864, ...];
n=5: [1, 24, 567, 12880, 251541, 0, -948897125, -243358236600, ...];
n=6: [1, 35, 1216, 41634, 1372320, 38884296, 0, -295870371264, ...];
n=7: [1, 48, 2295, 109000, 5106453, 230531544, 8944955227, 0, ...];
n=8: [1, 63, 3960, 248050, 15443328, 949131144, 56257429312, 2865412167360, 0, ...]; ...
in which the main diagonal is all zeros after the initial term, illustrating that [x^n] exp( n^2*x ) / A(x) = 0 for n>=0.
LOGARITHMIC DERIVATIVE.
The logarithmic derivative of A(x) yields the o.g.f. of A304312:
A'(x)/A(x) = 1 + 9*x + 148*x^2 + 3493*x^3 + 106431*x^4 + 3950832*x^5 + 172325014*x^6 + 8617033285*x^7 + 485267003023*x^8 + 30363691715629*x^9 + ... + A304312(n)*x^n +...
INVERT TRANSFORM.
1/A(x) = 1 - x*B(x), where B(x) is the o.g.f. of A107668:
B(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 + ... + A107668(n)*x^n + ...

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

Cf. A304320, A304312, A304321, A304323, A304324, A304325.

Cf. A006691, A107668.

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

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

A052200 Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines.

Original entry on oeis.org

1, 64, 20736, 16777216, 25600000000, 63403380965376, 232218265089212416, 1180591620717411303424, 7958661109946400884391936, 68719476736000000000000000000, 739696442014594807059393047166976, 9711967541295580042210555933809967104, 152784834199652075368661148843397208866816

Offset: 0

Michael Somos, Jan 28 2000

T in T_(n, k) is a Turing machine with n states and k symbols;
States q, q+ in set Q_n of n distinct states (plus the Halt state;)
Symbols s, s+ in set S_k of k distinct symbols (0 as the blank symbol;)
Shift direction d+ in {LEFT, RIGHT} (NONE is excluded here;)
+ suffix meaning next and q+ = f(q, s), s+ = g(q, s), d+ = h(q, s).
This sequence is computable. On the other hand, the busy beaver numbers are noncomputable, found only by examining each of the many n-state Turing machine programs' halting. - Michael Joseph Halm, Apr 29 2003
From Daniel Forgues, Jun 06 2011: (Start)
RE: Busy beaver halting Turing machines:
H in H_(n, k) is a halting* Turing machine with n states and k symbols;
* (on a blank tape, all 0's, as input)
sigma(H) is the number of non-blank symbols left on the tape by H;
s(H) is the number of steps (or shifts in our case) taken by H;
Sigma(n, k) = max {sigma(H) : H is a halting Turing machine with n states and k symbols}
S(n, k) = max {s(H) : H is a halting Turing machine with n states and k symbols}
Cf. A028444 for Sigma(n, 2), A060843 for S(n, 2). (End)
This sequence also counts machines with unreachable states, and all (up to (n-1)!) permutations of non-start states, which don't affect behavior. In contrast, A107668 only counts state graphs reaching all n states in canonical order. - John Tromp, Oct 17 2024

			a(1) = 64 = (4*1+4)^(2*1) = 8^2.

J. P. Jones, Recursive undecidability - an exposition, Amer. Math. Monthly, 81 (1974), 724-738.
Michael Somos, The Busy Beaver Problem
OEIS Wiki, Busy Beaver numbers
Index entries for sequences related to Busy Beaver problem

Cf. A028444, A004147, A060843, A107668.

A052200[n_]:=(4(n+1))^(2n); Array[A052200,20,0] (* Paolo Xausa, May 21 2023 *)

a(n) = (4*(n+1))^(2*n).

Entry revised by N. J. A. Sloane, Feb 08 2007

Edited by Daniel Forgues, Mar 25 2010

A107667 Triangular matrix T, read by rows, that satisfies: T = D + SHIFT_LEFT(T^2) where SHIFT_LEFT shifts each row 1 place to the left and D is the diagonal matrix {1, 2, 3, ...}.

Original entry on oeis.org

1, 4, 2, 45, 9, 3, 816, 112, 16, 4, 20225, 2200, 225, 25, 5, 632700, 58176, 4860, 396, 36, 6, 23836540, 1920163, 138817, 9408, 637, 49, 7, 1048592640, 75683648, 4886464, 290816, 16576, 960, 64, 8, 52696514169, 3460349970, 203451912, 10948203, 553473

Offset: 0

Paul D. Hanna, Jun 07 2005

			Reverse of rows form the initial terms of g.f.s below.
Row n=0: 1 = 1*(1-x) + 1*x*(1-x) + ...
Row n=1: 2 = 2*(1-2*x) + 4*x*(1-2*x)*(1-x) + 12*x^2*(1-2*x)*(1-x) + ...
Row n=2: 3 = 3*(1-3*x) + 9*x*(1-3*x)*(1-2*x)
           + 45*x^2*(1-3*x)*(1-2*x)*(1-x)
           + 216*x^3*(1-3*x)*(1-2*x)*(1-x) + ...
Row n=3: 4 = 4*(1-4*x) + 16*x*(1-4*x)*(1-3*x)
           + 112*x^2*(1-4*x)*(1-3*x)*(1-2*x)
           + 816*x^3*(1-4*x)*(1-3*x)*(1-2*x)*(1-x)
           + 5248*x^4*(1-4*x)*(1-3*x)*(1-2*x)*(1-x) + ...
Triangle T begins:
           1;
           4,        2;
          45,        9,       3;
         816,      112,      16,      4;
       20225,     2200,     225,     25,     5;
      632700,    58176,    4860,    396,    36,   6;
    23836540,  1920163,  138817,   9408,   637,  49,  7;
  1048592640, 75683648, 4886464, 290816, 16576, 960, 64, 8;
  ...
The matrix square T^2 shifts each row right 1 place, dropping the diagonal D and putting A006689 in column 0:
          1;
         12,        4;
        216,       45,       9;
       5248,      816,     112,     16;
     160675,    20225,    2200,    225,   25;
    5931540,   632700,   58176,   4860,  396,  36;
  256182290, 23836540, 1920163, 138817, 9408, 637, 49;
  ...

Cf. A006689, A107668 (column 0), A107669, A107670 (matrix square).

a = [[sum [a!!n!!i * a!!i!!(k+1) | i<-[k+1..n]] | k <- [0..n-1]] ++ [fromIntegral n+1] | n <- [0..]]

{T(n,k)=local(P=matrix(n+1,n+1,r,c,if(r>=c,(r^2)^(r-c)/(r-c)!)), D=matrix(n+1,n+1,r,c,if(r==c,r)));if(n>=k,(P^-1*D*P)[n+1,k+1])}

Matrix diagonalization method: define the triangular matrix P by P(n, k) = ((n+1)^2)^(n-k)/(n-k)! for n >=k >= 0 and the diagonal matrix D by D(n, n) = n+1 for n >= 0; then T is given by T = P^-1*D*P.

Rows read in reverse form the initial terms of the g.f.: (n+1) = Sum_{k>=0} T(n, n-k) * x^k * Product_{j=0..k} (1-(n+1-j)*x) = T(n, n)*(1-(n+1)*x) + T(n, n-1)*x*(1-(n+1)*x)*(1-n*x) + T(n, n-2)*x^2*(1-(n+1)*x)*(1-n*x)*(1-(n-1)*x) + ... [Corrected by Petros Hadjicostas, Mar 11 2021]

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

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

Original entry on oeis.org

1, 112, 76221, 152978176, 673315202500, 5508710472669120, 75300988091046198131, 1595530380622638283804672, 49561200934127182294698009969, 2161539625780059763174286300310000, 127884966535158110582342524738392563401, 9979510403062963314615799917574094659938048, 1003426348756281631241586585232930123009989117616

Offset: 0

Paul D. Hanna, May 12 2018

nonn

INVERT transform of A304324.

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^4 * x) * (1 - x*A(x)) = 0 is equal to 0.

			O.g.f.: A(x) = 1 + 112*x + 76221*x^2 + 152978176*x^3 + 673315202500*x^4 + 5508710472669120*x^5 + 75300988091046198131*x^6 + ...

Cf. A304324, A304396, A107668, A107675, A304395, A342202.

/* From formula: [x^n] exp( n^4*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^4 +x^2*O(x^m)) * (1 - x*Ser(A)) )[m+1] ); A[n+1]}
for(n=0, 25, print1( a(n), ", "))

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

a(n) = A342202(4,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)^(4*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.

A107670 Matrix square of triangle A107667.

Original entry on oeis.org

1, 12, 4, 216, 45, 9, 5248, 816, 112, 16, 160675, 20225, 2200, 225, 25, 5931540, 632700, 58176, 4860, 396, 36, 256182290, 23836540, 1920163, 138817, 9408, 637, 49, 12665445248, 1048592640, 75683648, 4886464, 290816, 16576, 960, 64

Offset: 0

Paul D. Hanna, Jun 07 2005

Column 0 is A006689. See triangle A107667 for more formulas.

			Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
          1;
         12,        4;
        216,       45,       9;
       5248,      816,     112,     16;
     160675,    20225,    2200,    225,   25;
    5931540,   632700,   58176,   4860,  396,  36;
  256182290, 23836540, 1920163, 138817, 9408, 637, 49;
  ...

Cf. A107667, A107668, A107669, A006689 (column 0).

{T(n,k)=local(P=matrix(n+1,n+1,r,c,if(r>=c,(r^2)^(r-c)/(r-c)!)), D=matrix(n+1,n+1,r,c,if(r==c,r)));if(n>=k,(P^-1*D^2*P)[n+1,k+1])}

Matrix diagonalization method: define the triangular matrix P by P(n, k) = ((n+1)^2)^(n-k)/(n-k)! for n >= k >= 0 and the diagonal matrix D by D(n, n) = n+1 for n >= 0; then T is given by T = P^-1*D^2*P.

A337805 Lazy Beaver Problem: a(n) is the smallest positive number of steps a(n) such that no n-state Turing machine halts in exactly a(n) steps on an initially blank tape.

Original entry on oeis.org

2, 7, 22, 72, 427

Offset: 1

Zachary Vance, Sep 23 2020

This sequence and the Busy Beaver (A060843) problem are closely related. Turing machines and the number of steps taken by a Turing machine on an initially blank tape are defined in A060843.
This sequence is computable, while the Busy Beaver problem is uncomputable.
a(n) - 1 <= BB(n), where BB(n) = A060843(n).
a(n) - 1 <= A107668 * 4^(2n), the number of uniquely behaving n-state Turing machines with 2 symbols, by the pigeonhole principle.

			For n = 2, there exist 2-state Turing machines which halt in exactly {1, 2, 3, 4, 5, 6} steps (and for no other number of steps) given an initially empty input tape. a(2) = 7 is defined as the lowest positive integer not present in that set of possible step lengths.

Scott Aaronson, The Busy Beaver Frontier, 2020.
Scott Aaronson, The Busy Beaver Frontier (blog post)

Known upper bounds of a(n) - 1 are A028444, A004147, and A141475.

cp's OEIS Frontend

A107669 a(n) = A107668(n)/(n+1)^2.

Views

Author

Keywords

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A052200 Number of n-state, 2-symbol, d+ in {LEFT, RIGHT}, 5-tuple (q, s, q+, s+, d+) (halting or not) Turing machines.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A107667 Triangular matrix T, read by rows, that satisfies: T = D + SHIFT_LEFT(T^2) where SHIFT_LEFT shifts each row 1 place to the left and D is the diagonal matrix {1, 2, 3, ...}.

Views

Author

Keywords

Examples

Crossrefs

Programs

Haskell

PARI

Formula

A107675 Column 0 of triangle A107674.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

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

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.