A107667 -id:A107667 - 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

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.

A006689 Number of deterministic, completely-defined, initially-connected finite automata with 2 inputs and n unlabeled states.

Original entry on oeis.org

1, 12, 216, 5248, 160675, 5931540, 256182290, 12665445248, 705068085303, 43631250229700, 2970581345516818, 220642839342906336, 17753181687544516980, 1538156947936524172656, 142767837727544113783650, 14132742269814671677890048, 1486239549269418316509918111, 165468157149718534883789004804

Offset: 1

N. J. A. Sloane

a(n) is divisible by n^2, see A082166. These automata have no nontrivial automorphisms (by states).
Equals the first column of triangle A107670, which is the matrix square of triangle A107667. As a lower triangular matrix T, A107667 satisfies: T = D + SHIFT_LEFT(T^2) where SHIFT_LEFT shifts each row 1 place left and D is the diagonal matrix [1,2,3,...]. - Paul D. Hanna, May 19 2005
A complete initially connected deterministic finite automaton (icdfa) with n states in an alphabet of k symbols can be represented by a special string of {0,...,n-1}^* with length kn. In that string, let f_i be the index of the first occurrence of state i (used in the formula). - Nelma Moreira, Jul 31 2005

			a(2) = 12 since the following transition diagrams represent all twelve initially connected automata with two input letters x and y and two states 1 (initial) and 2: 1==x,y==>2==>, 1--x-->2==>, 1--y-->2==>, 1--y-->1 1--x-->1 where the transitions from state 2 are specified arbitrary (4 different possibilities in every case).

R. Bacher and C. Reutenauer, The number of right ideals of given codimension over a finite field, in Noncommutative Birational Geometry, Representations and Combinatorics, edited by Arkady. Berenstein and Vladimir. Retakha, Contemporary Mathematics, Vol. 592, 2013.
V. A. Liskovets, The number of initially connected automata, Kibernetika, (Kiev), No3 (1969), 16-19; Engl. transl.: Cybernetics, v.4 (1969), 259-262.
R. Reis, N. Moreira and M. Almeida, On the Representation of Finite Automata, in Proocedings of 7th Int. Workshop on Descriptional Complexity of Formal Systems (DCFS05) Jun 30, 2005, Como, Italy, page 269-276
Robert W. Robinson, Counting strongly connected finite automata, pages 671-685 in "Graph theory with applications to algorithms and computer science." Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4-8, 1984. Edited by Y. Alavi, G. Chartrand, L. Lesniak [L. M. Lesniak-Foster], D. R. Lick and C. E. Wall. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1985. xv+810 pp. ISBN: 0-471-81635-3; Math Review MR0812651 (86g:05026).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. Almeida, N. Moreira and R. Reis. On the Representation of Finite Automata, Technical Report DCC-2005-04, DCC - FC & LIACC, Universidade do Porto, April, 2005.
M. Almeida, N. Moreira, and R. Reis, Enumeration and generation with a string automata representation, Theor. Comp. Sci. 387 (2007) 93-102, B(k=2,n)
E. Lebensztayn, A large deviations principle for the Maki-Thompson rumour model, arXiv preprint arXiv:1411.5614 [math.PR], 2014-2015.
V. A. Liskovets, The number of initially connected automata, Kibernetika, (Kiev), No3 (1969), 16-19; Engl. transl.: Cybernetics, v.4 (1969), 259-262.
V. A. Liskovets, Exact enumeration of acyclic automata, Proc. 15th Conf. "Formal Power Series and Algebr. Combin. (FPSAC'03)", 2003.
V. A. Liskovets, Exact enumeration of acyclic deterministic automata, Discrete Appl. Math., 154, No.3 (2006), 537-551.
R. W. Robinson, Counting strongly connected finite automata, pages 671-685 in "Graph theory with applications to algorithms and computer science." Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4-8, 1984. Edited by Y. Alavi, G. Chartrand, L. Lesniak [L. M. Lesniak-Foster], D. R. Lick and C. E. Wall. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1985. xv+810 pp. ISBN: 0-471-81635-3; Math Review MR0812651. (86g:05026). [Annotated scanned copy, with permission of the author.]
G. Sedlitz, Abzahlung von Automaten, formalen Sprachen und verwandten Strukturen, Master's Thesis, Vienna (2017), Theorem 6.1

Cf. A006690, A107670, A107667.

b := proc(k,n)
    option remember;
    if n = 1 then
        1;
    else
        n^(k*n) -add(binomial(n-1,j-1)*n^(k*(n-j))*procname(k,j),j=1..n-1) ;
    end if;
end proc:
B := proc(k,n)
    b(k,n)/(n-1)! ;
end proc:
A006689 := proc(n)
    B(2,n) ;
end proc:
seq(A006689(n),n=1..10) ; # R. J. Mathar, May 21 2018

a[1] = 1; a[n_] := a[n] = n^(2*n)/(n-1)! - Sum[n^(2*(n-i))*a[i]/(n-i)!, {i, 1, n-1}]; Table[ a[n], {n, 1, 15}] (* Jean-François Alcover, Dec 15 2014 *)

a(n)=if(n<1,0,n^(2*n)/(n-1)!-sum(i=1,n-1,n^(2*(n-i))/(n-i)!*a(i)))

a(n)=local(A);if(n<1,0,A=n*x+x*O(x^n); for(k=0,n,A+=polcoeff(A,k)*x^k*(n-prod(i=0,k,1-(n-i)*x)));polcoeff(A,n))

a(n) = h_2(n)/(n-1)!, where h_2(1) := 1, h_2(n) := n^(2*n) - Sum_{i=1..n-1} binomial(n-1, i-1)*n^(2*n-2*i)*h_2(i) for n > 1.

