cp's OEIS Frontend

A097877 Triangle read by rows: T(n,k) is the number of Dyck n-paths with k large components, 0 <= k <= n/2.

%I A097877 #15 Apr 21 2023 16:19:08
%S A097877 1,1,1,1,1,4,1,12,1,1,34,7,1,98,32,1,1,294,124,10,1,919,448,61,1,1,
%T A097877 2974,1576,298,13,1,9891,5510,1294,99,1,1,33604,19322,5260,583,16,1,
%U A097877 116103,68206,20595,2960,146,1,1,406614,242602,78954,13704,1006,19,1,1440025
%N A097877 Triangle read by rows: T(n,k) is the number of Dyck n-paths with k large components, 0 <= k <= n/2.
%C A097877 A prime Dyck path is one with exactly one return to ground level. Every nonempty Dyck path decomposes uniquely as a concatenation of prime Dyck paths, called its components. For example, UUDDUD has 2 components: UUDD and UD, of semilength 2 and 1 respectively. A large component is one of semilength >= 2.
%C A097877 Conjecture: This is the statistic "indegree" of elements in Pallo's comb posets. For the statistic "outdegree", see A009766. - _F. Chapoton_, Apr 18 2023
%H A097877 Alois P. Heinz, <a href="/A097877/b097877.txt">Rows n = 0..200, flattened</a>
%H A097877 J. M. Pallo, <a href="https://doi.org/10.1016/S0020-0190(03)00283-7">Right-arm rotation distance between binary trees</a>, Inform. Process. Lett., 87(4):173-177, 2003.
%F A097877 G.f.: 2/(1 + t*(1 - 4*z)^(1/2) + (1 - 2*z)(1-t)) = Sum_{n>=0, k>=0} T(n, k) z^n t^k satisfies (1-z)*G = 1 + z*t*(CatalanGF[z]-1)*G. The gf for Dyck paths (A000108) with z marking semilength is CatalanGF[z]:=(1 - sqrt[1 - 4*z])/(2*z). Hence the gf for prime Dyck paths is z*CatalanGF[z] and the gf for non-UD prime Dyck paths is S(z):= z*CatalanGF[z]-z. For fixed k, the gf for (T(n, k))_{n>=0} is S(z)^k/(1-z)^(k+1). This is clear because 1/(1-z) is the gf for all-UD Dyck paths (including the empty one) and a Dyck path with k large components is a product (uniquely) of an all-UD, a non-UD prime, an all-UD, a non-UD prime, ... with k non-UD primes and k+1 all-UDs.
%e A097877 T(3,1) = 4 because each of the 5 Dyck paths of semilength 3 has one large component except for UDUDUD, which has none.
%e A097877 Table begins:
%e A097877   \ k 0, 1, 2, ...
%e A097877   n\ ____________________
%e A097877   0 | 1;
%e A097877   1 | 1;
%e A097877   2 | 1,   1;
%e A097877   3 | 1,   4;
%e A097877   4 | 1,  12,   1;
%e A097877   5 | 1,  34,   7;
%e A097877   6 | 1,  98,  32,  1;
%e A097877   7 | 1, 294, 124, 10;
%e A097877   8 | 1, 919, 448, 61, 1;
%e A097877   ...
%Y A097877 The Fine distribution (A065600) counts Dyck paths by number of small components (= number of low peaks).
%Y A097877 Cf. A000108, A009766.
%K A097877 nonn,tabf
%O A097877 0,6
%A A097877 _David Callan_, Sep 21 2004