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

1, 1, 2, 1, 5, 5, 1, 10, 24, 16, 1, 18, 79, 122, 61, 1, 31, 223, 602, 680, 272, 1, 52, 579, 2439, 4682, 4155, 1385, 1, 86, 1432, 8856, 25740, 38072, 27776, 7936, 1, 141, 3434, 30030, 124146, 272416, 326570, 202084, 50521, 1, 230, 8071, 97332

Offset

0,3

Links

Sean A. Irvine, Table of n, a(n) for n = 0..999

G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (The numbers u_r^n on page 20.)

G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)

Formula

From Sean A. Irvine, Mar 12 2017: (Start)

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

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)

Example

Triangle T(n,k) begins:
1;
1,  2;
1,  5,    5;
1, 10,   24,  16;
1, 18,   79,  122,    61;
1, 31,  223,  602,   680,   272;
1, 52,  579, 2439,  4682,  4155,  1385;
1, 86, 1432, 8856, 25740, 38072, 27776, 7936;

Mathematica

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

Crossrefs

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

Sequence in context: A033282 A126350 A204111 * A209164 A209148 A126124

Adjacent sequences: A079499 A079500 A079501 * A079503 A079504 A079505

Keyword

nonn,tabl,easy

Author

N. J. A. Sloane, Jan 21 2003

Extensions

More terms from Sean A. Irvine, Mar 12 2017

Status

approved