A340648 a(n) is the maximum number of nonzero entries in an n X n sign-restricted matrix.

0, 1, 3, 6, 11, 18, 26, 35, 46, 59, 73, 88, 105, 124, 144, 165, 188, 213, 239, 266, 295, 326, 358, 391, 426, 463, 501, 540, 581, 624, 668, 713, 760, 809, 859, 910, 963, 1018, 1074, 1131, 1190, 1251, 1313, 1376, 1441, 1508, 1576, 1645, 1716, 1789, 1863, 1938, 2015

Offset

0,3

Comments

A sign-restricted matrix is such that each partial column sum, starting from row 1, equals 0 or 1, and each partial row sum, starting from column 1, is nonnegative.

Links

Table of n, a(n) for n=0..52.

Richard A. Brualdi and Geir Dahl, Sign-restricted matrices of 0's, 1's, and -1's, arXiv:2101.04150 [math.CO], 2021.

Index entries for linear recurrences with constant coefficients, signature (3,-4,4,-3,1).

Formula

a(n) = (3*n^2-n)/4 if (n==0) or (n==3) (mod 4);

a(n) = (3*n^2-n+2)/4 if (n==1) or (n==2) (mod 4).

From Stefano Spezia, Jan 14 2021: (Start)

G.f.: x*(1 + x^2 + x^3)/((1 - x)^3*(1 + x^2)).

a(n) = 3*a(n-1) - 4*a(n-2) + 4*a(n-3) - 3*a(n-4) + a(n-5) for n > 4. (End)

For n >= 4, a(n) = (A225231(n+1) + 1)/2 - 1. - Hugo Pfoertner, Jan 17 2021

Mathematica

LinearRecurrence[{3, -4, 4, -3, 1}, {0, 1, 3, 6, 11}, 50] (* Amiram Eldar, Jan 14 2021 *)

Prog

(PARI) a(n) = my(x=n % 4); if ((x==0) || (x==3), (3*n^2-n)/4, (3*n^2-n+2)/4);

Crossrefs

Cf. A225231.

Sequence in context: A024667 A363056 A025210 * A140126 A140235 A224214

Adjacent sequences: A340645 A340646 A340647 * A340649 A340650 A340651

Keyword

nonn,easy

Author

Michel Marcus, Jan 14 2021

Status

approved