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.

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

Author

Marcel K. Goh, Sep 07 2021

Keywords

• nonn
• tabl

Comments

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.

Examples

			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
		

Links

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

Crossrefs

Cf. A008683, A338993.

Programs

Mathematica

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 *)

PARI

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

Formula

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.