A186695 A Galton triangle: T(n,k) = (2k-1)*(T(n-1,k) + T(n-1,k-1)): a type B analog of the ordered Bell numbers A019538.
1, 1, 3, 1, 12, 15, 1, 39, 135, 105, 1, 120, 870, 1680, 945, 1, 363, 4950, 17850, 23625, 10395, 1, 1092, 26565, 159600, 373275, 374220, 135135, 1, 3279, 138285, 1303155, 4795875, 8222445, 6621615, 2027025
Offset: 1
Examples
Triangle begins n\k.|..1.....2.....3......4......5......6 ========================================= ..1.|..1 ..2.|..1.....3 ..3.|..1....12....15 ..4.|..1....39...135....105 ..5.|..1...120...870...1680....945 ..6.|..1...363..4950..17850..23625..10395 .. Examples of recurrence relation T(4,3) = 5*(T(3,3)+T(3,2)) = 5*(15+12) = 135; T(6,4) = 7*(T(5,4)+T(5,3)) = 7*(1680+870) = 17850.
Links
- Paweł Hitczenko, A class of polynomial recurrences resulting in (n/log n, n/log^2 n)-asymptotic normality, arXiv:2403.03422 [math.CO], 2024. See p. 8.
- Erich Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Tech Report TR 99-05, 1999.
- Erich Neuwirth, Recursively defined combinatorial functions: Extending Galton's board, Discrete Math. 239 No. 1-3, 33-51 (2001).
Programs
-
Maple
A186695 := proc(n, k) option remember; if k < 1 or k > n then 0; elif k = 1 then 1; else (2*k-1)*(procname(n-1, k) + procname(n-1, k-1)) ; end if; end proc: seq(seq(A186695(n,k),k = 1..n),n = 1..10);
-
Mathematica
T[n_, k_] := (2k-1)! Sum[(-1)^(k-j-1) (2j+1)^(n-1) Binomial[k-1, j], {j, 0, k-1}] / (2^(k-1) (k-1)!)^2; Table[T[n, k], {n, 1, 8}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 02 2019 *)
Formula
T(n+1,k+1) = ((2*k+1)!/(2^k*k!)^2)*Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*(2*j+1)^n.
Recurrence relation: T(n,k) = (2k-1)*(T(n-1,k) + T(n-1,k-1)) with boundary conditions T(n,1) = 1, T(1,k) = 0 for k >= 2.
E.g.f.: F(x,t) = (x/(1+x))*(exp(t)/sqrt((1+x) - x*exp(2*t)) - 1) = Sum_{n>=1} R(n,x)*t^n/n! = x*t + (x + 3*x^2)*t^2/2! + (x + 12*x^2 + 15*x^3)*t^3/3! + ....
Compare with the e.g.f. for A019538, which is (x/(1+x))*(exp(t)/((1+x) - x*exp(t))-1).
The row polynomials R(n,x) are related to the polynomials P(n,x) of the comments section by P(n,x) = 1/x*R(n,x^2).
The generating function F(x,t) satisfies the partial differential equation d/dt(F) = 2*x*(1+x)*d/dx(F) + (x-1)*F + x.
It follows that the polynomials P(n,x) := Sum_{k = 1..n} T(n,k)*x^(2*k-1) satisfy the recurrence P(n+1,x) = x*d/dx((1+x^2)*P(n,x)), with P(1,x) = x. (Cf. the recurrence relation for row polynomials of A185896.)
The recurrence relation for T(n,k) given above now follows.
The row polynomials R(n,x) = Sum_{k = 1..n} T(n,k)*x^k satisfy R(n,-x-1) = (-1)^n*((1+x)/x)*S(n,x), where S(n,x) is the n-th row polynomial of A187075.
In addition, R(n,1/(x-1)) = (1/(x-1)^n)*Q(n-1,x), where Q(n,x) is the n-th row polynomial of A156919.
Row sums are [1,4,28,280,3616...] = 1/2*A124212(n) for n >= 1.
Main diagonal is [1,3,15,105,...] = A001147(k) for k >= 1.
Put S(n) = sum {k = 1..n} (-1)^k*T(n,k)/(k+1). Then for m>=2, S(2*m-1) = S(2*m) = (4^m-1)*Bernoulli(2*m)/m.
From Peter Bala, Aug 30 2016: (Start)
n-th row polynomial R(n,x) = 1/(1 + x)^(3/2) * Sum_{k >= 0} (1/4)^k*(x/(1 + x))^k*binomial(2*k,k)*(2*k + 1)^n.
R(n,x) = (1/(1 + x))*Sum_{k = 0..n} binomial(2*k,k)*A145901(n,k)*(x/4)^k. (End)
Comments