A289229 -id:A289229 - cp's OEIS frontend

A289222 Triangle read by rows: T(n, k) is the number of ways to select k disjoint point triples from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.

1, 1, 1, 1, 4, 0, 1, 9, 12, 4, 1, 16, 66, 82, 13, 0, 1, 25, 204, 670, 859, 420, 76, 0, 1, 36, 480, 3028, 9585, 15108, 10956, 2910, 231, 2, 1, 49, 960, 9780, 56520, 190371, 371016, 404746, 235380, 68793, 9030, 252, 0, 1, 64, 1722, 25574, 231635, 1336320, 4988324

Offset: 1

Heinrich Ludwig, Jul 03 2017

The row index starts from 1. The column index k runs from 0 to floor(n*(n+1)/6), which is a trivial upper bound for the maximal number of 2 X 2 X 2 triangles that can be selected from an n X n X n triangular grid.

Rotations and reflections of a selection are regarded as different. If they are not to be counted, see A289229.

			The triangle begins:
  1;
  1,  1;
  1,  4,   0;
  1,  9,  12,    4;
  1, 16,  66,   82,   13,     0;
  1, 25, 204,  670,  859,   420,    76,    0;
  1, 36, 480, 3028, 9585, 15108, 10956, 2910, 231, 2;

Heinrich Ludwig, Table of n, a(n) for n = 1..116, first 11 (and a half) rows of the triangular array

Cf. A289229, A289233.

Columns 2 to 8: A000290, A289223, A289224, A289225, A289226, A289227, A289228.

A289230 Number of nonequivalent ways to select 3 disjoint point triples from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.

Original entry on oeis.org

0, 2, 19, 127, 536, 1688, 4357, 9789, 19844, 37172, 65397, 109335, 175214, 270934, 406329, 593463, 846934, 1184212, 1625979, 2196509, 2924050, 3841240, 4985531, 6399647, 8132044, 10237410, 12777167, 15820007, 19442436, 23729352, 28774625, 34681717, 41564304, 49546932

Offset: 3

Heinrich Ludwig, Jun 30 2017

Rotations and reflections of a selection are not counted. If they are to be counted see A289224.

			There are two nonequivalent ways to choose three 2 X 2 X 2 triangles (aaa, bbb, ccc) from a 4 X 4 X 4 point grid:
      a           a
     a a         a a
    b c c       b . c
   b b c .     b b c c
Note: aaa, bbb, ccc are not distinguishable, they are denoted differently for a better perception of the 2 X 2 X 2 triangles only.

Heinrich Ludwig, Table of n, a(n) for n = 3..100
Index entries for linear recurrences with constant coefficients, signature (5,-9,6,0,0,0,-6,9,-5,1).

Cf. A289224, A289229, A117662, A289231, A289232.

concat(0, Vec(x^4*(2 + 9*x + 50*x^2 + 60*x^3 + 37*x^4 - 21*x^5 - 20*x^6 - 4*x^7 + 7*x^8) / ((1 - x)^7*(1 + x)*(1 + x + x^2)) + O(x^40))) \\ Colin Barker, Jun 30 2017

a(n) = (n^6 -6*n^5 -24*n^4 +220*n^3 -153*n^2 -1488*n +2592)/36 + IF(MOD(n, 2) = 1, -1)/2 + IF(MOD(n, 3) = 1, -2)/9.

G.f.: x^4*(2 + 9*x + 50*x^2 + 60*x^3 + 37*x^4 - 21*x^5 - 20*x^6 - 4*x^7 + 7*x^8) / ((1 - x)^7*(1 + x)*(1 + x + x^2)). - Colin Barker, Jun 30 2017

A289231 Number of nonequivalent ways to select 4 disjoint point triples from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.

Original entry on oeis.org

0, 4, 159, 1644, 9548, 38872, 125367, 342831, 829052, 1822785, 3714519, 7113539, 12935256, 22511616, 37728563, 61194888, 96446684, 148191316, 222597315, 327633979, 473466444, 672912717, 941968139, 1300402591, 1772439504, 2387521212, 3181168199, 4195941108, 5482512012

Offset: 4

Heinrich Ludwig, Jun 30 2017

Rotations and reflections of a selection are not counted. If they are to be counted see A289225.

			There are four nonequivalent ways to choose four 2 X 2 X 2 triangles (aaa, ..., ddd) from a 5 X 5 X 5 point grid:
      a           a           a           .
     a a         a a         a a         a a
    b c c       . d .       . . .       . a .
   b b c d     b d d c     b c c d     b c c d
  . . . d d   b b . c c   b b c d d   b b c d d
Note: aaa, ..., ddd are not distinguishable, they are denoted differently for a better perception of the 2 X 2 X 2 triangles only.

