Sela Fried - cp's OEIS frontend

A384616 A(m,n) is the maximum sum of absolute differences of the labels of adjacent vertices of the grid graph P_m X P_n where the mn labels are exactly 1, 2, ..., mn.

0, 1, 8, 3, 23, 58, 7, 44, 115

Offset: 1

Sela Fried, Jun 07 2025

A(m, n) ~ Theta((m*n)^2) (see link).

			Array begins (values in parentheses are conjectural):
  [1]  0
  [2]  1    8
  [3]  3   23    58
  [4]  7   44   115   (216)
  [5] 11   71  (182)  (347)  (554)
  [6] 17  104  (271)  (508)  (815) (1192)
  [7] 23  143  (370)  (699) (1118) (1639) (2250)
  [8] 31 (188) (491)  (920) (1475) (2156) (2963) (3896)
  [9] 39 (239) (622) (1171) (1874) (2743) (3766) (4955) (6298)

Sela Fried, On the maximal sum of absolute differences of certain labelings of the grid graph, 2025.

Column 1 is A047838.

Cf. A067725.

import itertools
import numpy as np
def max_difference_sum(m, n):
    nums = list(range(1, m * n + 1))
    max_sum = 0
    best_matrix = None
    for perm in itertools.permutations(nums):
        matrix = np.array(perm).reshape((m, n))
        diff_sum = np.sum(np.abs(matrix[:,1:]-matrix[:,:-1])) + np.sum(np.abs(matrix[1:,:]-matrix[:-1,:]))
        if diff_sum > max_sum:
            max_sum = diff_sum
            best_matrix = matrix.copy()
    return max_sum, best_matrix
for m in range(1, 10):
    for n in range(1, m+1):
        max_sum, best = max_difference_sum(m, n)
        print(max_sum, end=', ')

Conjecture: A(m,2) = A067725(m-1) - 1.

A368539 Maximal sum of elements of A^2 where A is a square matrix of size n whose elements are a permutation of {1, 2, ..., n^2}.

Original entry on oeis.org

1, 54, 761, 5284

Offset: 1

Sela Fried, Dec 29 2023

The next terms are at least (and probably equal to) 5284, 24303, 85352 and 248045.
The lower bounds for the terms a(4)-a(7) are confirmed. a(8) >= 626610, a(9) >= 1421271, a(10) >= 2959798, a(11) >= 5750977. - Hugo Pfoertner, Jan 21 2024
In addition to the conditions (a)-(d) described in para 2.2 of Fried and Mansour (2023), conjecturally optimal matrices found using simulated annealing have the following additional property: If, using simultaneous row and column rearrangement, the matrix is brought into a form in which the terms of the main diagonal are sorted in ascending order, then every single row and every single column is monotonically increasing. See the linked file for examples from n=2 to n=14. - Hugo Pfoertner, Jan 25 2024

			                                                     [1 3 4]
For n = 3, the sum of the elements of A^2, where A = [2 6 8], is 761.
                                                     [5 7 9]

Sela Fried and Toufik Mansour, On the maximal sum of the entries of a matrix power, arXiv:2308.00348 [math.CO], 2023.
Hugo Pfoertner, Examples of solutions found by simulated annealing, for n=2-14. Jan 25, 2024.

Cf. A085000, A350566, A369396.

A364777 a(n) = (n^2)!(n!)^2/(2n-1)!.

Original entry on oeis.org

1, 16, 108864, 2391175987200, 615524208068689920000000, 4831082166102613213870122703257600000000, 2481336275198061145749280386508780674949224836628480000000000

Offset: 1

Sela Fried, Aug 07 2023

nonn

a(n) is the number of square matrices of size n, whose elements are a permutation of 1, 2, ..., n^2, having a saddle point.

A. J. Goldman, The probability of a saddlepoint, The American Mathematical Monthly, 64, 10 (1957), pp. 729-730.
E. D. Thorp, The probability that a matrix has a saddle point, Information Sciences 19 2 (1979), 91-95.

