Marcel K. Goh - cp's OEIS frontend

A360285 Triangle read by rows: T(n,k) is the number of subsets of {1,...,n} of cardinality k in which no two elements are coprime; n >= 0, 0 <= k <= floor(n/2) + [n=1].

1, 1, 1, 1, 2, 1, 3, 1, 4, 1, 1, 5, 1, 1, 6, 4, 1, 1, 7, 4, 1, 1, 8, 7, 4, 1, 1, 9, 9, 5, 1, 1, 10, 14, 11, 5, 1, 1, 11, 14, 11, 5, 1, 1, 12, 21, 24, 16, 6, 1, 1, 13, 21, 24, 16, 6, 1, 1, 14, 28, 39, 36, 21, 7, 1, 1, 15, 34, 48, 41, 22, 7, 1, 1, 16, 41, 69, 76, 57, 28, 8, 1

Offset: 0

Marcel K. Goh, Feb 01 2023

			Triangle T(n,k) begins:
   n/k 0  1  2  3  4 5 6
   0   1
   1   1  1
   2   1  2
   3   1  3
   4   1  4  1
   5   1  5  1
   6   1  6  4  1
   7   1  7  4  1
   8   1  8  7  4  1
   9   1  9  9  5  1
  10   1 10 14 11  5 1
  11   1 11 14 11  5 1
  12   1 12 21 24 16 6 1
  ...
For n=8 and k=3 the T(8,3)=4 sets are {2,4,6}, {2,4,8}, {2,6,8}, and {4,6,8}.

Marcel K. Goh and Jonah Saks, Alternating-sum statistics for certain sets of integers, arXiv:2206.12535 [math.CO], 2022.

Cf. A056171, A355146.

A355147 Triangle read by rows: T(n,k) is the number of product-free subsets of {1,...,n} with cardinality k; n >= 0, 0 <= k <= A028391(n).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 3, 2, 1, 4, 5, 2, 1, 5, 9, 6, 1, 1, 6, 14, 15, 7, 1, 1, 7, 20, 29, 22, 8, 1, 1, 8, 26, 43, 38, 17, 3, 1, 9, 34, 68, 76, 47, 15, 2, 1, 10, 43, 102, 144, 123, 62, 17, 2, 1, 11, 53, 143, 234, 238, 149, 55, 11, 1, 1, 12, 64, 196, 377, 472, 387, 204, 66, 12, 1

Offset: 0

Marcel K. Goh, Jun 28 2022

S is product-free if for any i,j in S, not necessarily distinct, i*j is not in S.

For n >= 2, the alternating row sums give 0.

			Triangle T(n,k) begins:
  n/k 0  1  2   3   4   5   6  7  8 9
   0  1
   1  1
   2  1  1
   3  1  2  1
   4  1  3  2
   5  1  4  5   2
   6  1  5  9   6   1
   7  1  6 14  15   7   1
   8  1  7 20  29  22   8   1
   9  1  8 26  43  38  17   3
  10  1  9 34  68  76  47  15  2
  11  1 10 43 102 144 123  62 17  2
  12  1 11 53 143 234 238 149 55 11 1
  ...
For n=5 and k=3 the T(5,3) = 2 sets are {2,3,5} and {3,4,5}.

Marcel K. Goh and Jonah Saks, Alternating-sum statistics for certain sets of integers, arXiv:2206.12535 [math.CO], 2022.

Row sums give A326489.

Cf. A028391.

A355146 Triangle read by rows: T(n,k) is the number of subsets of {1,...,n} of cardinality k in which every pair of elements is coprime; n >= 0, 0 <= k <= A036234(n).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 5, 2, 1, 5, 9, 7, 2, 1, 6, 11, 8, 2, 1, 7, 17, 19, 10, 2, 1, 8, 21, 25, 14, 3, 1, 9, 27, 37, 24, 6, 1, 10, 31, 42, 26, 6, 1, 11, 41, 73, 68, 32, 6, 1, 12, 45, 79, 72, 33, 6, 1, 13, 57, 124, 151, 105, 39, 6, 1, 14, 63, 138, 167, 114, 41, 6

Offset: 0

Marcel K. Goh, Jun 27 2022

