A090245 -id:A090245 - cp's OEIS frontend

A016142 Expansion of 1/((1-3x)(1-9*x)).

1, 12, 117, 1080, 9801, 88452, 796797, 7173360, 64566801, 581120892, 5230147077, 47071500840, 423644039001, 3812797945332, 34315186290957, 308836690967520, 2779530261754401, 25015772484929772, 225141952751788437, 2026277575928357400, 18236498186842001001, 164128483692038362212

Offset: 0

N. J. A. Sloane

a(n) is the number of lattices L in Z^(n+1) such that the quotient group Z^(n+1) / L is C_9. - Álvar Ibeas, Nov 29 2015

In the game of SET with four attributes there are 1080 potential SETs. See A090245. In the generalized game of SET with different numbers of attributes, the number of potential SETs is a(n+1). - Robert Price, Oct 14 2017

Vincenzo Librandi, Table of n, a(n) for n = 0..200
A. M. Hinz, S. Klavžar, U. Milutinović, C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 100. Book's website.
Index entries for linear recurrences with constant coefficients, signature (12,-27).

Cf. A006100, A090245.

[(1/6)*(9^(n+1)-3^(n+1)): n in [0..20]]; // Vincenzo Librandi, Feb 24 2014

Join[{a=1,b=12},Table[c=12*b-27*a;a=b;b=c,{n,60}]] (* Vladimir Joseph Stephan Orlovsky, Jan 31 2011 *)
CoefficientList[Series[1/((1-3x)(1-9x)),{x,0,20}],x] (* or *) Table[ (9^(n+1) -3^(n+1))/6,{n,0,20}]  (* Harvey P. Dale, Apr 03 2011 *)
Table[ncards = 3^nattr; (ncards*(ncards - 1))/6, {nattr, 1, 20}] (* Robert Price, Oct 14 2017 *)

Vec(1/((1-3*x)*(1-9*x))+O(x^99)) \\ Charles R Greathouse IV, Sep 26 2012

a(n) = (1/6)*(9^(n+1) - 3^(n+1)); \\ Joerg Arndt, Feb 23 2014

[lucas_number1(n,12,27) for n in range(1, 20)] # Zerinvary Lajos, Apr 27 2009

a(n) = (1/6)*(9^(n+1) - 3^(n+1)).
a(n-1) = Sum_{i=1..n} binomial(n,i)*3^(n-i)*6^(i-1). - Sam Handler (sam_5_5_5_0(AT)yahoo.com), Jun 29 2004
a(n) = 12*a(n-1) - 27*a(n-2), a(0)=1, a(1)=12. - Vincenzo Librandi, Mar 14 2011
a(n) = A006100(n+2) - A006100(n+1), for n > 0. - Álvar Ibeas, Nov 29 2015
E.g.f.: exp(3*x)*(3*exp(3*x) - 1)/2. - Elmo R. Oliveira, Mar 08 2025

A253586 The sum of the i-th ternary digits of n, k, and A(n,k) equals 0 (mod 3) for each i>=0 (leading zeros included); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

0, 2, 2, 1, 1, 1, 6, 0, 0, 6, 8, 8, 2, 8, 8, 7, 7, 7, 7, 7, 7, 3, 6, 6, 3, 6, 6, 3, 5, 5, 8, 5, 5, 8, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 18, 3, 3, 0, 3, 3, 0, 3, 3, 18, 20, 20, 5, 2, 2, 5, 2, 2, 5, 20, 20, 19, 19, 19, 1, 1, 1, 1, 1, 1, 19, 19, 19, 24, 18, 18, 24, 0, 0, 6, 0, 0, 24, 18, 18, 24

Offset: 0

Alois P. Heinz, Jan 04 2015

			Square array A(n,k) begins:
  0, 2, 1, 6, 8, 7, 3, 5, 4, ...
  2, 1, 0, 8, 7, 6, 5, 4, 3, ...
  1, 0, 2, 7, 6, 8, 4, 3, 5, ...
  6, 8, 7, 3, 5, 4, 0, 2, 1, ...
  8, 7, 6, 5, 4, 3, 2, 1, 0, ...
  7, 6, 8, 4, 3, 5, 1, 0, 2, ...
  3, 5, 4, 0, 2, 1, 6, 8, 7, ...
  5, 4, 3, 2, 1, 0, 8, 7, 6, ...
  4, 3, 5, 1, 0, 2, 7, 6, 8, ...