Heinrich Ludwig, Table of n, a(n) for n = 4..100
Index entries for linear recurrences with constant coefficients, signature (4,-4,-1,-2,8,5,-14,-1,1,14,-5,-8,2,1,4,-4,1).

Cf. A289229, A289225, A117662, A289230, A289232.

concat(0, Vec(x^5*(4 + 143*x + 1024*x^2 + 3612*x^3 + 7423*x^4 + 10001*x^5 + 8395*x^6 + 3273*x^7 - 1362*x^8 - 2393*x^9 - 878*x^10 + 488*x^11 + 539*x^12 + 101*x^13 - 89*x^14 - 41*x^15) / ((1 - x)^9*(1 + x)^2*(1 + x + x^2)^3) + O(x^40))) \\ Colin Barker, Jun 30 2017

a(n) = (n^8 -8*n^7 -50*n^6 +556*n^5 +261*n^4 -12724*n^3 +19088*n^2 +86016*n -201024)/144 + IF(MOD(n, 2) = 1, -2*n +5)/4 + IF(MOD(n, 3) = 1, -n^2 +2*n +12)/9.

G.f.: x^5*(4 + 143*x + 1024*x^2 + 3612*x^3 + 7423*x^4 + 10001*x^5 + 8395*x^6 + 3273*x^7 - 1362*x^8 - 2393*x^9 - 878*x^10 + 488*x^11 + 539*x^12 + 101*x^13 - 89*x^14 - 41*x^15) / ((1 - x)^9*(1 + x)^2*(1 + x + x^2)^3). - Colin Barker, Jun 30 2017

A289232 Number of nonequivalent ways to select 5 disjoint point triples from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.

Original entry on oeis.org

0, 77, 2569, 31951, 223346, 1089665, 4161705, 13314461, 37246668, 93781829, 216901737, 467727523, 951014654, 1839155785, 3406165049, 6074688977, 10479716856, 17553399741, 28636182537, 45620375447, 71133273514, 108768061009, 163371926729, 241402171109, 351362501892

Offset: 5

Heinrich Ludwig, Jul 01 2017

Rotations and reflections of a selection are not counted. If they are to be counted see A289226.

			There are 77 nonequivalent ways to choose five 2 X 2 X 2 triangles (aaa, ..., eee) from a 6 X 6 X 6 point grid, for example:
        .               a
       . .             a a
      . . .           . d .
     a a b b         b d d c
    c a d b e       b b e c c
   c c d d e e     . . e e . .
Note: aaa, ..., eee are not distinguishable, they are denoted differently for a better perception of the 2 X 2 X 2 triangles only.

Heinrich Ludwig, Table of n, a(n) for n = 5..100
Index entries for linear recurrences with constant coefficients, signature (8,-25,32,11,-88,99,0,-99,88,-11,-32,25,-8,1).

Cf. A289229, A117662, A289230, A289231, A289226.

concat(0, Vec(x^6*(77 + 1953*x + 13324*x^2 + 29499*x^3 + 18617*x^4 - 15880*x^5 - 17638*x^6 + 4876*x^7 + 8057*x^8 - 881*x^9 - 1966*x^10 + 81*x^11 + 201*x^12) / ((1 - x)^11*(1 + x)^3) + O(x^40))) \\ Colin Barker, Jul 01 2017

a(n) = (n^10 -10*n^9 -85*n^8 +1160*n^7 +1345*n^6 -49084*n^5 +61035*n^4 +897210*n^3 -2205196*n^2 -5725656*n +18174960)/720 + IF(MOD(n, 2) = 1, -2*n^2 +13*n -11)/4.

G.f.: x^6*(77 + 1953*x + 13324*x^2 + 29499*x^3 + 18617*x^4 - 15880*x^5 - 17638*x^6 + 4876*x^7 + 8057*x^8 - 881*x^9 - 1966*x^10 + 81*x^11 + 201*x^12) / ((1 - x)^11*(1 + x)^3). - Colin Barker, Jul 01 2017

A289233 Largest number of disjoint point triples that can be chosen from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.

Original entry on oeis.org

0, 1, 1, 3, 4, 6, 9, 11, 15, 18, 22, 26, 30, 35, 39, 45, 50, 56, 63, 69, 77, 84, 92, 100, 108, 117, 125, 135, 144, 154, 165, 175, 187, 198, 210, 222, 234, 247, 259, 273, 286, 300, 315, 329, 345, 360, 376, 392, 408, 425, 441, 459, 476, 494, 513, 531, 551, 570

Offset: 1

Heinrich Ludwig, Jul 08 2017

nonn