For n >= 1, the alternating row sums equal 0.

			Triangle T(n,k) begins:
  n/k 0  1  2  3  4  5 6
  0   1
  1   1  1
  2   1  2  1
  3   1  3  3  1
  4   1  4  5  2
  5   1  5  9  7  2
  6   1  6 11  8  2
  7   1  7 17 19 10  2
  8   1  8 21 25 14  3
  9   1  9 27 37 24  6
  10  1 10 31 42 26  6
  11  1 11 41 73 68 32 6
  12  1 12 45 79 72 33 6
  ...
For n=8 and k=5 the T(8,5)=3 sets are {1,2,3,5,7}, {1,3,4,5,7}, and {1,3,5,7,8}.

Marcel K. Goh and Jonah Saks, Alternating-sum statistics for certain sets of integers, arXiv:2206.12535 [math.CO], 2022.

Row sums give A084422.

Cf. A000720, A036234, A186974, A320436.

A355145 Triangle read by rows: T(n,k) is the number of primitive subsets of {1,...,n} of cardinality k; n>=0, 0<=k<=ceiling(n/2).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 3, 1, 1, 4, 2, 1, 5, 5, 2, 1, 6, 7, 3, 1, 7, 12, 10, 3, 1, 8, 16, 15, 5, 1, 9, 22, 26, 13, 2, 1, 10, 28, 38, 22, 4, 1, 11, 37, 66, 60, 26, 4, 1, 12, 43, 80, 76, 35, 6, 1, 13, 54, 123, 156, 111, 41, 6, 1, 14, 64, 161, 227, 180, 74, 12

Offset: 0

Marcel K. Goh, Jun 20 2022

A set is primitive if it does not contain distinct i and j such that i divides j.

For n >= 2, the alternating row sums equal -1.

			Triangle T(n,k) begins:
   n/k 0  1  2  3  4  5  6  7  8  9 10 11 12
    0  1
    1  1  1
    2  1  2
    3  1  3  1
    4  1  4  2
    5  1  5  5  2
    6  1  6  7  3
    7  1  7 12 10  3
    8  1  8 16 15  5
    9  1  9 22 26 13  2
   10  1 10 28 38 22  4
   11  1 11 37 66 60 26  4
   12  1 12 43 80 76 35  6
   ...
For n=6 and k=3 the T(6,3) = 3 primitive sets are {2,3,5}, {3,4,5}, and {4,5,6}.

Marcel K. Goh and Jonah Saks, Alternating-sum statistics for certain sets of integers, arXiv:2206.12535 [math.CO], 2022.

Columns k=0..2 give: A000012, A000027, A161664.
Row sums give A051026.
T(2n,n) gives A174094.
T(2n-1,n) gives A192298 for n>=1.
Cf. A087077, A087086.

Sum_{k=1..ceiling(n/2)} k * T(n,k) = A087077(n). - Alois P. Heinz, Jun 24 2022

A347580 Triangle read by rows: T(n,k) is the number of chains of length k in the poset of all arithmetic progressions contained in {1,...,n} of length in the range [1..n-1], ordered by inclusion.

Original entry on oeis.org

1, 1, 2, 1, 6, 6, 1, 12, 24, 12, 1, 21, 68, 72, 24, 1, 32, 144, 244, 180, 48, 1, 47, 283, 666, 764, 432, 96, 1, 64, 486, 1510, 2436, 2164, 1008, 192, 1, 85, 799, 3117, 6534, 8028, 5816, 2304, 384, 1, 109, 1232, 5860, 15368, 24524, 24516, 15040, 5184, 768

Offset: 1

Marcel K. Goh, Sep 07 2021

Let L_n be the lattice of all arithmetic progressions contained in {1,...,n}, including the empty progression and the whole interval. T(n,k) is the number of chains of length k+2 in L_n that contain both the maximal and minimal element.

			Triangle begins:
  n/k 1   2    3     4     5      6      7      8      9    10    11   12
   1  1
   2  1   2
   3  1   6    6
   4  1  12   24    12
   5  1  21   68    72    24
   6  1  32  144   244   180     48
   7  1  47  283   666   764    432     96
   8  1  64  486  1510  2436   2164   1008    192
   9  1  85  799  3117  6534   8028   5816   2304    384
  10  1 109 1232  5860 15368  24524  24516  15040   5184   768
  11  1 137 1838 10418 33049  65402  84284  70992  37760 11520  1536
  12  1 167 2611 17420 65706 157010 250332 270996 197280 92608 25344 3072

