A109822 -id:A109822 - cp's OEIS frontend

A096747 Triangle read by rows: T(n,1) = 1, T(n,k) = T(n-1,k)+(n-1)*T(n-1,k-1) for 1<=k<=n+1.

1, 1, 1, 1, 2, 2, 1, 4, 6, 6, 1, 7, 18, 24, 24, 1, 11, 46, 96, 120, 120, 1, 16, 101, 326, 600, 720, 720, 1, 22, 197, 932, 2556, 4320, 5040, 5040, 1, 29, 351, 2311, 9080, 22212, 35280, 40320, 40320, 1, 37, 583, 5119, 27568, 94852, 212976, 322560, 362880

Offset: 0

Thomas J Engelsma (tom(AT)opertech.com), Dec 05 2004

Note: rows continue as factorials - stopped at second factorial for clarity.
T(n,n) = T(n,n+1) = n!. Sum of row n = n! + s(n,2), where s(n,2) are signless Stirling numbers of the first kind (A081046). T(n,k) = A109822(n,k) for 1<=k<=n (i.e. triangle without the last column is A109822). - Emeric Deutsch, Jul 03 2005
Sum(k=0..n-1, T(n,k))/T(n,n-1) are for n>=1 the harmonic numbers A001008(n)/A002805(n). - Peter Luschny, Sep 15 2014

			Triangle begins:
*0.........................1
*1......................1.....1
*2...................1.....2.....2
*3................1.....4.....6.....6
*4.............1.....7....18....24....24
*5..........1....11....46....96...120...120
*6.......1....16...101...326...600...720...720
*7....1....22...197...932..2556..4320..5040..5040
T(5,3)=46 because 4*7+18=46

Robert Israel, Table of n, a(n) for n = 0..10152 (rows 0..141, flattened)
R. P. Stanley, Ordering events in Minkowski space, arXiv:math/0501256 [math.CO], 2005.

Cf. A081046, A109822.

T:=proc(n,k) if k=1 then 1 elif k=n+1 then n! else T(n-1,k)+(n-1)*T(n-1,k-1) fi end: for n from 0 to 11 do seq(T(n,k),k=1..n+1) od; # yields sequence in triangular form
with(combinat): T:=(n,k)->sum(abs(stirling1(n,n-i)),i=0..k-1): for n from 0 to 11 do seq(T(n,k),k=1..n+1) od; # yields sequence in triangular form; Emeric Deutsch, Jul 03 2005

T[n_, k_] := Sum[Abs[StirlingS1[n, n - i]], {i, 0, k}]; T[0, 0] := 1;
Table[T[n, k], {n, 0, 15}, {k, 0, n}]//Flatten (* G. C. Greubel, Dec 08 2016 *)

@CachedFunction
def T(n,k):
    if n == 0: return 1
    if k < 0: return 0
    return T(n-1,k)+(n-1)*T(n-1,k-1)
for n in range(9): print([T(n,k) for k in (0..n)]) # Peter Luschny, Sep 15 2014

T(n+1, i) = n*T(n, i-1)+T(n, i)
T(n, k) = sum(|stirling1(n, n-i)|, i=0..k-1) for 1<=k<=n. - Emeric Deutsch, Jul 03 2005
E.g.f. as triangle: g(x,y) = Sum_{n>=0} Sum_{1<=k<=n+1} T(n,k) x^n y^k/n! where
g(x,y) = -y^2/((y-1)*(x*y-1)) - (1-x*y)^(-1/y)*(-y+y^2/(y-1)). - Robert Israel, Nov 28 2016

More terms from Emeric Deutsch, Jul 03 2005

A059418 Triangle T(n,k) arising from enumeration of permutations with ordered orbits, read by rows (1<=k<=n).

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 12, 7, 4, 1, 60, 33, 19, 7, 1, 360, 192, 109, 47, 11, 1, 2520, 1320, 737, 344, 102, 16, 1, 20160, 10440, 5742, 2801, 956, 198, 22, 1, 181440, 93240, 50634, 25349, 9493, 2342, 352, 29, 1, 1814400, 927360, 498312, 253426, 101293, 28229

Offset: 1

N. J. A. Sloane, Jan 30 2001

From Peter Bala, Jul 08 2012: (Start)
A non-plane recursive tree is a rooted labeled plane tree (the children of a node are not ordered) with the property that the labels increase along any path from the root to a leaf. T(n,k) counts the total number of vertices of outdegree k among the set of n! non-plane recursive trees on n+1 vertices. An example is given below.
(End)

			1; 1,1; 3,2,1; 12,7,4,1; 60,33,19,7,1; ...
Row 3: [12,7,4,1]. There are 6 non-plane recursive trees on 4 nodes.
The total number of nodes of outdegree 0 = 1+2+2+2+2+3 = 12;
The total number of nodes of outdegree 1 = 3+1+1+1+1 = 7;
The total number of nodes of outdegree 2 = 1+1+1+1 = 4;
The total number of nodes of outdegree 3 = 1;
...................................................................
.0o......0o..........0o..........0o.........0o...........0o........
..|.......|........../.\........./.\......../.\........../|\.......
..|.......|........./...\......./...\....../...\......../.|.\......
.1o......1o.......1o.....o3...1o....o2...2o.....o1...../..|..\.....
..|....../.\.......|...........|..........|..........1o..2o...o3...
..|...../...\......|...........|..........|........................
.2o...2o.....o3...2o..........3o.........3o........................
..|................................................................
..|................................................................
.3o................................................................
....................................... - _Peter Bala_, Jul 08 2012

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 258, #10, F(n,k).

M. Drmota, Recursive Trees.

Diagonals give A001710, A006595. A109822, A130534.

t[n_, k_] := (n - 2)*t[n - 1, k] + t[n - 1, k - 1]; t[n_, n_] := 1; t[n_, 1] = n!/2; Table[t[n, k], {n, 10}, {k, n}] // Flatten (* Robert G. Wilson v, Jul 08 2012 *)

T(n, k) = (n-2)*T(n-1, k) + T(n-1, k-1), T(n, 1)=n!/2, T(n, n)=1.
From Peter Bala, Jul 08 2012: (Start)
E.g.f.: A(x,z) = x/(2-x){1/(1-z) - 1/(1-z)^(x-1)} = x*z + (x+x^2)*z^2/2! + (3*x+2*x^2+x^3)*z^3/3! + ....
A(x+1,z) is an e.g.f. for the row reverse of A109822 and A(x+2,z) generates the triangle of unsigned Stirling numbers of the first kind A130534 but with the first column omitted.
E.g.f. for column k: 1/(2^k*(1-x)) + (x-1)*sum {j = 0..k-1} 1/(j!*2^(k-j))*log^j(1/(1-x)) - see Drmota.
The row polynomial R(n,x) satisfies the recurrence equation R(n,x) = (x+n-2)*R(n-1,x) + (n-1)!*x with R(1,x) = x and also the recurrence R(n,x) = (x+2*n-3)*R(n-1,x) - (n-1)*(x+n-3)*R(n-2,x) with R(1,x) = x and R(2,x) = x+x^2. R(n,x) = {(x-1)*x*(x+1)*...*(x+n-2) - n!}/(x-2).
(End)

More terms from Larry Reeves (larryr(AT)acm.org), Jan 31 2001

cp's OEIS Frontend

A096747 Triangle read by rows: T(n,1) = 1, T(n,k) = T(n-1,k)+(n-1)*T(n-1,k-1) for 1<=k<=n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

Extensions