A001840(n-1) = floor(n*(n+1)/6) is a trivial upper bound for a(n), which is not reached for n = 3, 5, 6, 8, 15, 17, 18, 20 but for all other n <= 21.
From Jon E. Schoenfield, Aug 16 2017: (Start)
If n is even, then the bottom three rows of points can be assembled into n-1 of the 3-point triangles; e.g., the full grid for n = 8 has 8*9/2 = 36 points, of which the 21 points in the bottom three rows can be assembled into 7 three-point triangles as follows, leaving the remaining 15 points in the same triangular arrangement as in the full grid for the n = 5 case:
.
Row 1:                .
.
Row 2:              .   .
.
Row 3:            .   .   .
.
Row 4:          .   .   .   .
.
Row 5:        .   .   .   .   .
.
Row 6:      2---2   4---4   6---6
.            \ /     \ /     \ /
Row 7:    1   2   3   4   5   6   7
.        / \     / \     / \     / \
Row 8:  1---1   3---3   5---5   7---7
.
Thus, if n is even, then a(n) >= a(n-3) + n - 1.
Similarly, if n mod 3 = 2, then the bottom two rows of points can be assembled into (2n-1)/3 of the 3-point triangles; e.g., of the 36 points in the full grid for n = 8, the 15 points in the bottom two rows can be assembled into 5 three-point triangles as follows, leaving the remaining 21 points in the same triangular arrangement as in the full grid for the n=6 case:
.
Row 1:                     .
.
Row 2:                   .   .
.
Row 3:                 .   .   .
.
Row 4:               .   .   .   .
.
Row 5:             .   .   .   .   .
.
Row 6:           .   .   .   .   .   .
.
Row 7:         1   2---2   3   4---4   5
.             / \   \ /   / \   \ /   / \
Row 8:       1---1   2   3---3   4   5---5
.
Thus, if n mod 3 = 2, then a(n) >= a(n-2) + (2n-1)/3.
Given the terms through a(21) = 77, the two lower bounds above and the upper bound a(n) <= floor(n(n+1)/6) are sufficient to establish that a(22) = 84, a(23) = 92, a(24) = 100, a(26) = 117, and a(28) = 135. (A solution with 108 three-point triangles can be constructed on the n = 25 grid.)
Conjecture: a(n) = floor((n(n+1) - floor(((n+3) mod 12)/6))/6); i.e., the upper bound floor(n(n+1)/6) can be reached unless n(n+1)/2 is a multiple of 3 and (n+3) mod 12 >= 6, in which case a(n) falls short of the upper bound by 1. (End)
a(31) = 165, a(33) = 187, a(34) = 198, a(35) = 210, a(36) = 222, a(37) = 234, a(38) = 247, and a(40) = 273. - Rob Pratt, Dec 19 2017
From Jon E. Schoenfield, Dec 21 2017: (Start)
If we refer to a triangular grid with n points on each side simply as an "n-triangle", then for any n > 13, the n-triangle can be broken into an (n-12)-triangle, a 12-triangle, and a parallelogram-shaped grid with 12 points on each of two opposite sides and n-12 points on each of the other two sides (with n-12 > 1). E.g., we can break the 21-triangle into (1) a 9-triangle, (2) a 12-triangle, and (3) a 9 X 12 parallelogram grid:
                         _________
                        1          ^
                       1 1         |
                      1 1 1        |
                     1 1 1 1       |
                    1 1 1 1 1      9
                   1 1 1 1 1 1     |
                  1 1 1 1 1 1 1    |
                 1 1 1 1 1 1 1 1   |
                1 1 1 1 1 1 1 1 1__v
                                  _______________
              2  3 3 3 3 3 3 3 3 3                ^
             2 2  3 3 3 3 3 3 3 3 3               |
            2 2 2  3 3 3 3 3 3 3 3 3              |
           2 2 2 2  3 3 3 3 3 3 3 3 3             |
          2 2 2 2 2  3 3 3 3 3 3 3 3 3            |
         2 2 2 2 2 2  3 3 3 3 3 3 3 3 3          12
        2 2 2 2 2 2 2  3 3 3 3 3 3 3 3 3          |
       2 2 2 2 2 2 2 2  3 3 3 3 3 3 3 3 3         |
      2 2 2 2 2 2 2 2 2  3 3 3 3 3 3 3 3 3        |
     2 2 2 2 2 2 2 2 2 2  3 3 3 3 3 3 3 3 3       |
    2 2 2 2 2 2 2 2 2 2 2  3 3 3 3 3 3 3 3 3      |
   2 2 2 2 2 2 2 2 2 2 2 2  3 3 3 3 3 3 3 3 3 ____v
  |                       ||                 |
  |<---------12---------->||<-------9------->|
