A144402 -id:A144402 - cp's OEIS frontend

A144385 Triangle read by rows: T(n,k) is the number of partitions of [1, 2, ..., k] into exactly n blocks, each of size 1, 2 or 3 (n >= 0, 0 <= k <= 3n).

1, 0, 1, 1, 1, 0, 0, 1, 3, 7, 10, 10, 0, 0, 0, 1, 6, 25, 75, 175, 280, 280, 0, 0, 0, 0, 1, 10, 65, 315, 1225, 3780, 9100, 15400, 15400, 0, 0, 0, 0, 0, 1, 15, 140, 980, 5565, 26145, 102025, 323400, 800800, 1401400, 1401400, 0, 0, 0, 0, 0, 0, 1, 21, 266, 2520, 19425, 125895, 695695, 3273270, 12962950, 42042000, 106506400, 190590400, 190590400

Offset: 0

David Applegate and N. J. A. Sloane, Dec 07 2008, Dec 17 2008

Row n has 3n+1 entries.

			Triangle begins:
[1]
[0, 1, 1, 1]
[0, 0, 1, 3, 7, 10, 10]
[0, 0, 0, 1, 6, 25, 75, 175, 280, 280]
[0, 0, 0, 0, 1, 10, 65, 315, 1225, 3780, 9100, 15400, 15400]
[0, 0, 0, 0, 0, 1, 15, 140, 980, 5565, 26145, 102025, 323400, 800800, 1401400, 1401400]

Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, Analysis of the Gift Exchange Problem, arXiv:1701.08394, 2017.
David Applegate and N. J. A. Sloane, The Gift Exchange Problem (arXiv:0907.0513, 2009)

See A144399, A144402, A144417, A111246 for other versions of this triangle.
Column sums give A001680, row sums give A144416. Taking last nonzero entry in each row gives A025035.
Diagonals include A000217, A001296, A027778, A144516; also A025035.
A generalization of the triangle in A144331 (and in several other entries).
Cf. A144643.

T := proc(n, k)
option remember;
if n = k then 1;
elif k < n then 0;
elif n < 1 then 0;
else T(n - 1, k - 1) + (k - 1)*T(n - 1, k - 2) + 1/2*(k - 1)*(k - 2)*T(n - 1, k - 3);
end if;
end proc;
for n from 0 to 12 do lprint([seq(T(n,k),k=0..3*n)]); od:

t[n_, n_] = 1; t[n_ /; n >= 0, k_] /; 0 <= k <= 3*n := t[n, k] = t[n-1, k-1] + (k-1)*t[n-1, k-2] + (1/2)*(k-1)*(k-2)*t[n-1, k-3]; t[, ] = 0; Table[t[n, k], {n, 0, 12}, {k, 0, 3*n}] // Flatten (* Jean-François Alcover, Jan 14 2014 *)

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

E.g.f.: Sum_{ n >= 0, k >= 0 } T(n, k) y^n x^k / k! = exp( y*(x+x^2/2+x^3/6) ). That is, the coefficient of y^n is the e.g.f. for row n. E.g. the e.g.f. for row 2 is (1/2)*(x+x^2/2+x^3/6)^2 = 1*x^2/2! + 3*x^3/3! + 7*x^4/4! + 10*x^5/5! + 10*x^6/6!.

A144633 Triangle of 3-restricted Stirling numbers of the first kind (T(n,k), 0 <= k <= n), read by rows.

Original entry on oeis.org

1, 0, 1, 0, -1, 1, 0, 2, -3, 1, 0, -5, 11, -6, 1, 0, 10, -45, 35, -10, 1, 0, 35, 175, -210, 85, -15, 1, 0, -910, -315, 1225, -700, 175, -21, 1, 0, 11935, -6265, -5670, 5565, -1890, 322, -28, 1, 0, -134750, 139755, -5005, -39270, 19425, -4410, 546, -36, 1

Offset: 0

N. J. A. Sloane, Jan 21 2009

Definition: take the triangle in A144385, write it as an (infinite) upper triangular square matrix, invert it and transpose it.

The Bell transform of A144636(n+1). Also the inverse Bell transform of the sequence "g(n) = 1 if n<3 else 0". For the definition of the Bell transform see A264428. - Peter Luschny, Jan 19 2016

			Triangle begins:
1;
0,    1;
0,   -1,    1;
0,    2,   -3,    1;
0,   -5,   11,   -6,    1;
0,   10,  -45,   35,  -10,   1;
0,   35,  175, -210,   85, -15,   1;
0, -910, -315, 1225, -700, 175, -21,  1;

J. Y. Choi and J. D. H. Smith, On the combinatorics of multi-restricted numbers, Ars. Com., 75(2005), pp. 44-63.

Alois P. Heinz, Rows n = 0..140, flattened
J. Y. Choi and J. D. H. Smith, The Tri-restricted Numbers and Powers of Permutation Representations, J. Comb. Math. Comb. Comp. 42 (2002), 113-125.
J. Y. Choi and J. D. H. Smith, On the Unimodality and Combinatorics of the Bessel Numbers, Discrete Math., 264 (2003), 45-53.
J. Y. Choi et al., Reciprocity for multirestricted Stirling numbers, J. Combin. Theory 113 A (2006), 1050-1060.

