login
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.
0

%I #37 Sep 13 2021 11:38:12

%S 1,1,2,1,6,6,1,12,24,12,1,21,68,72,24,1,32,144,244,180,48,1,47,283,

%T 666,764,432,96,1,64,486,1510,2436,2164,1008,192,1,85,799,3117,6534,

%U 8028,5816,2304,384,1,109,1232,5860,15368,24524,24516,15040,5184,768

%N 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.

%C 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.

%H M. K. Goh, J. Hamdan, and J. Saks, <a href="https://arxiv.org/abs/2106.05949">The lattice of arithmetic progressions</a>, arXiv:2106.05949 [math.CO], 2021. See Table 2 p. 7.

%F 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.

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

%e Triangle begins:

%e n/k 1 2 3 4 5 6 7 8 9 10 11 12

%e 1 1

%e 2 1 2

%e 3 1 6 6

%e 4 1 12 24 12

%e 5 1 21 68 72 24

%e 6 1 32 144 244 180 48

%e 7 1 47 283 666 764 432 96

%e 8 1 64 486 1510 2436 2164 1008 192

%e 9 1 85 799 3117 6534 8028 5816 2304 384

%e 10 1 109 1232 5860 15368 24524 24516 15040 5184 768

%e 11 1 137 1838 10418 33049 65402 84284 70992 37760 11520 1536

%e 12 1 167 2611 17420 65706 157010 250332 270996 197280 92608 25344 3072

%t t[n_, k_] := If[k == 1, n, Sum[2(n-(k-1) r), {r, 1, Quotient[n-1, k-1]}]];

%t f[n_, k_] := If[k == 1, n, t[n, k]/2];

%t T[n_, k_] := T[n, k] = If[k == 1, 1, Sum[f[n, i] T[i, k-1], {i, 1, n-1}]];

%t Table[T[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Sep 13 2021, from PARI code *)

%o (PARI) t(n, k) = if (k==1, n, sum(r=1, (n-1)\(k-1), 2*(n-(k-1)*r))); \\ A338993

%o f(n, k) = if (k==1, n, t(n,k)/2);

%o T(n, k) = if (k==1, 1, sum(i=1, n-1, f(n, i)*T(i, k-1))); \\ _Michel Marcus_, Sep 11 2021

%Y Cf. A008683, A338993.

%K nonn,tabl

%O 1,3

%A _Marcel K. Goh_, Sep 07 2021