.
All points of a 2 X 12 parallelogram grid and all points of a 3 X 12 parallelogram grid can be assembled into 3-point triangles using the simple patterns
.
         o o                     o o .
          o .                     o . .
           . .                     o o .
            o o                     o . .
             o .                     o o .
              . .         and         o . .
               o o                     o o .
                o .                     o . .
                 . .                     o o .
                  o o                     o . .
                   o .                     o o .
                    . .                     o . .
.
respectively, so those patterns can be combined to assemble a k X 12 parallelogram completely into 3-point triangles for any k > 1. Thus, since both the 12-triangle and the (n-12) X 12 parallelogram grid can be completely assembled into 3-point triangles for any n > 13, we have, for n > 13, a(n) >= a(n-12) + a(12) + (n-12)*12/3, which reduces to a(n) >= a(n-12) + 4n - 22. In particular, if the trivial upper bound floor(n*(n+1)/6) is reached by a(n), then it is also reached by a(n+12k) for any positive integer k. Given a(1)..a(12), this is sufficient to prove that a(n) = floor(n*(n+1)/6) except when n mod 12 is 3, 5, 6, or 8; in those cases, a(n) >= floor(n*(n+1)/6) - 1. (End)
Theorem 1.1 of the Conway and Lagarias link indicates that all the points can be covered by 3-point triangles iff n mod 12 = 0, 2, 9, or 11. That fact, together with the above results for a(n) in the specific cases for n in [1, 3..8, 10] and the recursive lower bound a(n) >= a(n-12) + 4n - 22, is sufficient to prove that a(n) = floor(n*(n+1)/6) - d where d is 1 when n mod 12 is in [3, 5, 6, 8] and 0 otherwise. - Jon E. Schoenfield, Dec 26 2017

			From a 21 X 21 X 21 point grid up to 77 disjoint 2 X 2 X 2 triangles (aaa, bbb, ...) can be chosen. Selections like the one below with no point left are very rare compared to C(400, 77). 400 is the total number of 2 X 2 X 2 triangles in the 21-grid.
                        a
                       a a
                      c c b
                     d c b b
                    d d f f e
                   h h g f e e
                  i h g g k k j
                 i i l m m k j j
                p p l l m n q q o
               r p s t t n n q o o
              r r s s t u w w x x v
             y a a b b u u w z x v v
            y y a c b d f f z z g g e
           j j h c c d d f i k k g e e
          l j h h m m n n i i k o o p p
         l l w w q m r n s x x t o u p v
        y z z w q q r r s s x t t u u v v
       y y z f f a g g b h h c i i d j j e
      k k l l f a a g b b h c c i d d j e e
     m k n l o u u p v v q w w r x x s y y t
    m m n n o o u p p v q q w r r x s s y t t

J. H. Conway and J. C. Lagarias, Tiling with Polyominoes and Combinatorial Group Theory, JCTA 53 (1990), 183-208.
Index entries for linear recurrences with constant coefficients, signature (2, 0, -1, -2, 2, 1, 0, -2, 1).

Cf. A001840, A289222, A289229.

f[n_] := Floor[n (n +1)/6] - If[ !MemberQ[{3, 5, 6, 8}, Mod[n, 12]], 0, 1]; Array[f, 58] (* or *)
CoefficientList[ Series[(-x +x^2 -x^3 +x^4 -x^5)/((-1 +x)^3 (1 +x -x^3 +x^5 +x^6)), {x, 0, 57}], x] (* or *)
LinearRecurrence[{2, 0, -1, -2, 2, 1, 0, -2, 1}, {0, 1, 1, 3, 4, 6, 9, 11, 15}, 58] (* Robert G. Wilson v, Dec 26 2017 *)

G.f.: x*(1 - x + x^2 - x^3 + x^4) / ((1 - x)^3*(1 + x + x^2)*(1 - x^2 + x^4)) (conjectured). - Colin Barker, Jul 08 2017

a(n) = floor(n*(n+1)/6) except when n mod 12 is 3, 5, 6, or 8; in those cases, a(n) = floor(n*(n+1)/6) - 1. - Jon E. Schoenfield, Dec 25 2017

a(22)-a(26) from Jon E. Schoenfield, Aug 16 2017
a(27)-a(28) from Rob Pratt, Dec 19 2017
More terms from Jon E. Schoenfield, Dec 25 2017

cp's OEIS Frontend

A289222 Triangle read by rows: T(n, k) is the number of ways to select k disjoint point triples from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A289230 Number of nonequivalent ways to select 3 disjoint point triples from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A289231 Number of nonequivalent ways to select 4 disjoint point triples from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A289232 Number of nonequivalent ways to select 5 disjoint point triples from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A289233 Largest number of disjoint point triples that can be chosen from an n X n X n triangular point grid, each point triple forming a 2 X 2 X 2 triangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions