|
%I #86 Sep 08 2022 08:45:15
%S 1,1,1,3,2,1,10,6,3,1,35,20,10,4,1,126,70,35,15,5,1,462,252,126,56,21,
%T 6,1,1716,924,462,210,84,28,7,1,6435,3432,1716,792,330,120,36,8,1,
%U 24310,12870,6435,3003,1287,495,165,45,9,1,92378,48620,24310,11440,5005,2002
%N Triangle T(n,k) = binomial(2*n-k-1, n-k) read by rows.
%C Sometimes called a Catalan triangle, although there are many other triangles that carry that name - see A009766, A008315, A028364, A033184, A053121, A059365, A062103.
%C Number of nodes of outdegree k in all ordered trees with n edges. Equivalently, number of ascents of length k in all Dyck paths of semilength n. Example: T(3,2) = 3 because the Dyck paths of semilength 3 are UDUDUD, UD(UU)DD, (UU)DDUD, (UU)DUDD and UUUDDD, where U = (1,1), D = (1,-1), the ascents of length 2 being shown between parentheses. - _Emeric Deutsch_, Nov 19 2006
%C Riordan array (f(x), x*g(x)) where f(x) is the g.f. of A088218 and g(x) is the g.f. of A000108. - _Philippe Deléham_, Jan 23 2010
%C T(n,k) is the number of nonnegative paths of upsteps U = (1,1) and downsteps D = (1,-1) of length 2*n with k returns to ground level, the horizontal line through the initial vertex. Example: T(2,1) = 2 counts UDUU, UUDD. Also, T(n,k) = number of these paths whose last descent has length k, that is, k downsteps follow the last upstep. Example: T(2,1) = 2 counts UUUD, UDUD. - _David Callan_, Nov 21 2011
%C Belongs to the hitting-time subgroup of the Riordan group. Multiplying this triangle by the square Pascal matrix gives A092392 read as a square array. See the example below. - _Peter Bala_, Nov 03 2015
%H Reinhard Zumkeller, <a href="/A100100/b100100.txt">Rows n = 0..125 of triangle, flattened</a>
%H Peter Bala, <a href="/A100100/a100100_1.pdf">Notes on logarithmic differentiation, the binomial transform and series reversion</a>
%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.
%H Gi-Sang Cheon, Hana Kim, and Louis W. Shapiro, <a href="https://doi.org/10.1016/j.laa.2010.04.044">An algebraic structure for Faber polynomials</a>, Lin. Alg. Applic. 433 (2010) 1170-1179.
%H Tian-Xiao He and Renzo Sprugnoli, <a href="http://dx.doi.org/10.1016/j.disc.2008.11.021">Sequence characterization of Riordan arrays</a>, Discrete Math. 309 (2009), no. 12, 3962-3974.
%F From _Peter Bala_, Sep 06 2015: (Start)
%F Matrix product A094527 * P^(-1) = A113955 * P^(-2), where P denotes Pascal's triangle A007318.
%F Essentially, the logarithmic derivative of A033184. (End)
%F Let column(k) = [T(n, k), n >= k], then the generating function for column(k) is (2/(sqrt(1-4*x)+1))^(k-1)/sqrt(1-4*x). - _Peter Luschny_, Mar 19 2021
%F O.g.f. row polynomials R(n, x) := Sum_{k=0..n} T(n, k)*x^k, i.e. o.g.f. of the triangle, G(z,x) = 1/((2 - c(z))*(1 - x*z*c(z))), with c the o.g.f. of A000108 (Catalan). See the Riordan coomment by _Philippe Deléham_ above. - _Wolfdieter Lang_, Apr 06 2021
%e From _Paul Barry_, Mar 15 2010: (Start)
%e Triangle begins in row n=0 with columns 0<=k<=n as:
%e 1;
%e 1, 1;
%e 3, 2, 1;
%e 10, 6, 3, 1;
%e 35, 20, 10, 4, 1;
%e 126, 70, 35, 15, 5, 1;
%e 462, 252, 126, 56, 21, 6, 1;
%e Production matrix begins
%e 1, 1;
%e 2, 1, 1;
%e 3, 1, 1, 1;
%e 4, 1, 1, 1, 1;
%e 5, 1, 1, 1, 1, 1;
%e 6, 1, 1, 1, 1, 1, 1;
%e 7, 1, 1, 1, 1, 1, 1, 1;
%e (End)
%e A092392 as a square array = A100100 * square Pascal matrix:
%e /1 1 1 1 ...\ / 1 \/1 1 1 1 ...\
%e |2 3 4 5 ...| | 1 1 ||1 2 3 4 ...|
%e |6 10 15 21 ...| = | 3 2 1 ||1 3 6 10 ...|
%e |20 35 56 84 ...| |10 6 3 1 ||1 4 10 20 ...|
%e |70 ... | |35 ... ||1 ... |
%e - _Peter Bala_, Nov 03 2015
%p A100100 := proc(n,k)
%p binomial(2*n-k-1,n-1) ;
%p end proc:
%p seq(seq(A100100(n,k),k=0..n),n=0..10) ; # _R. J. Mathar_, Feb 06 2015
%t Flatten[Table[Binomial[2 n - k - 1, n - k], {n, 0, 11}, {k, 0, n}]] (* _Vincenzo Librandi_, Nov 21 2018 *)
%o (PARI) T(n,k)=binomial(2*n-k-1,n-k) \\ _Charles R Greathouse IV_, Jan 16 2012
%o (Haskell)
%o a100100 n k = a100100_tabl !! n !! n
%o a100100_row n = a100100_tabl !! n
%o a100100_tabl = [1] : f a092392_tabl where
%o f (us : wss'@(vs : wss)) = (vs !! 1 : us) : f wss'
%o -- _Reinhard Zumkeller_, Jan 15 2014
%o (Magma) /* As triangle */ [[Binomial(2*n - k - 1, n - k): k in [0..n]]: n in [0.. 15]]; // _Vincenzo Librandi_, Nov 21 2018
%Y Row sums are A000984. Equivalent to A092392, to which A088218 has been added as a first column. Columns include A088218, A000984, A001700, A001791, A002054, A002694. Diagonal sums are A100217. Matrix inverse is A100218.
%Y Cf. A059481 (mirrored). Cf. A033184, A094527, A113955.
%K easy,nonn,tabl
%O 0,4
%A _Paul Barry_, Nov 08 2004
|
