Fabio Visonà - cp's OEIS frontend

User: Fabio Visonà

Fabio Visonà has authored 2 sequences.

A341590 a(n) = (Sum_{j=1..3} StirlingS1(3,j)*(2^j-1)^n)/3!.

0, 0, 4, 44, 360, 2680, 19244, 136164, 957520, 6715760, 47049684, 329465884, 2306615480, 16147371240, 113034787324, 791253077204, 5538800238240, 38771687761120, 271402072608164, 1899815283098124, 13298709306209800

Offset: 0

Fabio Visonà, Feb 15 2021

Number of 3-element subsets of the powerset P([n]) such that their union is equal to the universe [n] = {1,2, ... ,n}.
StirlingS1(k,j) is a signed Stirling number of the first kind (cf. A048994).
In general, the number of k-element subsets of P([n]) such that their union is equal to [n] is (Sum_{j=0..k} StirlingS1(k,j)*(2^j-1)^n)/k!. That can be expressed also as (-1)^n*(Sum_{j=0..n} binomial(n,j)*(-1)^j*binomial(2^j,k)). See the below link to Mathematics Stack Exchange for proofs. The case k = 2 is A003462.

			For n = 2 and [n] = [2] = {1,2} the a(2) = 4 solutions are {{},{1},{2}}, {{},{1},{1,2}}, {{},{2},{1,2}}, {{1},{2},{1,2}}.

Fabio Visonà, Table of n, a(n) for n = 0..100
Mathematics Stack Exchange, Answer to question about tuples of distinct sets in P([n]) such that their union is equal to [n]
Index entries for linear recurrences with constant coefficients, signature (11,-31,21).

Cf. A003462, A016212, A048994.

LinearRecurrence[{11,-31,21},{0,0,4},30] (* Harvey P. Dale, Mar 02 2025 *)

a(n) = (Sum_{j=1..3} A048994(3,j)*(2^j-1)^n)/3!.
a(n) = (2 - 3^(1+n) + 7^n)/6.
a(n) = (-1)^n*(Sum_{j=0..n} binomial(n,j)*(-1)^j*binomial(2^j,3)).
G.f.: 4*x^2/(1 - 11*x + 31*x^2 - 21*x^3). - Stefano Spezia, Feb 15 2021
a(n) = 4 * A016212(n-2) for n >= 2. - Alois P. Heinz, Feb 15 2021

A341584 Size of the largest subset of the numbers [1..n] which does not contain a 3-term arithmetic progression modulo n.

Original entry on oeis.org

0, 1, 2, 2, 2, 2, 4, 3, 4, 4, 4, 4, 4, 4, 6, 4, 6, 5, 8, 6, 8, 6, 8, 6, 8, 7, 8, 8, 8, 8, 8, 8, 9, 8, 10, 9, 10, 10, 12, 10, 11, 9, 12, 9, 12, 10, 12, 10, 13, 10, 14, 11, 14, 11, 16, 11, 16, 12, 16, 12, 16, 13, 16, 13, 16, 14, 16, 13, 16, 14, 18, 14, 16, 14, 20, 14, 16, 14, 20, 15, 18

Offset: 0

Fabio Visonà, Feb 15 2021

This is similar to A003002, but the arithmetic progression is modulo n here.

For n >= 3, a(n) can be viewed as the maximum number of vertices that can be chosen from a regular polygon with n sides so that no three of them form an isosceles or equilateral triangle.

			n, a(n), example of an optimal subset:
0, 0, {}
1, 1, {1}
2, 2, {1,2}
3, 2, {1,2}
4, 2, {1,2}
5, 2, {1,2}
6, 4, {1,2,4,5}
7, 3, {1,2,4}
8, 4, {1,2,4,5}
9, 4, {1,2,4,5}
10, 4, {1,2,4,5}
11, 4, {1,2,4,5}
12, 4, {1,2,4,5}
13, 4, {1,2,4,5}
14, 6, {1,2,4,8,9,11}
15, 4, {1,2,4,5}
16, 6, {1,3,4,8,9,11}
17, 5, {1,2,6,7,9}
18, 8, {1,2,4,5,10,11,13,14}
19, 6, {1,3,4,8,9,11}
20, 8, {1,2,4,5,11,12,14,15}

Math StackExchange, A question about this sequence.

Cf. A003002.

/* For n >= 3: */
int a(int n)
{
int upp, maxb, s, i, l, h, maxs;
uint64_t b, bs, m, mv[31], mn;
for (l = 1; l <= 31; l++) { mv[l - 1] = 1 << 2*l; mv[l - 1] |= (1 << l); mv[l - 1] |= 1; }
maxb = 1 << n; mn = maxb - 1; h = (n - 1) / 2; maxs = 2*n/3; upp = 0;
for (b = 0; b < maxb; b++) {
  for (i = 0, s = 0, m = 1; i < n; i++, m <<= 1) { if (b & m) s++; }
  if (s <= maxs) {
   for (l = 1; l <= h; l++) {
    m = mv[l - 1];
    for (i = 0; i < n; i++) { if ((b & m) == m) { l = 1000; break; } m = ((m << 1) & mn) | (m >> (n - 1)); }
   }
   if (l < 1000 && s > upp) upp = s;
  }
}
return upp;
}

a(31)-a(80) from Bert Dobbelaere, Feb 20 2021

cp's OEIS Frontend

User: Fabio Visonà

A341590 a(n) = (Sum_{j=1..3} StirlingS1(3,j)*(2^j-1)^n)/3!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula