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,3

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.

Links

Table of n, a(n) for n=1..55.

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

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.

Example

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

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

Prog

(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

Crossrefs

Cf. A008683, A338993.

Sequence in context: A229565 A259477 A208919 * A259569 A046651 A063007

Adjacent sequences: A347577 A347578 A347579 * A347581 A347582 A347583

Keyword

nonn,tabl

Author

Marcel K. Goh, Sep 07 2021

Status

approved