cp's OEIS Frontend

A100754 Triangle read by rows: T(n, k) = number of hill-free Dyck paths (i.e., no peaks at height 1) of semilength n and having k peaks.

%I A100754 #66 Jul 09 2025 04:24:18
%S A100754 1,1,1,1,4,1,1,8,8,1,1,13,29,13,1,1,19,73,73,19,1,1,26,151,266,151,26,
%T A100754 1,1,34,276,749,749,276,34,1,1,43,463,1781,2762,1781,463,43,1,1,53,
%U A100754 729,3758,8321,8321,3758,729,53,1,1,64,1093,7253,21659,31004,21659,7253,1093,64,1
%N A100754 Triangle read by rows: T(n, k) = number of hill-free Dyck paths (i.e., no peaks at height 1) of semilength n and having k peaks.
%C A100754 Row n has n - 1 terms. Row sums yield the Fine numbers (A000957).
%C A100754 Related to the number of certain sets of non-crossing partitions for the root system A_n (p. 11, Athanasiadis and Savvidou). - _Tom Copeland_, Oct 19 2014
%C A100754 T(n,k) is the number of permutations pi of [n-1] with k - 1 descents such that s(pi) avoids the patterns 132, 231, and 312, where s is West's stack-sorting map. - _Colin Defant_, Sep 16 2018
%C A100754 The absolute values of the polynomials at -1 and j (cube root of 1) seem to be given by A126120 and A005043. - _F. Chapoton_, Nov 16 2021
%C A100754 _Don Knuth_ observes that this sequence also arrises from the enumeration of restricted max-and-min-closed relations, only there it appears as an array read by antidiagonals: see the Knuth "Notes" link and A372068. Knuth also gives a formula expressing the array A372368 in terms of this array. He also reports that there is strong experimental evidence that the n-th term of row m in this array is a polynomial of degree 2*m-2 in n. - _N. J. A. Sloane_, May 12 2024
%H A100754 Alois P. Heinz, <a href="/A100754/b100754.txt">Rows n = 2..142, flattened</a>
%H A100754 C. Athanasiadis and C. Savvidou, <a href="http://arxiv.org/abs/1204.0362">The local h-vector of the cluster subdivision of a simplex</a>, arXiv preprint arXiv:1204.0362 [math.CO], 2012.
%H A100754 Paul Barry, <a href="https://arxiv.org/abs/1803.06408">Three Études on a sequence transformation pipeline</a>, arXiv:1803.06408 [math.CO], 2018.
%H A100754 Colin Defant, <a href="https://arxiv.org/abs/1809.03123">Stack-sorting preimages of permutation classes</a>, arXiv:1809.03123 [math.CO], 2018.
%H A100754 E. Deutsch and L. Shapiro, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00121-2">A survey of the Fine numbers</a>, Discrete Math., 241 (2001), 241-265.
%H A100754 D. E. Knuth, <a href="/A372066/a372066.txt">Notes on four arrays of numbers arising from the enumeration of CRC constraints and min-and-max-closed constraints</a>, May 06 2024
%F A100754 T(n, k) = Sum_{j=0..min(k, n-k)} (j/(n-j)) * C(n-j, k-j) * C(n-j, k), n >= 2.
%F A100754 G.f.: t*z*r/(1 - t*z*r), where r = r(t, z) is the Narayana function defined by r = z*(1 + r)*(1 + t*r).
%F A100754 From _Tom Copeland_, Oct 19 2014: (Start)
%F A100754 With offset 0 for A108263 and offset 1 for A132081, row polynomials of this entry P(n, x) = Sum_{i} A108263(n, i)*x^i*(1 + x)^(n - 2*i) = Sum_{i} A132081(n - 2, i)*x^i*(1 + x)^(n - 2*i).
%F A100754 E.g., P(4, x) = 1*x*(1 + x)^(4 - 2*1) + 2*x^2*(1 + x)^(4 - 2*2) = x + 4*x^2 + x^3.
%F A100754 Equivalently, let Q(n, x) be the row polynomials of A108263. Then P(n, x) = (1 + x)^n * Q(n, x/(1 + x)^2).
%F A100754 E.g., P(4, x) = (1 + x)^4 * (x/(1 + x)^2 + 2 * (x/(1 + x)^2)^2).
%F A100754 See Athanasiadis and Savvidou (p. 7). (End)
%e A100754 T(4, 2) = 4 because we have UU*DDUU*DD, UU*DUU*DDD, UUU*DDU*DD and UUU*DU*DDD, where U = (1, 1), D = (1,-1) and * indicates the peaks.
%e A100754 Triangle starts:
%e A100754    1;
%e A100754    1,  1;
%e A100754    1,  4,   1;
%e A100754    1,  8,   8,    1;
%e A100754    1, 13,  29,   13,    1;
%e A100754    1, 19,  73,   73,   19,    1;
%e A100754    1, 26, 151,  266,  151,   26,    1;
%e A100754    1, 34, 276,  749,  749,  276,   34,   1;
%e A100754    1, 43, 463, 1781, 2762, 1781,  463,  43,  1;
%e A100754    1, 53, 729, 3758, 8321, 8321, 3758, 729, 53, 1;
%e A100754    ...
%e A100754 As an array (for which the rows of the preceding triangle are the antidiagonals):
%e A100754    1,  1,    1,     1,      1,      1,       1,        1,        1, ...
%e A100754    1,  4,    8,    13,     19,     26,      34,       43,       53, ...
%e A100754    1,  8,   29,    73,    151,    276,     463,      729,     1093, ...
%e A100754    1, 13,   73,   266,    749,   1781,    3758,     7253,    13061, ...
%e A100754    1, 19,  151,   749,   2762,   8321,   21659,    50471,   107833, ...
%e A100754    1, 26,  276,  1781,   8321,  31004,   97754,   271125,   679355, ...
%e A100754    1, 34,  463,  3758,  21659,  97754,  367285,  1196665,  3478915, ...
%e A100754    1, 43,  729,  7253,  50471, 271125, 1196665,  4526470, 15118415, ...
%e A100754    1, 53, 1093, 13061, 107833, 679355, 3478915, 15118415, 57500480, ...
%e A100754    ...
%p A100754 T := (n, k) -> add((j/(n-j))*binomial(n-j, k-j)*binomial(n-j,k), j=0..min(k,n-k)): for n from 2 to 13 do seq(T(n, k), k = 1..n-1) od; # yields the sequence in triangular form
%t A100754 T[n_, k_] := Sum[(j/(n-j))*Binomial[n-j, k-j]*Binomial[n-j, k], {j, 0, Min[k, n-k]}]; Table[T[n, k], {n, 2, 13}, {k, 1, n-1}] // Flatten (* _Jean-François Alcover_, Feb 19 2017, translated from Maple *)
%Y A100754 Cf. A000957, A108263, A132081.
%Y A100754 See also A099594, A272644, A372066, A372067, A372068.
%K A100754 nonn,tabl
%O A100754 2,5
%A A100754 _Emeric Deutsch_, Jan 14 2005