A358035 a(n) = (8n^3 + 12n^2 + 4*n - 9)/3.

Original entry on oeis.org

5, 37, 109, 237, 437, 725, 1117, 1629, 2277, 3077, 4045, 5197, 6549, 8117, 9917, 11965, 14277, 16869, 19757, 22957, 26485, 30357, 34589, 39197, 44197, 49605, 55437, 61709, 68437, 75637, 83325, 91517, 100229, 109477, 119277, 129645, 140597, 152149, 164317

Offset: 1

Sela Fried, Oct 26 2022

Conjecture: a(n) is the disorder number of the Aztec diamond of size n.

G. E. Andrews and K. Eriksson, Integer Partitions, Cambridge University Press, 2004.

Sela Fried, The disorder number of a graph, arXiv:2208.03788 [math.CO], 2022.
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A354528.

Table[(8n^3+12n^2+4n-9)/3,{n,40}] (* or *) LinearRecurrence[{4,-6,4,-1},{5,37,109,237},40] (* Harvey P. Dale, Nov 20 2022 *)

def A358035(n): return n*(n*((n<<3) + 12) + 4)//3 - 3 # Chai Wah Wu, Oct 31 2022

G.f.: x*(5 + 17*x - 9*x^2 + 3*x^3)/(1 - x)^4. - Stefano Spezia, Oct 26 2022

A354528 Square array T(m,n) read by antidiagonals - see Comments for definition.

Original entry on oeis.org

0, 1, 1, 3, 5, 3, 7, 12, 12, 7, 11, 21, 23, 21, 11, 17, 32, 39, 32, 17, 23, 45, 55, 61, 55, 45, 23, 31, 60, 77, 87, 77, 60, 31, 39, 77, 99, 117, 119, 117, 99, 77, 39, 49, 96, 127, 151, 161, 151, 127, 96, 49, 59, 117, 155, 189, 203, 213

Offset: 1

Sela Fried, Aug 16 2022

T(m,n) is defined as follows:
T(m, n) = T(n, m).
T(1, n) = floor(n^2/2) - 1.
T(2, n) = (n+1)^2 - 4.
For m, n >= 3 we have:
T(m, n) = m*n*(m + n)/2 - 3,             if m and n are both even;
        = m*n*(m + n)/2 - (m + n)/2 - 1, if m and n are both odd;
        = m*n*(m + n)/2 - n/2 - 1,       if m is odd and n is even.
The disorder number M(G) of a graph G is defined to be the maximal length of a walk along the edges of the graph, according to any ordering of its vertices.
Conjecture: T(m, n) = M(P_m X P_n) where P_m X P_n is the grid graph of size m X n.
The conjecture is proved if m = 1 or n = 1.

			m\n   1  2  3   4   5   6 ...
1     0  1  3   7  11  17
2     1  5 12  21  32  45
3     3 12 23  39  55  77
4     7 21 39  61  87 117
5    11 32 55  87 119 161
6    17 45 77 117 161 213
...

L. Bulteau, S. Giraudo and S. Vialette, Disorders and Permutations, CPM, 2021.

Sela Fried, The disorder number of a graph, arXiv:2208.03788 [math.CO], 2022.

Cf. A047838, A028347, A179094, A354529.

A356658 The number of orderings of the hypercube Q_n whose disorder number is equal to the disorder number of Q_n.

Original entry on oeis.org

2, 8, 48, 2304, 4024320

Offset: 1

Sela Fried, Aug 20 2022

A proof of a closed form for this sequence will settle Question 3.3 of the preprint "The disorder number of a graph" (see links).

			For n = 2, there are exactly two orderings that begin at 00, whose disorder is the disorder number of Q_2, namely, [00, 11, 01, 10] and [00, 11, 10, 01]. Since we can start at any vertex, we need to multiply their number by 2^2, yielding a(2) = 8.