M. K. Goh, J. Hamdan, and J. Saks, The lattice of arithmetic progressions, arXiv:2106.05949 [math.CO], 2021. See Table 2 p. 7.

Cf. A008683, A338993.

t[n_, k_] := If[k == 1, n, Sum[2(n-(k-1) r), {r, 1, Quotient[n-1, k-1]}]];
f[n_, k_] := If[k == 1, n, t[n, k]/2];
T[n_, k_] := T[n, k] = If[k == 1, 1, Sum[f[n, i] T[i, k-1], {i, 1, n-1}]];
Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* Jean-François Alcover, Sep 13 2021, from PARI code *)

t(n, k) = if (k==1, n, sum(r=1, (n-1)\(k-1), 2*(n-(k-1)*r))); \\ A338993
f(n, k) = if (k==1, n, t(n,k)/2);
T(n, k) = if (k==1, 1, sum(i=1, n-1, f(n, i)*T(i, k-1))); \\ Michel Marcus, Sep 11 2021

Let f(n,k) = n, if k=1; A338993(n,k)/2, if 2<=k<=n. Then T(n,k) = 1, if k=1; Sum_{i=1..n-1} f(n,k)*T(i,k-1), if 2<=k<=n; 0, if k>n.

Sum_{k=1..n} (-1)^k*T(n,k) = A008683(n-1), for n>=2.

A341822 Length of the longest 2-increasing sequence of positive integer triples with entries <= n.

Original entry on oeis.org

1, 2, 4, 8, 10, 14, 17, 21, 27, 30, 35

Offset: 1

Marcel K. Goh, Feb 20 2021

A triple t=(a_1,a_2,a_3) is defined to be 2-less than a triple u=(b_1,b_2,b_3) if a_i < b_i for at least two coordinates i. A sequence t^(j) of triples is 2-increasing if for all i < j, t^(i) is 2-less than t^(j).

Terms n <= 5 have been confirmed by brute-force search (Table 1 of Gowers and Long (2021)).

			For n=4, the sequence (1,1,1), (1,2,2), (2,1,3), (2,2,4), (3,3,1), (3,4,2), (4,3,3), (4,4,4) has length a(4)=8 and every 2-increasing sequence of length 9 must contain a triple with some coordinate equal to 5.

W. T. Gowers and J. Long, The length of an s-increasing sequence of r-tuples, Combinatorics, Probability and Computing 30 (2021), 1-36.

W. T. Gowers and J. Long, The length of an s-increasing sequence of r-tuples, arXiv:1609.08688 [math.CO], 2016.
Po-Shen Loh, Directed paths: from Ramsey to Ruzsa and Szemerédi, arXiv:1505.07312 [math.CO], 2015.

Cf. A000093.

a(n) >= n^{3/2} when n is a perfect square.

It is conjectured that a(n) <= n^{3/2} for all n.

Edited by N. J. A. Sloane, Mar 21 2021

a(10)-a(11) and confirmation of previous terms by Bert Dobbelaere, Mar 27 2021

A339942 Triangle read by rows: T(n,k) is the number of permutations of the cyclic group Z/nZ whose longest embedded arithmetic progression has length k.

Original entry on oeis.org

1, 0, 2, 0, 0, 6, 0, 8, 8, 8, 0, 0, 40, 60, 20, 0, 0, 468, 192, 48, 12, 0, 0, 462, 3150, 1176, 210, 42, 0, 128, 4192, 27872, 6592, 1312, 192, 32, 0, 0, 57402, 182790, 99630, 19656, 2970, 378, 54, 0, 0, 67440, 1795320, 1594640, 146200, 22000, 2840, 320, 40, 0, 0, 61050, 17433130, 17373620, 4289340, 662860, 85910, 9790, 990, 110

Offset: 1

Marcel K. Goh, Dec 23 2020

For the case k=2, it can be proved that if n is a power of 2, then T(n,2)=2^{n-1}; otherwise T(n,2)=0 (Lemma 8 of Goh and Zhao (2020)). It can also be shown that T(n,n) = n*phi(n), where phi is the Euler totient function.

			Triangle T(n,k) begins:
  n/k 1   2        3         4         5        6      7     8    9  10  11
   1  1
   2  0   2
   3  0   0        6
   4  0   8        8         8
   5  0   0       40        60        20
   6  0   0      468       192        48       12
   7  0   0      462      3150      1176      210     42
   8  0 128     4192     27872      6592     1312    192    32
   9  0   0    57402    182790     99630    19656   2970   378   54
  10  0   0    67440   1795320   1594640   146200  22000  2840  320  40
  11  0   0    61050  17433130  17373620  4289340 662860 85910 9790 990 110

