login
Triangle T(n,k) read by rows; related to number of preorders.
6

%I #23 Nov 07 2017 18:27:28

%S 1,1,2,1,5,5,1,10,24,16,1,18,79,122,61,1,31,223,602,680,272,1,52,579,

%T 2439,4682,4155,1385,1,86,1432,8856,25740,38072,27776,7936,1,141,3434,

%U 30030,124146,272416,326570,202084,50521,1,230,8071,97332

%N Triangle T(n,k) read by rows; related to number of preorders.

%H Sean A. Irvine, <a href="/A079502/b079502.txt">Table of n, a(n) for n = 0..999</a>

%H G. Kreweras, <a href="http://www.numdam.org/item?id=MSH_1976__53__5_0">Les préordres totaux compatibles avec un ordre partiel</a>, Math. Sci. Humaines No. 53 (1976), 5-30. (The numbers u_r^n on page 20.)

%H G. Kreweras, <a href="/A019538/a019538.pdf">Les préordres totaux compatibles avec un ordre partiel</a>, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)

%F From _Sean A. Irvine_, Mar 12 2017: (Start)

%F A079502 can be constructed one row at a time from the corresponding row of A050447. For row n, construct up to the n-th difference sequence of row n in A050447, retaining the first element of each difference sequence. Row n of A079502 is then constructed backwards (i.e., starting with A079502(n,n) and computing down to A079502(n,2)) from the first element of the n-th difference sequence, then successively subtracting the first element of the previous difference sequences. More precisely, let R_n denote the n-th row of A050447 augmented with R_n(1) = 0, and R_n^(d) the d-th difference of that row, such that R_n^(0)(m) = R_n(m) and R_n^(k)(m) = R_n^(k-1)(m+1) - R_n^(k-1)(m). Row n of A079502 is then T(n,n) = R_n^(n)(0) and for m < n, T(n,m) = R_n^(n)(0) - T(n,m+1).

%F For example, starting with row 4 of A050447: [0], 1, 8, 31, 85, 190, 371, ..., we construct up to order 4 difference sequences: first-differences 1, 7, 23, 54, 105, 181, ...; second-differences 6, 16, 31, 51, 76, ...; third-differences 10, 15, 20, 25, ...; fourth-differences 5, 5, 5, ... (constant). Only the first elements of these difference sequences are needed. Thus T(4,4) = 5, T(4,3) = 10 - 5 = 5, T(4,2) = 6 - (10 - 5) = 1, T(4,1) = 1 - (6 - (10 - 5)) = 0. (End)

%e Triangle T(n,k) begins:

%e 1;

%e 1, 2;

%e 1, 5, 5;

%e 1, 10, 24, 16;

%e 1, 18, 79, 122, 61;

%e 1, 31, 223, 602, 680, 272;

%e 1, 52, 579, 2439, 4682, 4155, 1385;

%e 1, 86, 1432, 8856, 25740, 38072, 27776, 7936;

%t t[n_, m_] := t[n, m] = If[m == 0, 1, t[n, m - 1] + Sum[t[2 k, m - 1] t[n - 1 - 2 k, m], {k, 0, (n - 1)/2}]]; Map[Function[s, Rest@ Reverse@ Map[Abs@ Fold[#2 - #1 &, Reverse@ Take[s, #]] &, Range@ Length@ s]]@ Reverse@ Map[First, NestList[Differences@ # &, {First@ #}~Join~Differences@ #, Length@ # - 2]] &, Table[t[n, k], {n, 2, 11}, {k, 0, n}]] (* _Michael De Vlieger_, Mar 13 2017, after _Jean-François Alcover_ at A050447 *)

%Y Diagonals give A000111, A006326, A006327, A006328. Cf. A050447.

%K nonn,tabl,easy

%O 0,3

%A _N. J. A. Sloane_, Jan 21 2003

%E More terms from _Sean A. Irvine_, Mar 12 2017