M. Dominus, "Anti-Gray" codes that maximize the number of bits that change at each step, Mathematics Stack Exchange, 2013.
Sela Fried, The disorder number of a graph, arXiv:2208.03788 [math.CO], 2022.

Cf. A271771.

A354529 a(1) = 3, a(2) = 12 and a(n) = (3n^2+8n-2)/2 if n is even or = (3n^2+8n-5)/2, if n is odd, for n >= 3.

Original entry on oeis.org

3, 12, 23, 39, 55, 77, 99, 127, 155, 189, 223, 263, 303, 349, 395, 447, 499, 557, 615, 679, 743, 813, 883, 959, 1035, 1117, 1199, 1287, 1375, 1469, 1563, 1663, 1763, 1869, 1975, 2087, 2199, 2317, 2435, 2559, 2683, 2813, 2943, 3079, 3215, 3357, 3499, 3647, 3795, 3949, 4103, 4263, 4423

Offset: 1

Sela Fried, Aug 16 2022

The disorder number M(G) of a graph G is defined to be the maximal length of a walk along the edges of the graph, according to any ordering of its vertices.

Conjecture: a(n) = M(P_3 X P_n) where P_3 X P_n is the grid graph of size 3 X n.

Sela Fried, The disorder number of a graph, arXiv:2208.03788 [math.CO], 2022.
Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

Cf. A047838, A028347, A179094, A354528.

def A354529(n): return 9*n-6 if n<3 else n*(3*n+8)-2-3*(n&1)>>1 # Chai Wah Wu, Sep 11 2022

From Stefano Spezia, Aug 16 2022: (Start)
O.g.f.: x*(3 + 6*x - x^2 - x^3 - 2*x^4 + x^5)/((1 - x)^3*(1 + x)).
E.g.f.: ((3*x^2 + 11*x - 2)*cosh(x) + (3*x^2 + 11*x - 5)*sinh(x) - x^2 + 2)/2. (End)

A356480 a(n) is the minimal number of river crossings necessary to solve the missionaries and cannibals problem for n missionaries and n cannibals where the boat capacity is the minimum necessary to allow a solution.

Original entry on oeis.org

1, 5, 11, 9, 11, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, 101, 103, 105, 107, 109, 111, 113, 115, 117, 119, 121, 123, 125, 127, 129, 131, 133, 135

Offset: 1

Sela Fried, Aug 09 2022

The problem is: n missionaries and n cannibals must cross the river using a boat. The missionaries must not be outnumbered by the cannibals at either river bank, or on the boat, and the boat cannot cross the river by itself.
It turns out that the necessary boat capacity is two people for n=1,2,3; three people for n=4,5; and four people for n > 5.
This problem is a generalization of the classical missionaries and cannibals problem, in which n = 3 and the boat capacity is two people. In this case the minimal number of crossings is a(3) = 11 (see example).

			Suppose n = 3 and that all the people must cross from the left river side to the right. Let m and c denote the number of missionaries and the number of the cannibals on the left bank of the river at any time. Let b=L if the boat is on the left bank, b=R if the boat is on the right bank. Then (m, c, b) fully captures the condition of the system. A solution of minimal length is then given by (3, 3, L)-->(2, 2, R)-->(3, 2, L)-->(3, 0, R)-->(3, 1, L)-->(1, 1, R)-->(2, 2, L)-->(0, 2, R)-->(0, 3, L)-->(0, 1, R)-->(1, 1, L)-->(0, 0, R).

P. Norvig and S. J. Russell, Artificial Intelligence: A Modern Approach, Third Edition, 2010. Exercise 3.9.

R. Fraley, K. L. Cooke, and P. Detrick, Graphical Solution of Difficult Crossing Puzzles, Mathematics Magazine, Vol. 39 (3), pp. 151-157, (1966).
Wikipedia, Missionaries and cannibals problem.
Index entries for linear recurrences with constant coefficients, signature (2,-1).

Cf. A060747, A167484.

G.f.: x*(4*x^6 - 4*x^5 + 4*x^4 - 8*x^3 + 2*x^2 + 3*x + 1)/(x-1)^2.