Alois P. Heinz, Antidiagonals n = 0..200, flattened
Rémy Sigrist, Colored representation of the table for 0 <= n, k < 3^7 (where the hue is function of T(n, k))
Wikipedia, Set (game)

Column k=0 and row n=0 gives A004488.
Main diagonal gives A001477.
A(n,floor(n/3)) gives A060587.
Cf. A090245, A253587.

A:= proc(n, k) local i, j; `if`(n=0 and k=0, 0,
      A(iquo(n, 3, 'i'), iquo(k, 3, 'j'))*3 +irem(6-i-j, 3))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..14);

A(n,k) = A(floor(n/3),floor(k/3))*3+(6-(n mod 3)-(k mod 3) mod 3), A(0,0) = 0.

A253587 The sum of the i-th ternary digits of n, k, and T(n,k) equals 0 (mod 3) for each i>=0 (leading zeros included); triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Original entry on oeis.org

0, 2, 1, 1, 0, 2, 6, 8, 7, 3, 8, 7, 6, 5, 4, 7, 6, 8, 4, 3, 5, 3, 5, 4, 0, 2, 1, 6, 5, 4, 3, 2, 1, 0, 8, 7, 4, 3, 5, 1, 0, 2, 7, 6, 8, 18, 20, 19, 24, 26, 25, 21, 23, 22, 9, 20, 19, 18, 26, 25, 24, 23, 22, 21, 11, 10, 19, 18, 20, 25, 24, 26, 22, 21, 23, 10, 9, 11

Offset: 0

Alois P. Heinz, Jan 04 2015

			Triangle T(n,k) begins:
  0;
  2, 1;
  1, 0, 2;
  6, 8, 7, 3;
  8, 7, 6, 5, 4;
  7, 6, 8, 4, 3, 5;
  3, 5, 4, 0, 2, 1, 6;
  5, 4, 3, 2, 1, 0, 8, 7;
  4, 3, 5, 1, 0, 2, 7, 6, 8;

Alois P. Heinz, Rows n = 0..200, flattened
Wikipedia, Set (game)

Column k=0 gives A004488.
Main diagonal gives A001477.
T(n,floor(n/3)) gives A060587.
Cf. A090245, A253586.

T:= proc(n, k) local i, j; `if`(n=0 and k=0, 0,
      T(iquo(n, 3, 'i'), iquo(k, 3, 'j'))*3 +irem(6-i-j, 3))
    end:
seq(seq(T(n, k), k=0..n), n=0..14);

T(n,k) = T(floor(n/3),floor(k/3))*3+(6-(n mod 3)-(k mod 3) mod 3), T(0,0) = 0.

A090246 The largest subset of P(Z/3Z)^n that does not contain 3 collinear points.

Original entry on oeis.org

2, 4, 10, 20, 56

Offset: 1

Hans Havermann, Jan 23 2004

P(Z/3Z)^n is the projective space of n dimensions over the finite field Z/3Z. This is the size of the largest subset which does not contain 3 points lying in a line.
Davis and Maclagan described a game similar to the game SET that could be played in this space using projective lines, rather than in (Z/3Z)^n using the algebraic notion of line. This sequence is the analog of A090245 for this game.
So far this sequence agrees with A104442.

B. Davis and D. Maclagan, The Card Game SET, The Mathematical Intelligencer, Vol. 25:3 (Summer 2003), pp. 33-40.
B. L. Davis and D. Maclagan, The Card Game SET [From _Omar E. Pol_, Feb 21 2009]
Ivars Peterson, SET Math.
Ivars Peterson, SET Math [From _Omar E. Pol_, Feb 21 2009]

Cf. A090245.

Edited by Jack W Grahl, May 12 2009

A156989 Largest size of a subset of {1,2,3}^n that does not contain any combinatorial lines (i.e., strings formed by 1, 2, 3, and at least one instance of a wildcard x, with x then substituted for 1, 2, or 3, e.g. 12x3x gives the combinatorial line 12131, 12232, 12333.)

Original entry on oeis.org

1, 2, 6, 18, 52, 150, 450

Offset: 0

Terence Tao, Feb 20 2009