M. K. Goh and R. Y. Zhao, Arithmetic subsequences in a random ordering of an additive set, arXiv:2012.12339 [math.CO], 2020.

Cf. A000010, A002618, A339941.

T(n,n) = n*A000010(n).

A339941 Triangle read by rows: T(n,k) is the number of permutations of {1,...,n} whose longest embedded arithmetic progression has length k.

Original entry on oeis.org

1, 0, 2, 0, 4, 2, 0, 10, 12, 2, 0, 20, 82, 16, 2, 0, 48, 516, 134, 20, 2, 0, 104, 3232, 1480, 198, 24, 2, 0, 282, 21984, 15702, 2048, 274, 28, 2, 0, 496, 168368, 162368, 28048, 3204, 362, 32, 2, 0, 1066, 1306404, 1902496, 374194, 39420, 4720, 462, 36, 2, 0, 2460, 11064306, 23226786, 4929828, 622140, 64020, 6644, 574, 40, 2

Offset: 1

Marcel K. Goh, Dec 23 2020

Asymptotics can be found in Goh and Zhao (2020). The column k=2 corresponds to the number of 3-free permutations of 1..n, for n>=2.

			Triangle T(n,k) begins:
  n/k 1    2         3         4        5       6      7     8    9 10 11 12
   1  1
   2  0    2
   3  0    4         2
   4  0   10        12         2
   5  0   20        82        16        2
   6  0   48       516       134       20       2
   7  0  104      3232      1480      198      24      2
   8  0  282     21984     15702     2048     274     28     2
   9  0  496    168368    162368    28048    3204    362    32    2
  10  0 1066   1306404   1902496   374194   39420   4720   462   36   2
  11  0 2460  11064306  23226786  4929828  622140  64020  6644  574  40  2
  12  0 6128 101355594 298314654 68584052 9719492 913440 98472 9024 698 44 2

M. K. Goh and R. Y. Zhao, Arithmetic subsequences in a random ordering of an additive set, arXiv:2012.12339 [math.CO], 2020.

Cf. A003407 (column k=2), A338993, A339942.

A338993 Triangle read by rows: T(n,k) is the number of k-permutations of {1,...,n} that form a nontrivial arithmetic progression, 1 <= k <= n.

Original entry on oeis.org

1, 2, 2, 3, 6, 2, 4, 12, 4, 2, 5, 20, 8, 4, 2, 6, 30, 12, 6, 4, 2, 7, 42, 18, 10, 6, 4, 2, 8, 56, 24, 14, 8, 6, 4, 2, 9, 72, 32, 18, 12, 8, 6, 4, 2, 10, 90, 40, 24, 16, 10, 8, 6, 4, 2, 11, 110, 50, 30, 20, 14, 10, 8, 6, 4, 2, 12, 132, 60, 36, 24, 18, 12, 10, 8, 6, 4, 2

Offset: 1

Marcel K. Goh, Nov 17 2020

The step size ranges from 1 to floor((n-1)/(k-1)) and for each r, there are 2*(n-(k-1)*r) possible ways to form a progression.

Proof can be found in Lemma 1 of Goh and Zhao (2020).

			Triangle T(n,k) begins:
  n/k  1   2   3   4   5   6   7   8   9  10  11  12 ...
   1   1
   2   2   2
   3   3   6   2
   4   4  12   4   2
   5   5  20   8   4   2
   6   6  30  12   6   4   2
   7   7  42  18  10   6   4   2
   8   8  56  24  14   8   6   4   2
   9   9  72  32  18  12   8   6   4   2
  10  10  90  40  24  16  10   8   6   4   2
  11  11 111  50  30  20  14  10   8   6   4   2
  12  12 132  60  36  24  18  12  10   8   6   4   2
  ...
For n=4 and k=3 the T(4,3)=4 permutations are 123, 234, 321, and 432.

M. K. Goh and R. Y. Zhao, Arithmetic subsequences in a random ordering of an additive set, arXiv:2012.12339 [math.CO], 2020.

