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
Examples
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;
Links
- Sean A. Irvine, Table of n, a(n) for n = 0..999
- Germain 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.)
- Germain Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30. (Annotated scanned copy)
- Igor Pak, Boris Shapiro, Ilya Smirnov, and Ken-ichi Yoshida, Hilbert-Kunz multiplicity of quadrics via the Ehrhart theory, Stockholm Univ. (Sweden, 2025). See pp. 5, 10.
Programs
-
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 *)
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)
Extensions
More terms from Sean A. Irvine, Mar 12 2017