A353044 a(n) is the minimal sum of squares over partitions of n with a nonnegative rank.

Original entry on oeis.org

1, 4, 5, 8, 11, 14, 17, 22, 25, 28, 33, 38, 41, 46, 51, 56, 61, 66, 71, 76, 81, 88, 93, 98, 103, 110, 117, 122, 127, 134, 141, 148, 153, 160, 167, 174, 181, 188, 195, 202, 209, 216, 223, 230, 237, 244, 253, 260, 267, 274, 281, 290, 299

Offset: 1

Sela Fried, Apr 19 2022

nonn

For n not equal to 2, a(n) is the minimal sum of squares over balanced partitions of n.

a(n) is strictly increasing and has parity equal to n.

			Both (5, 3, 3, 3, 3) and (6, 3, 2, 2, 2, 2) are balanced and have the minimal sum of squares of 61 over balanced partitions of n = 17.

Sela Fried, Table of n, a(n) for n = 1..1000
Sela Fried, The minimal sum of squares over partitions with a nonnegative rank, Annals of Combinatorics, 2022.

Cf. A064174, A047993.

a(n) = my(m=oo); forpart(p=n, if (vecmax(p) >= #p, m = min(m, norml2(Vec(p))));); m; \\ Michel Marcus, Aug 09 2022

a(n) = Theta(n^(4/3)).

A349404 The maximal coefficient in the expansion of x_1(x_1 + x_2)...(x_1 + x_2 + ... + x_n).

Original entry on oeis.org

1, 1, 1, 2, 4, 9, 27, 96, 384, 1536, 7500, 37500, 194400, 1166400, 7563150, 52942050, 385351680, 3082813440, 24998984640, 224990861760, 2024917755840, 19051200000000, 190512000000000, 1944663768432000, 21391301452752000

Offset: 0

Sela Fried, Nov 16 2021

nonn

Sela Fried, On the coefficients of the distinct monomials in the expansion of x1(x1+x2)...(x1+x2+...+xn), arXiv:2111.07331 [math.CO], 2021.

Cf. A000140, A065048, A347917.

Max/@Table[Values@CoefficientRules[Times@@Array[Total@Array[x,#]&,n]],{n,0,12}] (* Giorgos Kalogeropoulos, Nov 16 2021 *)

cp's OEIS Frontend

User: Sela Fried

A384616 A(m,n) is the maximum sum of absolute differences of the labels of adjacent vertices of the grid graph P_m X P_n where the m*n labels are exactly 1, 2, ..., m*n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A368539 Maximal sum of elements of A^2 where A is a square matrix of size n whose elements are a permutation of {1, 2, ..., n^2}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A364777 a(n) = (n^2)!*(n!)^2/(2*n-1)!.

Views

Author

Keywords

Comments

Links

A358035 a(n) = (8*n^3 + 12*n^2 + 4*n - 9)/3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

A354528 Square array T(m,n) read by antidiagonals - see Comments for definition.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A356658 The number of orderings of the hypercube Q_n whose disorder number is equal to the disorder number of Q_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A354529 a(1) = 3, a(2) = 12 and a(n) = (3n^2+8n-2)/2 if n is even or = (3n^2+8n-5)/2, if n is odd, for n >= 3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

Formula

A356480 a(n) is the minimal number of river crossings necessary to solve the missionaries and cannibals problem for n missionaries and n cannibals where the boat capacity is the minimum necessary to allow a solution.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A353044 a(n) is the minimal sum of squares over partitions of n with a nonnegative rank.

Views

Author

Keywords

A384616 A(m,n) is the maximum sum of absolute differences of the labels of adjacent vertices of the grid graph P_m X P_n where the mn labels are exactly 1, 2, ..., mn.

A364777 a(n) = (n^2)!(n!)^2/(2n-1)!.

A358035 a(n) = (8n^3 + 12n^2 + 4*n - 9)/3.