For k = 2, a(n) = Sum (Product_{i=1..n-1} i^(f_i - f_{i-1} - 1)) * n^(n*k - f_{n-1} - 1), where the sum is taken over integers f_1, ..., f_{n-1} satisfying 0 <= f_1 < k and f_{i-1} < f_{i} < i*k for i = 2..n-1. - Nelma Moreira, Jul 31 2005 [Typo corrected by Petros Hadjicostas, Feb 26 2021. See Theorem 8 in Almeida, Moreira, and Reis (2007). The value of f_0 is not relevant.]

More terms and more detailed definition from Valery A. Liskovets, Apr 09 2003
Further terms from Paul D. Hanna, May 19 2005
Edited by N. J. A. Sloane, Dec 06 2008 at the suggestion of R. J. Mathar

A107671 Triangular matrix T, read by rows, that satisfies: T = D + SHIFT_LEFT(T^3), 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, 8, 2, 513, 27, 3, 81856, 2368, 64, 4, 23846125, 469625, 7625, 125, 5, 10943504136, 160767720, 1898856, 19656, 216, 6, 7250862593527, 83548607478, 776598305, 6081733, 43561, 343, 7, 6545029128786432, 61068815111168, 465690017280, 2966844928, 16494080, 86528, 512, 8

Offset: 0

Paul D. Hanna, Jun 07 2005

			Triangle T begins:
              1;
              8,           2;
            513,          27,         3;
          81856,        2368,        64,       4;
       23846125,      469625,      7625,     125,     5;
    10943504136,   160767720,   1898856,   19656,   216,   6;
  7250862593527, 83548607478, 776598305, 6081733, 43561, 343, 7;
  ...
The matrix cube T^3 shifts each row to the right 1 place, dropping the diagonal D and putting A006690 in column 0:
             1;
            56,           8;
          7965,         513,        27;
       2128064,       81856,      2368,      64;
     914929500,    23846125,    469625,    7625,  125;
  576689214816, 10943504136, 160767720, 1898856, 19656, 216;
  ...
From _Petros Hadjicostas_, Mar 11 2021: (Start)
We illustrate the above formula for T(n,k=0) 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 s_1^(-1)*Product_{j=1..r} (Sum_{i=1..j} s_i)^(3*s_j) for these four terms is 19683/3, 729/1, 1728/2, and 216/1.
Thus T(2,0) = (19683/3)/6 - (729/1)/2 - (1728/2)/2 + (216/1)/1 = 513. (End)

Cf. A107667, A107672 (column 0), A107673, A107674 (matrix square), A107676 (matrix cube), A006690.

{T(n,k)=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)));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)^3)^(n-k)/(n-k)! for n >= k >= 0 and the diagonal matrix D(n, n) = n+1 for n >= 0; then T is given by T = P^-1*D*P.

T(n,k=0) = Sum_{r=1..(n+1)} (-1)^(r-1) * Sum_{s_1, ..., s_r} (s_1^(-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.) - Petros Hadjicostas, Mar 11 2021

A107676 Matrix cube of triangle A107671.

Original entry on oeis.org

1, 56, 8, 7965, 513, 27, 2128064, 81856, 2368, 64, 914929500, 23846125, 469625, 7625, 125, 576689214816, 10943504136, 160767720, 1898856, 19656, 216, 500750172337212, 7250862593527, 83548607478, 776598305, 6081733, 43561, 343

Offset: 0

Paul D. Hanna, Jun 07 2005

Column 0 is A006690.

			Triangle begins:
1;
56,8;
7965,513,27;
2128064,81856,2368,64;
914929500,23846125,469625,7625,125;
576689214816,10943504136,160767720,1898856,19656,216; ...
which equals the matrix cube of triangle A107671:
1;
8,2;
513,27,3;
81856,2368,64,4;
23846125,469625,7625,125,5;
10943504136,160767720,1898856,19656,216,6; ...

Cf. A107667, A107671, A107674, A006690.

{T(n,k)=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)));if(n>=k,(P^-1*D^3*P)[n+1,k+1])}

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

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

Original entry on oeis.org

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

A107674 Matrix square of triangle A107671.

Original entry on oeis.org

1, 24, 4, 2268, 135, 9, 461056, 15936, 448, 16, 160977375, 3789250, 69000, 1125, 25, 85624508376, 1485395280, 19994688, 223560, 2376, 36, 64363893844726, 862907827866, 9138674195, 79086196, 596820, 4459, 49, 64928246784463872

Offset: 0

Paul D. Hanna, Jun 07 2005

Column 0 is A107675.

			Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
            1;
           24,          4;
         2268,        135,        9;
       461056,      15936,      448,     16;
    160977375,    3789250,    69000,   1125,   25;
  85624508376, 1485395280, 19994688, 223560, 2376, 36;
  ...

Cf. A006690, A107667, A107671, A107675, A107676.

{T(n,k)=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)));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)^3)^(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.

cp's OEIS Frontend

A107668 Column 0 of triangle A107667.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Haskell

PARI

PARI

PARI

Formula

A107670 Matrix square of triangle A107667.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A006689 Number of deterministic, completely-defined, initially-connected finite automata with 2 inputs and n unlabeled states.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A107671 Triangular matrix T, read by rows, that satisfies: T = D + SHIFT_LEFT(T^3), 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

PARI

Formula

A107676 Matrix cube of triangle A107671.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

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

Views

Author

Keywords

Crossrefs

Programs

PARI

A107674 Matrix square of triangle A107671.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula