A331390 Number of binary matrices with 3 distinct columns and any number of nonzero rows with n ones in every column and rows in nonincreasing lexicographic order.

1, 9, 29, 68, 134, 237, 388, 600, 887, 1265, 1751, 2364, 3124, 4053, 5174, 6512, 8093, 9945, 12097, 14580, 17426, 20669, 24344, 28488, 33139, 38337, 44123, 50540, 57632, 65445, 74026, 83424, 93689, 104873, 117029, 130212, 144478, 159885, 176492, 194360, 213551

Offset

1,2

Comments

The condition that the rows be in nonincreasing order is equivalent to considering nonequivalent matrices up to permutation of rows.

a(n) is the number of T_0 n-regular set multipartitions (multisets of sets) on a 3-set.

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1000

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

Formula

a(n) = round(((n+2)/2)^4) - 3*(n+1) + 2.

G.f.: x*(1 + 5*x - 2*x^2 - 3*x^3 + 2*x^4)/((1 - x)^5*(1 + x)). - Andrew Howroyd, Nov 14 2025

E.g.f.: (x*(17 + 55*x + 14*x^2 + x^3)*cosh(x) - (1 - 17*x - 55*x^2 - 14*x^3 - x^4)*sinh(x))/16. - Stefano Spezia, Nov 15 2025

Example

The a(2) = 9 matrices are:
  [1, 0, 0]  [1, 1, 0]  [1, 0, 1]  [1, 0, 0]
  [1, 0, 0]  [1, 0, 0]  [1, 0, 0]  [1, 0, 0]
  [0, 1, 0]  [0, 1, 0]  [0, 1, 0]  [0, 1, 1]
  [0, 1, 0]  [0, 0, 1]  [0, 1, 0]  [0, 1, 0]
  [0, 0, 1]  [0, 0, 1]  [0, 0, 1]  [0, 0, 1]
  [0, 0, 1]
  .
  [1, 1, 1]  [1, 1, 0]  [1, 1, 0]  [1, 0, 1]  [1, 1, 0]
  [1, 0, 0]  [1, 0, 1]  [1, 0, 0]  [1, 0, 0]  [1, 0, 1]
  [0, 1, 0]  [0, 1, 0]  [0, 1, 1]  [0, 1, 1]  [0, 1, 1]
  [0, 0, 1]  [0, 0, 1]  [0, 0, 1]  [0, 1, 0]

Mathematica

A331390[n_] := Round[(n/2 + 1)^4] - 3*n - 1; Array[A331390, 50] (* or *)
LinearRecurrence[{4, -5, 0, 5, -4, 1}, {1, 9, 29, 68, 134, 237}, 50] (* Paolo Xausa, Nov 14 2025 *)

Prog

(PARI) a(n) = {round(((n+2)/2)^4) - 3*(n+1) + 2}

Crossrefs

Column k=3 of A331126.

Sequence in context: A272784 A272807 A316602 * A273071 A273146 A272844

Adjacent sequences: A331387 A331388 A331389 * A331391 A331392 A331393

Keyword

nonn,easy

Author

Andrew Howroyd, Jan 15 2020

Status

approved