The density Hales-Jewett theorem implies that a(n) = o(3^n). a(n) is studied further in the polymath1 project, see link below.

			For n=2, one example that shows a(2) is at least 6 is { 11, 13, 22, 23, 31, 32 }.

H. Furstenberg, Y. Katznelson, A density version of the Hales-Jewett theorem for k=3, Graph Theory and Combinatorics (Cambridge, 1988). Discr. Math. 75 (1989) no. 1-3, 227-241.
H. Furstenberg and Y. Katznelson, A density version of the Hales-Jewett theorem, J. Anal. Math. 57 (1991), 64-119.
K. O'Bryant, Sets of natural numbers with proscribed subsets, arXiv:1410.4900 [math.NT], 2014-2015.
K. O'Bryant, Sets of Natural Numbers with Proscribed Subsets, J. Int. Seq. 18 (2015) # 15.7.7
D. H. J. Polymath, Density Hales-Jewett and Moser numbers, arXiv:1002.0374 [math.CO]
Polymath1 Project, Wiki Main Page
Terence Tao, Bounds for the first few density Hales-Jewett numbers, and related quantities

Bounded below by A003142. Cf. A000244, A090245.

A144686 Maximal size of a connected acyclic domain of permutations of n elements with diameter n*(n-1)/2.

Original entry on oeis.org

1, 2, 4, 9, 20, 45, 100

Offset: 1

N. J. A. Sloane, Feb 07 2009

a(n) is at most 2.487^n and at least 2.076^n for large enough n (see Felsner & Valtr). Originally conjectured to equal A144685, but in fact a(n) is asymptotically larger and exceeds A144685 at least for n >= 34 (see Karpov & Slinko). - Clayton Thomas, Aug 19 2019 [Updated by Andrey Zabolotskiy, Dec 31 2023]

B. Monjardet, Acyclic domains of linear orders: a survey, in "The Mathematics of Preference, Choice and Order: Essays in Honor of Peter Fishburn", edited by Steven Brams, William V. Gehrlein and Fred S. Roberts, Springer, 2009, pp. 139-160.

James Abello, The Weak Bruhat Order of S_Sigma, Consistent Sets, and Catalan Numbers, SIAM Journal on Discrete Mathematics, 4 (1991), 1-16; alternative link.
James Abello, The Majority Rule and Combinatorial Geometry (via the Symmetric Group), Annales Du Lamsade, 3 (2004), 1-13.
Vladimir I. Danilov, Alexander V. Karzanov, and Gleb Koshevoy, Condorcet domains of tiling type, Discrete Applied Mathematics 160.7-8 (2012), pages 933-940.
Stefan Felsner and Pavel Valtr, Coding and counting arrangements of pseudolines, Discrete & Computational Geometry 46.3 (2011), pages 405-416.
Alexander Karpov and Arkadii Slinko, Constructing large peak-pit Condorcet domains, Theory and Decision, 94 (2023), 97-120.
B. Monjardet, Acyclic domains of linear orders: a survey, in "The Mathematics of Preference, Choice and Order: Essays in Honor of Peter Fishburn", edited by Steven Brams, William V. Gehrlein and Fred S. Roberts, Springer, 2009, pp. 139-160 ⟨halshs-00198635⟩.

Cf. A090245 (has same initial terms but probably is unrelated), A144685, A144687, A369614.

a(1)-a(2) added and name edited by Andrey Zabolotskiy, Dec 31 2023

A236397 Weight of the largest-weight sunflower-free set of width n.

Original entry on oeis.org

1, 2, 4, 8, 20, 40, 96, 224

Offset: 0

N. J. A. Sloane, Jan 28 2014

Peebles conjectures that if n is even, a(n+1) = 2*A090245(n).

J. Peebles, Cap Set Bounds and Matrix Multiplication, Senior Thesis, Harvey Mudd College, 2013.

Cf. A090245.

A292773 a(n) is the least integer m such that any choice of m elements in (Z_3)^n contains a subset of size 3 whose sum is zero.

Original entry on oeis.org

5, 9, 19, 41, 91, 225

Offset: 1

N. J. A. Sloane, Sep 30 2017

