A336529 a(n) = (n^3+5*n+3)/3 + 2*floor(n/2) + a(n-2), with a(0)=1 and a(1)=3.

1, 3, 10, 20, 43, 75, 132, 208, 325, 475, 686, 948, 1295, 1715, 2248, 2880, 3657, 4563, 5650, 6900, 8371, 10043, 11980, 14160, 16653, 19435, 22582, 26068, 29975, 34275, 39056, 44288, 50065, 56355, 63258, 70740, 78907, 87723, 97300, 107600, 118741, 130683, 143550, 157300

Offset

0,2

Comments

Let S be a fixed matching of size 2 in a complete n-uniform hypergraph G with >= 4n vertices. Given T,T' (each also a matching of size 2), define the equivalence relation where T ~ T' if and only if there exists an automorphism of G that maps every hyperedge in T to a hyperedge in T' while mapping every hyperedge in S to a hyperedge in S. Then the number of equivalence classes is a(n).

a(n) is the number of equivalence classes of 2 X 2 matrices with nonnegative integer entries where each row and column sum to at most n, such that two matrices are related if one can be obtained from the other by permuting rows and columns.

Links

Michael De Vlieger, Table of n, a(n) for n = 0..10000

Yu Hin Au, Nathan Lindzey, and Levent Tunçel, Matchings, hypergraphs, association schemes, and semidefinite optimization, arXiv:2008.08628 [math.CO], 2020.

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

Formula

a(n) = 3*a(n-1) - a(n-2) - 5*a(n-3) + 5*a(n-4) + a(n-5) - 3*a(n-6) + a(n-7). - Wesley Ivan Hurt, Nov 04 2020

G.f.: (1 + 2*x^2 - 2*x^3 + 3*x^4) / ((1 - x)^5*(1 + x)^2). - Colin Barker, Nov 05 2020

Example

To see a(2)=10, let S = {{1,2},{3,4}}. Then a representative from each of the 10 equivalence classes are
  1. {{1,2}, {3,4}}
  2. {{1,3}, {2,4}}
  3. {{1,5}, {3,4}}
  4. {{1,3}, {4,5}}
  5. {{1,2}, {5,6}}
  6. {{1,3}, {5,6}}
  7. {{1,5}, {2,6}}
  8. {{1,5}, {3,6}}
  9. {{1,5}, {6,7}}
  10. {{5,6}, {7,8}}
Likewise, in the 2 X 2 matrix interpretation, a representative from each of the a(2)=10 equivalence classes are
  [2 0 ; 0 2]
  [1 1 ; 1 1]
  [2 0 ; 0 1]
  [1 1 ; 1 0]
  [2 0 ; 0 0]
  [1 1 ; 0 0]
  [1 0 ; 1 0]
  [1 0 ; 0 1]
  [1 0 ; 0 0]
  [0 0 ; 0 0]

Mathematica

Nest[Append[#1, (#2^3 + 5 #2 + 3)/3 + 2*Floor[#2/2] + #1[[-2]] ] & @@ {#, Length@ #} &, {1, 3}, 42] (* Michael De Vlieger, Nov 04 2020 *)
LinearRecurrence[{3, -1, -5, 5, 1, -3, 1}, {1, 3, 10, 20, 43, 75, 132}, 60] (* Harvey P. Dale, May 28 2021 *)

Prog

(PARI) Vec((1 + 2*x^2 - 2*x^3 + 3*x^4) / ((1 - x)^5*(1 + x)^2) + O(x^40)) \\ Colin Barker, Nov 05 2020

Crossrefs

Cf. A316587.

Sequence in context: A295953 A005997 A213850 * A081205 A273379 A306813

Adjacent sequences: A336526 A336527 A336528 * A336530 A336531 A336532

Keyword

nonn,easy

Author

Yu Hin Au, Jul 24 2020

Status

approved