For another version of this triangle see A144634.
Columns give A144636-A144639.
Cf. A144402.

A:= proc(n,k) option remember; if n=k then 1 elif k A(i-1, j-1))^(-1) end:
T:= (n,k)-> M(n+1)[k+1, n+1]:
seq(seq(T(n,k), k=0..n), n=0..12); # Alois P. Heinz, Oct 23 2009

max = 10; t[n_, n_] = 1; t[n_ /; n >= 0, k_] /; (0 <= k <= 3*n) := t[n, k] = t[n-1, k-1] + (k-1)*t[n-1, k-2] + (1/2)*(k-1)*(k-2)*t[n-1, k-3]; t[, ] = 0; A144633 = Table[t[n, k], {n, 0, max}, {k, 0, max}] // Inverse // Transpose; Table[A144633[[n, k]], {n, 1, max}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jan 14 2014 *)

# uses[bell_matrix from A264428]
bell_matrix(lambda n: A144636(n+1), 10) # Peter Luschny, Jan 18 2016

Corrected and extended by Alois P. Heinz, Oct 23 2009

A111246 Triangle read by rows: a(n,k) = number of partitions of an n-set into exactly k nonempty subsets, each of size <= 3.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 0, 7, 6, 1, 0, 10, 25, 10, 1, 0, 10, 75, 65, 15, 1, 0, 0, 175, 315, 140, 21, 1, 0, 0, 280, 1225, 980, 266, 28, 1, 0, 0, 280, 3780, 5565, 2520, 462, 36, 1, 0, 0, 0, 9100, 26145, 19425, 5670, 750, 45, 1, 0, 0, 0, 15400, 102025, 125895, 56595, 11550, 1155

Offset: 1

Ji Young Choi, Oct 31 2005

a(n,k) = 0 if k > n; a(n,k) = 0 if n > 0 and k < 0; a(n,k) can be extended to negative n and k, just as the Stirling numbers or Pascal's triangle can be extended. The present triangle is called the tri-restricted Stirling numbers of the second kind.

Also the Bell transform of the sequence "a(n) = 1 if n<3 else 0". For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016

			a(1,1)=1;
a(2,1)=1; a(2,2)=1;
a(3,1)=1; a(3,2)=3; a(3,3)=1;
a(4,1)=0; a(4,2)=7; a(4,3)=6; a(4,4)=1;
a(5,1)=0; a(5,2)=10; a(5,3)=25; a(5,4)=10; a(5,5)=1;
a(6,1)=0; a(6,2)=10; a(6,3)=75; a(6,4)=65; a(6,5)=15; a(6,6)=1; ...

J. Y. Choi and J. D. H. Smith, On the combinatorics of multi-restricted numbers, Ars. Com., 75(2005), pp. 44-63.

J. Y. Choi and J. D. H. Smith, The Tri-restricted Numbers and Powers of Permutation Representations, J. Comb. Math. Comb. Comp. 42 (2002), 113-125.
J. Y. Choi and J. D. H. Smith, On the Unimodality and Combinatorics of the Bessel Numbers, Discrete Math., 264 (2003), 45-53.
J. Y. Choi et al., Reciprocity for multirestricted Stirling numbers, J. Combin. Theory 113 A (2006), 1050-1060.

A144385 and A144402 are other versions of this same triangle.

Cf. A001680, A008277 (Stirling numbers).

# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0,...) as column 0.
BellMatrix(n -> `if`(n<3,1,0), 10); # Peter Luschny, Jan 27 2016

BellMatrix[f_Function, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 12;
M = BellMatrix[If[# < 3, 1, 0]&, rows];
Table[M[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 24 2018, after Peter Luschny *)

row(n) = {x='x+O('x^(n+1)); polcoeff(serlaplace(exp(y*(x+x^2/2+x^3/6))), n, 'x); }
tabl(nn) = for(n=1, nn, print(Vecrev(row(n)/y))) \\ Jinyuan Wang, Dec 21 2019

a(n, k) = a(n-1, k-1) + k*a(n-1, k) - binomial(n-1, 3)*a(n-4, k-1).
G.f. = Sum_{k_1+k_2+k_3=k, k_1+ 2k_2+3k_3=n} frac{n!}{(1!)^{k_1}(2!)^{k_2}(3!)^{k_3}k_1!k_2!k_3!}.
E.g.f.: exp(y*(x+x^2/2+x^3/6)). - Vladeta Jovovic, Nov 01 2005

More terms from Vladeta Jovovic, Nov 01 2005

Recurrence, offset and example corrected by David Applegate, Jan 16 2009

cp's OEIS Frontend

A144385 Triangle read by rows: T(n,k) is the number of partitions of [1, 2, ..., k] into exactly n blocks, each of size 1, 2 or 3 (n >= 0, 0 <= k <= 3n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A144633 Triangle of 3-restricted Stirling numbers of the first kind (T(n,k), 0 <= k <= n), read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Extensions

A111246 Triangle read by rows: a(n,k) = number of partitions of an n-set into exactly k nonempty subsets, each of size <= 3.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions