A111577 Galton triangle T(n, k) = T(n-1, k-1) + (3k-2)*T(n-1, k) read by rows.

1, 1, 1, 1, 5, 1, 1, 21, 12, 1, 1, 85, 105, 22, 1, 1, 341, 820, 325, 35, 1, 1, 1365, 6081, 4070, 780, 51, 1, 1, 5461, 43932, 46781, 14210, 1596, 70, 1, 1, 21845, 312985, 511742, 231511, 39746, 2926, 92, 1, 1, 87381, 2212740, 5430405, 3521385, 867447, 95340, 4950, 117, 1

Offset: 1

Author

Gary W. Adamson, Aug 07 2005

Keywords

• nonn
• easy
• tabl

Comments

In triangles of analogs to Stirling numbers of the second kind, the multipliers of T(n-1,k) in the recurrence are terms in arithmetic sequences: in Pascal's triangle A007318, the multiplier = 1. In triangle A008277, the Stirling numbers of the second kind, the multipliers are in the set (1,2,3...). For this sequence here, the multipliers are from A016777.

Riordan array [exp(x), (exp(3x)-1)/3]. - Paul Barry, Nov 26 2008

From Peter Bala, Jan 27 2015: (Start)

Working with an offset of 0, this is the triangle of connection constants between the polynomial basis sequences {x^n}, n>=0 and {n!*3^n*binomial((x - 1)/3,n)}, n>=0. An example is given below.

Call this array M and let P denote Pascal's triangle A007318, then P * M = A225468, P^2 * M = A075498. Also P^(-1) * M is a shifted version of A075498.

This triangle is the particular case a = 3, b = 0, c = 1 of the triangle of generalized Stirling numbers of the second kind S(a,b,c) defined in the Bala link. (End)

Named after the English scientist Francis Galton (1822-1911). - Amiram Eldar, Jun 13 2021

This is the array of (r, β)-Stirling numbers for r = 1 and β = 3. See Corcino. - Peter Bala, Feb 26 2025

Examples

			T(5,3) = T(4,2) + 7*T(4,3) = 21 + 7*12 = 105.
The triangle starts in row n = 1 as:
  1;
  1,  1;
  1,  5,   1;
  1, 21,  12,  1;
  1, 85, 105, 22, 1;
Connection constants: Row 4: [1, 21, 12, 1] so
x^3 = 1 + 21*(x - 1) + 12*(x - 1)*(x - 4) + (x - 1)*(x - 4)*(x - 7). - _Peter Bala_, Jan 27 2015
From _Peter Bala_, Feb 26 2025: (Start)
The array factorizes as
/1                \     /1               \/1              \/1             \
|1   1            |     |1   1           ||0  1           ||0  1          |
|1   5    1       |  =  |1   4   1       ||0  1   1       ||0  0  1       | ...
|1  21   12   1   |     |1  13   7   1   ||0  1   4  1    ||0  0  1  1    |
|1  85  105  22  1|     |1  44  34  10  1||0  1  13  7  1 ||0  0  1  4  1 |
|...              |     |...             ||...            ||...           |
where, in the infinite product on the right-hand side, the first array is the Riordan array (1/(1 - x), x/(1 - 3*x)). Cf. A193843. (End)
		

Links

• Peter Bala, A 3 parameter family of generalized Stirling numbers, 2015.
• Peter Bala, Factorising (r,b)-Stirling arrays
• Roberto B. Corcino, The (r, β)-Stirling Numbers, The Mindanao Forum, Vol. XIV, No.2, pp. 91-99, 1999.
• 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.
• Ruedi Suter, Two Analogues of a Classical Sequence, Journal of Integer Sequences, Vol. 3 (2000), Article 00.1.8. [_Paul Barry_, Nov 26 2008]

Crossrefs

Cf. A008277, A039755, A075498, A225468.

Cf. A282629, A284861, A225117.

Programs

Maple

A111577 := proc(n,k) option remember; if k = 1 or k = n then 1; else procname(n-1,k-1)+(3*k-2)*procname(n-1,k) ; fi; end:
seq( seq(A111577(n,k),k=1..n), n=1..10) ; # R. J. Mathar, Aug 22 2009

Mathematica

T[, 1] = 1; T[n, n_] = 1;
T[n_, k_] := T[n, k] = T[n-1, k-1] + (3k-2) T[n-1, k];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] (* Jean-François Alcover, Jun 13 2019 *)

Formula

T(n, k) = T(n-1, k-1) + (3k-2)*T(n-1, k).

E.g.f.: exp(x)*exp((y/3)*(exp(3x)-1)). - Paul Barry, Nov 26 2008

Let f(x) = exp(1/3*exp(3*x) + x). Then, with an offset of 0, the row polynomials R(n,x) are given by R(n,exp(3*x)) = 1/f(x)*(d/dx)^n(f(x)). Similar formulas hold for A008277, A039755, A105794, A143494 and A154537. - Peter Bala, Mar 01 2012

T(n, k) = 1/(3^k*k!)*Sum_{j=0..k}((-1)^(k-j)*binomial(k,j)*(3*j+1)^n). - Peter Luschny, May 20 2013

From Peter Bala, Jan 27 2015: (Start)

T(n,k) = Sum_{i = 0..n-1} 3^(i-k+1)*binomial(n-1,i)*Stirling2(i,k-1).

O.g.f. for n-th diagonal: exp(-x/3)*Sum_{k >= 0} (3*k + 1)^(k+n-1)*((x/3*exp(-x))^k)/k!.

O.g.f. column k (with offset 0): 1/( (1 - x)*(1 - 4*x)*...*(1 - (3*k + 1)*x) ). (End)

Extensions

Edited and extended by R. J. Mathar, Aug 22 2009