Cf. A008279.

T[n_,k_]:=If[k==1, n,Sum[2(n-(k-1)r),{r,Floor[(n-1)/(k-1)]}]]; Flatten[Table[T[n,k],{n,12},{k,n}]] (* Stefano Spezia, Nov 17 2020 *)

T(n,k) = if (k==1, n, sum(r=1, (n-1)\(k-1), 2*(n-(k-1)*r))); \\ Michel Marcus, Sep 08 2021

T(n,k) = n, if k=1; Sum_{r=1..floor((n-1)/(k-1))} 2*(n-(k-1)*r), if 2 <= k <= n.

T(n,k) = 2*n*f - (k-1)*(f^2 + f), where f = floor((n-1)/(k-1)), for 2 <= k <= n.

A338550 Number of binary trees of height n such that the number of nodes at depth d equals d+1 for every d = 0..n.

Original entry on oeis.org

1, 1, 4, 60, 3360, 705600, 558835200, 1678182105600, 19198403288064000, 840083731079104512000, 141100463472046393835520000, 91242050302344912388163665920000, 227753296409896438988240405704212480000, 2199573010737856838816729366169572868096000000, 82356764599728553816070191604819734458909327360000000

Offset: 0

Marcel K. Goh, Nov 02 2020

To satisfy the constraint, there must be n+1 nodes at depth n, and there are 2n allowed slots for a new node.

A binary tree with such a level profile contains A000217(n+1) nodes.

Cf. A000217, A007685, A203471, A296589.

Table[Product[Binomial[2k,k+1],{k,n}],{n,0,14}] (* or *)
Table[2^(n^2+n-1/24)Glaisher^(3/2)Pi^(-1/4-n/2)BarnesG[3/2+n]Gamma[1+n]/(Exp[1/8]BarnesG[3+n]),{n,0,14}] (* Stefano Spezia, Nov 02 2020 *)

a(n) = binomial(2*n,n+1)*a(n-1), a(0)=1.
a(n) = Product_{k=1..n} binomial(2*k,k+1).
a(n) = 2^(n^2+n-1/24)*A^(3/2)*Pi^(-1/4-n/2)*G(3/2 + n)*Gamma(1 + n)/(exp(1/8)*G(3 + n)) where A is the Glaisher-Kinkelin constant and G is the Barnes G function. - Stefano Spezia, Nov 02 2020
a(n) ~ A^(3/2) * 2^(-7/24 + n + n^2) * exp(-1/8 + n/2) / (n^(11/8 + n/2) * Pi^((n+1)/2)), where A = A074962 is the Glaisher-Kinkelin constant. - Vaclav Kotesovec, Aug 29 2023
a(n) = Product_{1 <= j <= i <= n-1}  (i + j + 2)/(i - j + 1). - Peter Bala, Oct 25 2024

cp's OEIS Frontend

User: Marcel K. Goh

A360285 Triangle read by rows: T(n,k) is the number of subsets of {1,...,n} of cardinality k in which no two elements are coprime; n >= 0, 0 <= k <= floor(n/2) + [n=1].

Views

Author

Keywords

Examples

Links

Crossrefs

A355147 Triangle read by rows: T(n,k) is the number of product-free subsets of {1,...,n} with cardinality k; n >= 0, 0 <= k <= A028391(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A355146 Triangle read by rows: T(n,k) is the number of subsets of {1,...,n} of cardinality k in which every pair of elements is coprime; n >= 0, 0 <= k <= A036234(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A355145 Triangle read by rows: T(n,k) is the number of primitive subsets of {1,...,n} of cardinality k; n>=0, 0<=k<=ceiling(n/2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A347580 Triangle read by rows: T(n,k) is the number of chains of length k in the poset of all arithmetic progressions contained in {1,...,n} of length in the range [1..n-1], ordered by inclusion.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A341822 Length of the longest 2-increasing sequence of positive integer triples with entries <= n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A339942 Triangle read by rows: T(n,k) is the number of permutations of the cyclic group Z/nZ whose longest embedded arithmetic progression has length k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A339941 Triangle read by rows: T(n,k) is the number of permutations of {1,...,n} whose longest embedded arithmetic progression has length k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A338993 Triangle read by rows: T(n,k) is the number of k-permutations of {1,...,n} that form a nontrivial arithmetic progression, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples