Nathaniel Johnston - cp's OEIS frontend

A379103 Expansion of (1-3x-sqrt(9x^2-14*x+1))/4.

0, 1, 5, 35, 295, 2765, 27705, 290535, 3148995, 34995065, 396602605, 4566227435, 53259218495, 627982592965, 7473163652705, 89640387354735, 1082664905352795, 13155505626756465, 160709002086562005, 1972595405313408435, 24315686632846439895, 300886761671728853565, 3736205372071338170505, 46540791299676591116535

Offset: 0

Nathaniel Johnston, Dec 15 2024

Problem A6 on the 2024 William Lowell Putnam Mathematical Competition was to compute the Hankel transform of this sequence, which is A110147.

Given constants X and Y, let A(x) = (1 - x*(X - Y) - sqrt(1 - 2*x*(X + Y) + x^2*(X - Y)^2))/(2*Y) = x*(1) + x^2*(X) + x^3*X*(X + Y) + x^4*X*(X^2 + 3*X*Y + Y^2) + ... where the coefficients of A(x) is the Narayana triangle A090181. A(x) satisfies 0 = x - A(x)*(1 - x*(X-Y)) + A(x)^2*Y. The Hankel transform of the coefficients 1, X, X*(X + Y), ... is the sequence 1, (X*Y), (X*Y)^2, ... while the Hankel transform of X, X*(X + Y), X*(X^2 + 3*X*Y + Y^2), ... is the sequence X, X^3*Y, X^6*Y^3, X^10*Y^6, .... In the case of this sequence, X = 5 and Y = 2. - Michael Somos, Apr 26 2025

			G.f. = x + 5*x^2 + 35*x^3 + 295*x^4 + 2765*x^5 + 27705*x^6 + ... - _Michael Somos_, Apr 26 2025

Nathaniel Johnston, Determinant involving (1 - 3x - sqrt(1 - 14x + 9x^2))/4, YouTube video, 2024.
Nathaniel Johnston, Putnam 2024 A6 solution, 2024.

Cf. A025231, A047891, A082298, A110147.

a = 3;b = 2;c(1) = 1;last_val = 16;for j = 2:last_val
c(j) = a*c(j-1) + b*sum(c(1:j-1).*fliplr(c(1:j-1)));
end

a[ n_] := SeriesCoefficient[ (1 - 3*x - Sqrt[1 - 14*x + 9*x^2])/4, {x, 0, n}]; (* Michael Somos, Apr 26 2025 *)
a[ n_] := With[{X = 5, Y = 2}, SeriesCoefficient[ Nest[x/(1 - (X-Y)*x - Y*#)&, O[x], n], {x, 0, n}]]; (* Michael Somos, Apr 28 2025 *)
a[ n_] := With[{X = 5, Y = 2}, SeriesCoefficient[ Nest[x/(1 - X*x/(1 - Y*#))&, O[x], Ceiling[n/2]], {x, 0, n}]]; (* Michael Somos, Apr 28 2025 *)

my(x='x+O('x^33)); concat([0],Vec((1-3*x-sqrt(9*x^2-14*x+1))/4)) \\ Joerg Arndt, Dec 15 2024

a(n) = my(A = O(x)); for(k=1, n, A = x + 3*x*A + 2*A^2); polcoeff(A, n); /* Michael Somos, Apr 26 2025 */

a(n) = my(A = O(x), X = 5, Y = 2); for(k = 1, n, A = x/(1 - (X-Y)*x - Y*A)); polcoeff(A, n); /* Michael Somos, Apr 28 2025 */

a(n) = my(A = O(x), X = 5, Y = 2); for(k = 1, (n+1)\2, A = x/(1 - X*x/(1 - Y*A))); polcoeff(A, n); /* Michael Somos, Apr 28 2025 */

a(0) = 0, a(1) = 1, a(n) = 3*a(n-1) + 2*Sum_{k=0..n} a(k)*a(n-k) for n >= 2.
G.f.: (1-3*x-sqrt(9*x^2-14*x+1))/4.
G.f.: x/(1-5*x/(1-2*x/(1-5*x/(1-2*x/(1-5*x/(...)))))). - Thomas Scheuerle, Feb 28 2025
a(n) = (1/4)*(-1)^(n+1) * Sum_{k=0..n} binomial(1/2,k) * binomial(1/2,n-k) * (7+2*sqrt(10))^k * (7-2*sqrt(10))^(n-k) for n >= 2. - Ehren Metcalfe, Feb 26 2025
a(n) ~ 5^(1/4) * (7 + 2*sqrt(10))^(n - 1/2) / (2^(7/4) * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 27 2025
The g.f. A(x) satisfies 0 = x - (1 - 3*x)*A(x) + 2*A(x)^2 and A(x) = x + 3*x*A(x) + 2*A(x)^2. - Michael Somos, Apr 26 2025

A363065 Number of Laplacian integral graphs on n vertices.

Original entry on oeis.org

1, 2, 4, 10, 24, 70, 188, 553, 1721, 5716

Offset: 1

Nathaniel Johnston, May 16 2023

A (simple, undirected) graph is called Laplacian integral if all eigenvalues of its Laplacian matrix are integers. The corresponding sequence that uses the adjacency matrix instead of the Laplacian matrix is A077027.

Since every cograph is Laplacian integral, a(n) >= A000084(n).

			For n <= 3, all graphs are Laplacian integral, so a(n) = A000088(n) when n <= 3.
There is exactly one graph on 4 vertices that is not Laplacian integral: the path P_4, which has Laplacian matrix
   1 -1  0  0
  -1  2 -1  0
   0 -1  2 -1
   0  0 -1  1
which has eigenvalues 0, 2, 2-sqrt(2), and 2+sqrt(2), which are not all integers.

R. Grone and R. Merris, Indecomposable Laplacian integral graphs, Linear Algebra and its Applications, 428 (2008), 1565-1570.

Cf. A000084, A000088, A077027, A363064 (connected graphs only).

a(10) from M. A. Achterberg, May 26 2023

A363064 Number of connected Laplacian integral graphs on n vertices.

Original entry on oeis.org

1, 1, 2, 5, 12, 37, 94, 280, 912, 3164, 8424

Offset: 1

Nathaniel Johnston, May 16 2023

A (simple, undirected) graph is called Laplacian integral if all eigenvalues of its Laplacian matrix are integers. The corresponding sequence that uses the adjacency matrix instead of the Laplacian matrix is A064731.

Since every cograph is Laplacian integral, a(n) >= A000669(n).

			For n <= 3, all connected graphs are Laplacian integral, so a(n) = A001349(n) when n <= 3.
There is exactly one connected graph on 4 vertices that is not Laplacian integral: the path P_4, which has Laplacian matrix
   1 -1  0  0
  -1  2 -1  0
   0 -1  2 -1
   0  0 -1  1
which has eigenvalues 0, 2, 2-sqrt(2), and 2+sqrt(2), which are not all integers.

R. Grone and R. Merris, Indecomposable Laplacian integral graphs, Linear Algebra and its Applications, 428 (2008), 1565-1570.

Cf. A000669, A001349, A064731, A363065 (include disconnected graphs).

a(10) from M. A. Achterberg, May 26 2023

a(11) from Luis M. B. Varona, Apr 27 2025

A352940 The largest positive integer k such that binomial(k+1,2) <= binomial(n,2)^2.

Original entry on oeis.org

3, 8, 13, 20, 29, 39, 50, 63, 77, 92, 109, 128, 147, 169, 191, 215, 241, 268, 296, 326, 357, 389, 423, 459, 495, 534, 573, 614, 657, 700, 746, 792, 840, 890, 941, 993, 1047, 1102, 1159, 1217, 1276, 1337, 1399, 1463, 1528, 1594, 1662, 1731, 1802, 1874, 1948

Offset: 3

Nathaniel Johnston, May 06 2022

nonn

This sequence is bounded between floor((n-1)^2/sqrt(2) - 1) and (n-1)^2.

This sequence is the maximum dimension of a subspace of C^n * C^n (where * is the tensor/Kronecker product) that can be shown to be entangled by the first level of the hierarchy described in the linked Johnston-Lovitz-Vijayaraghavan paper.

N. Johnston, B. Lovitz, and A. Vijayaraghavan. Complete hierarchy of linear systems for certifying quantum entanglement of subspaces. Physical Review A, 106:062443, 2022.

from math import isqrt
def A352940(n): return (isqrt(n**2*(n*(2*n-4)+2)+1)-1)//2 # Chai Wah Wu, May 07 2022

a(n) ~ (n-1)^2/sqrt(2).

A352099 Number of inequivalent {-1,1} matrices of order n, up to permutation of rows and/or columns and multiplication of rows and/or columns by -1.

Original entry on oeis.org

1, 2, 3, 12, 39, 388, 8102, 656108, 199727714, 224693292768, 893966897828288, 12397352268917562436, 598097093939369977901540, 100707091308314174859433507948, 59497535893138933753768955970555554, 124081719421265185713331815803874814236572, 919072633264334061873768956083917736204779032768

Offset: 1

Nathaniel Johnston, May 05 2022

nonn

The equivalence operations described in the title are commonly used when discussing Hadamard matrices, for example (see A007299). See A353052 for the version of this sequence that also considers transposition as part of the equivalence relation.

Since the row and column multiplication operations can be used to force the first row and column to consist only of ones, 2^((n-1)^2) is an upper bound on this sequence. A lower bound is 2^((n-1)^2) / (n!)^2.

Eugene Nonko, Table of n, a(n) for n = 1..45
Project Euler, Problem 626: Counting Binary Matrices.

Cf. A007299, A111368, A353052.

a(8) onwards from Eugene Nonko, Nov 30 2024

A353052 Number of inequivalent {-1,1} matrices of order n, up to permutation of rows and/or columns, multiplication of rows and/or columns by -1, and transposition.

Original entry on oeis.org

1, 2, 3, 10, 30, 242, 4386

Offset: 1

Nathaniel Johnston, Apr 20 2022

The equivalence operations described in the title are commonly used when discussing Hadamard matrices, for example (see A096201). They are natural when considering norms of these matrices or properties that can be inferred from their singular values, since they do not change singular values. See A352099 for the version of this sequence that does not consider transposition as part of the equivalence relation.

Since the row and column multiplication operations can be used to force the first row and column to consist only of ones, 2^[(n-1)^2] is an upper bound on this sequence. A lower bound is 2^[n*(n-2)] / (n!)^2.

			When n = 3, there are 3 inequivalent matrices, so a(3) = 3:
  1 1 1       1  1  1       1  1  1
  1 1 1       1  1 -1       1 -1 -1
  1 1 1  and  1 -1 -1  and  1 -1 -1
All other 3-by-3 matrices with entries in {-1,1} can be converted into one of these three matrices by permutating rows and/or columns, multiplying some rows and/or columns by -1, and potentially transposing the matrix.

John Holbrook, Nathaniel Johnston, and Jean-Pierre Schoch, Real Schur norms and Hadamard matrices, arXiv:2206.02863 [math.CO], 2022.
Nathaniel Johnston, All inequivalent matrices of size 6-by-6 or less

Cf. A111368, A352099.

a(7) from Nathaniel Johnston, May 05 2022

A332263 Maximal length of a string over the alphabet {0,1,2} with the property that its contiguous substrings of length n all have different quantities of 0's, 1's, or 2's.

Original entry on oeis.org

3, 7, 12, 17, 22, 30, 39, 45, 56, 66, 77, 90

Offset: 1

Nathaniel Johnston, Feb 08 2020

In other words, the contiguous substrings of length n are all different if we interpret them as multisets.

Since there are binomial(n+2,2) different triples of nonnegative integers summing up to n, we have the bound a(n) <= binomial(n+2,2)+n-1. Equality holds if and only if n <= 3.

			Maximal strings for n = 1, 2, ..., 8 are:
012
0011220
011122200012
00111122220000121
0100212111000002222211
001011112122220200001012120200
010010220212110100000202222212111110100
021200201101121220202000010111111212222220200

Bert Dobbelaere, C++ program
MathOverflow, Sequences with 3 Letters

a(9)-a(12) from Bert Dobbelaere, Feb 09 2020

A330283 Number of n-celled quasi still lifes in Conway's Game of Life, up to rotation and reflection.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 6, 13, 57, 141, 465, 1224, 3956, 11599, 36538, 107415, 327250, 972040, 2957488, 8879327, 26943317

Offset: 1

Nathaniel Johnston, Dec 09 2019

A quasi still life is a still life made up of two or more strict still lifes (A019473) that share at least 1 neighboring dead cell, but those cells still remain dead due to underpopulation just like if we were to separate those component strict still lifes. Contrast with pseudo still lifes (A056613), where the component strict still lifes share at least 1 neighboring dead cell that remains dead, but the reason shifts from underpopulation in the strict still lifes to overpopulation in the combined pattern.

			When n = 8, the 6 quasi still lifes are the various arrangements of blocks and tubs in which they share a neighbor, but that neighbor remains dead due to underpopulation. In the diagrams below, "." is a dead cell, "o" is a live cell, and "*" is a dead neighboring cell that makes the pattern a quasi still life:
.o...o.
o.o*o.o
.o...o.
.
.o.....
o.o*.o.
.o.*o.o
.....o.
.
oo...
oo...
..*..
...oo
...oo
.
oo....
oo....
..*.o.
...o.o
....o.
.
.o.....
o.o....
.o.*.o.
....o.o
.....o.
.
.o....
o.o...
.o.*..
..*.o.
...o.o
....o.

LifeWiki, quasi still lifes

Cf. A019473, A056613.

A273308 Maximum population of a 2 X n still life in Conway's Game of Life.

Original entry on oeis.org

0, 4, 4, 6, 8, 8, 10, 12, 12, 14, 16, 16, 18, 20, 20, 22, 24, 24, 26, 28, 28, 30, 32, 32, 34, 36, 36, 38, 40, 40, 42, 44, 44, 46, 48, 48, 50, 52, 52, 54, 56, 56, 58, 60, 60, 62, 64, 64, 66, 68, 68, 70, 72, 72, 74, 76, 76, 78, 80, 80, 82, 84, 84, 86, 88, 88

Offset: 1

Nathaniel Johnston, May 19 2016

Although the Chu et al. reference does not discuss this problem explicitly, the same methods in that paper can be used to prove the formula for this sequence.

			a(2) = 4 because the largest number of alive cells in a 2 X 2 still life is 4, which is attained by the block.
a(4) = 6 because the largest number of alive cells in a 2 X 4 still life is 6, which is attained by the snake.

Colin Barker, Table of n, a(n) for n = 1..1000
G. Chu, P. Stuckey, and M.G. de la Banda, Using relaxations in Maximum Density Still Life, In Proc. of Fifteenth Intl. Conf. on Principles and Practice of Constraint Programming, 258-273 (2009).
LifeWiki, Still life
Index entries for linear recurrences with constant coefficients, signature (1,0,1,-1).

Cf. A019473, A055397.

seq(4*floor((n+1)*(1/3))+2*floor((1/2)*(`mod`(n+1, 3))), n = 2 .. 110);

LinearRecurrence[{1,0,1,-1},{0,4,4,6,8},70] (* Harvey P. Dale, Apr 19 2023 *)

concat(0, Vec(2*x^2*(2+x^2-x^3)/((1-x)^2*(1+x+x^2)) + O(x^50))) \\ Colin Barker, May 24 2016

def A273308(n): return n+sum(divmod(n,3)) if n > 1 else 0 # Chai Wah Wu, Jan 29 2023

For n >= 1, a(3*n) = a(3*n-1) = 4*n and a(3*n+1) = 4*n+2.
From Colin Barker, May 24 2016: (Start)
a(n) = a(n-1)+a(n-3)-a(n-4) for n>5.
G.f.: 2*x^2*(2+x^2-x^3) / ((1-x)^2*(1+x+x^2)). (End)
a(n) = A063224(n+1) = A063200(n+1) for n>1. - R. J. Mathar, May 27 2016

A266797 a(n) = (6^n + 4^n + 3*2^n)/8.

Original entry on oeis.org

2, 8, 38, 200, 1112, 6368, 37088, 218240, 1292672, 7689728, 45874688, 274196480, 1640978432, 9829081088, 58907353088, 353175633920, 2117979963392, 12703584616448, 76204327436288, 457157244354560, 2742668586647552, 16454912005111808, 98725073977868288

Offset: 1

Nathaniel Johnston, Jan 03 2016

Gives the number of ways that the product of the values on n different 6-sided dice can be a perfect square. Thus a(n)/6^n is the probability that the product of n different 6-sided dice is a perfect square.

			a(1) = 2 because there are two ways for one die to be a perfect square: if its value is 1 or 4.
a(2) = 8 because there are eight ways for the product of the values on two dice to result in perfect squares: 1*1, 1*4, 2*2, 3*3, 4*1, 4*4, 5*5, 6*6.

Colin Barker, Table of n, a(n) for n = 1..1000
Math.StackExchange, When the product of dice rolls yields a square
Index entries for linear recurrences with constant coefficients, signature (12,-44,48).

Maple
```
seq((6^n+4^n+3*2^n)/8, n = 1 .. 40);
```

a(n) = 2^(n-3)*(2^n+3^n+3) \\ Colin Barker, Jan 08 2016

Vec(2*x*(1-3*x)*(1-5*x)/((1-2*x)*(1-4*x)*(1-6*x)) + O(x^30)) \\ Colin Barker, Jan 08 2016

From Colin Barker, Jan 08 2016: (Start)
a(n) = 2^(n - 3)*(2^n + 3^n + 3).
a(n) = 12*a(n-1) - 44*a(n-2) + 48*a(n-3) for n>3.
G.f.: 2*x*(1 - 3*x)*(1 - 5*x) / ((1 - 2*x)*(1 - 4*x)*(1 - 6*x)).
(End)

cp's OEIS Frontend

User: Nathaniel Johnston

A379103 Expansion of (1-3*x-sqrt(9*x^2-14*x+1))/4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Mathematica

PARI

PARI

PARI

PARI

Formula

A363065 Number of Laplacian integral graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A363064 Number of connected Laplacian integral graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A352940 The largest positive integer k such that binomial(k+1,2) <= binomial(n,2)^2.

Views

Author

Keywords

Comments

Links

Programs

Python

Formula

A352099 Number of inequivalent {-1,1} matrices of order n, up to permutation of rows and/or columns and multiplication of rows and/or columns by -1.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A353052 Number of inequivalent {-1,1} matrices of order n, up to permutation of rows and/or columns, multiplication of rows and/or columns by -1, and transposition.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A332263 Maximal length of a string over the alphabet {0,1,2} with the property that its contiguous substrings of length n all have different quantities of 0's, 1's, or 2's.

Views

Author

Keywords

Comments

Examples

Links

Extensions

A330283 Number of n-celled quasi still lifes in Conway's Game of Life, up to rotation and reflection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A273308 Maximum population of a 2 X n still life in Conway's Game of Life.

Views

A379103 Expansion of (1-3x-sqrt(9x^2-14*x+1))/4.