Y. Edel, C. Elsholtz, A. Geroldinger, S. Kubertin and L. Rackham, Zero-sum problems in finite abelian groups and affine caps, Quarterly Journal of Mathematics 58 (2), 159-186.
Christian Elsholtz, Lower bounds for multidimensional zero sums, Combinatorica 24.3 (2004): 351-358.
H. Harborth, Ein Extremalproblem für Gitterpunkte, J. Reine Angew. Math. 262 (1973), 356-360.
Aaron Potechin, Maximal caps in AG (6, 3), Designs, Codes and Cryptography volume 46, pages 243-259 (2008).

Cf. A090245.

a(n) = 2*A090245(n) + 1, (follows from Harborth, Hilfssatz 3). - C. Elsholtz, Oct 04 2021

a(6), based on Potechin's paper, added by C. Elsholtz, Oct 04 2021

A380167 Maximum number of sets for the SET card game for n cards with 3 properties where each can take 3 values.

Original entry on oeis.org

1, 1, 2, 3, 5, 8, 12, 12, 13, 14, 16, 19, 23, 26, 30, 36, 41, 47, 54, 62, 71, 81, 92, 104, 117

Offset: 3

Justin Stevens, Jan 22 2025

Also the maximum number of lines for n points in F_3^3 where a line is defined as three points p, q, r such that p+q+r = 0.

			For n=3, the maximum number of SETs with 3 cards is 1 hence a(3)=1.
For n=4, no additional SETs can be formed, hence a(4)=1.
For n=5, we can take a 3-card SET, say {p, q, r}. Then, for two additional cards, s and t, outside of the SET, the only possible way this can form a SET is if we have one element from the first SET plus s and t form a SET. An example of this with the 4 properties being coordinates from 0 to 2 in mod 3 (in the equivalent definition of a SET) is the points {(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 0, 2), (0, 0, 1, 0), (0, 0, 2, 0)} which form 2 SETs. Hence a(5)=2.

Justin Stevens and Duncan Wilson, The Maximum Number of Sets for 12 Cards is 14, arXiv:2501.12565 [math.CO], 2025.
Jim Vinci, The maximum number of sets for n cards and the total number of internal sets for all partitions of the deck, 2009.

Cf. A090245 for a complementary sequence of the maximum number of cards with no sets.

Cf. A182240 for the number of ways to select n cards which is the search space complexity of this sequence for 4 properties instead of 3.

from itertools import combinations
def add_mod3(a, b, c):
    """Component-wise addition mod 3 of two 3D tuples."""
    return tuple((a[i] + b[i] + c[i]) % 3 for i in range(3))
def is_set(a,b,c):
    """Returns true if three elements form a set."""
    return add_mod3(a,b,c) == (0,0,0)
if _name_ == "_main_":
    all_points = [(x,y,z) for x in range(3) for y in range(3) for z in range(3)]
    max_sets = 0
    for n in range(3, 28):
        for comb in combinations(all_points, n):
            num_sets = 0
            for possible_set in combinations(comb, 3):
                if is_set(possible_set[0], possible_set[1], possible_set[2]):
                    num_sets += 1
            if num_sets > max_sets:
                max_sets = num_sets
        print("Max sets for %d cards: %d"%(n, max_sets))

cp's OEIS Frontend

A016142 Expansion of 1/((1-3*x)*(1-9*x)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

PARI

Sage

Formula

A253586 The sum of the i-th ternary digits of n, k, and A(n,k) equals 0 (mod 3) for each i>=0 (leading zeros included); square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A253587 The sum of the i-th ternary digits of n, k, and T(n,k) equals 0 (mod 3) for each i>=0 (leading zeros included); triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A090246 The largest subset of P(Z/3Z)^n that does not contain 3 collinear points.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A156989 Largest size of a subset of {1,2,3}^n that does not contain any combinatorial lines (i.e., strings formed by 1, 2, 3, and at least one instance of a wildcard x, with x then substituted for 1, 2, or 3, e.g. 12x3x gives the combinatorial line 12131, 12232, 12333.)

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A144686 Maximal size of a connected acyclic domain of permutations of n elements with diameter n*(n-1)/2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A236397 Weight of the largest-weight sunflower-free set of width n.

Views

Author

Keywords

Comments

Links

Crossrefs

A292773 a(n) is the least integer m such that any choice of m elements in (Z_3)^n contains a subset of size 3 whose sum is zero.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A380167 Maximum number of sets for the SET card game for n cards with 3 properties where each can take 3 values.

Views

Author

Keywords

Comments

A016142 Expansion of 1/((1-3x)(1-9*x)).