|
|
A059438
|
|
Triangle T(n,k) (1 <= k <= n) read by rows: T(n,k) is the number of permutations of [1..n] with k components.
|
|
18
|
|
|
1, 1, 1, 3, 2, 1, 13, 7, 3, 1, 71, 32, 12, 4, 1, 461, 177, 58, 18, 5, 1, 3447, 1142, 327, 92, 25, 6, 1, 29093, 8411, 2109, 531, 135, 33, 7, 1, 273343, 69692, 15366, 3440, 800, 188, 42, 8, 1, 2829325, 642581, 125316, 24892, 5226, 1146, 252, 52, 9, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
LINKS
|
|
|
FORMULA
|
Let f(x) = Sum_{n >= 0} n!*x^n, g(x) = 1 - 1/f(x). Then g(x) is g.f. for first diagonal A003319 and Sum_{n >= k} T(n, k)*x^n = g(x)^k.
Triangle T(n, k), n > 0 and k > 0, read by rows; given by [0, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, ...] DELTA A000007 where DELTA is Deléham's operator defined in A084938.
If g(x) = x + x^2 + 3*x^3 + 13*x^4 + ... is the generating function for the number of permutations with no global descents, then 1/(1-g(x)) is the generating function for n!. Setting t=1 in f(x, t) implies Sum_{k=1..n} T(n,k) = n!. Let g(x) be the o.g.f. for A003319. Then the o.g.f. for this table is given by f(x, t) = 1/(1 - t*g(x)) - 1 (i.e., the coefficient of x^n*t^k in f(x,t) is T(n,k)). - Mike Zabrocki, Jul 29 2004
|
|
EXAMPLE
|
Triangle begins:
[1] [ 1]
[2] [ 1, 1]
[3] [ 3, 2, 1]
[4] [ 13, 7, 3, 1]
[5] [ 71, 32, 12, 4, 1]
[6] [ 461, 177, 58, 18, 5, 1]
[7] [ 3447, 1142, 327, 92, 25, 6, 1]
[8] [ 29093, 8411, 2109, 531, 135, 33, 7, 1]
[9] [273343, 69692, 15366, 3440, 800, 188, 42, 8, 1]
|
|
MAPLE
|
# Uses function PMatrix from A357368. Adds column 1, 0, 0, ... to the left.
|
|
MATHEMATICA
|
(* p = indecomposable permutations = A003319 *) p[n_] := p[n] = n! - Sum[ k!*p[n-k], {k, 1, n-1}]; t[n_, k_] /; n < k = 0; t[n_, 1] := p[n]; t[n_, k_] /; n >= k := t[n, k] = Sum[ t[n-j, k-1]*p[j], {j, 1, n}]; Flatten[ Table[ t[n, k], {n, 1, 10}, {k, 1, n}] ] (* Jean-François Alcover, Mar 06 2012, after Philippe Deléham *)
|
|
PROG
|
(SageMath)
R = PolynomialRing(ZZ, 'x')
C = [R(0)] + [R(1) for i in range(dim+1)]
A = [(i + 2) // 2 for i in range(dim+1)]
A[0] = R.gen(); T = []
for k in range(1, dim+1) :
for n in range(k, 0, -1) :
C[n] = C[n-1] + C[n+1] * A[n-1]
T.append(list(C[1])[1::])
return T
(SageMath) Alternatively, using the function PartTrans from A357078:
# Adds a (0, 0)-based column (1, 0, 0, ...) to the left of the triangle.
dim = 10
A = ZZ[['t']]; g = A([0]+[factorial(n) for n in range(1, 30)]).O(dim+2)
PartTrans(dim, lambda n: list(g / (1 + g))[n]) # Peter Luschny, Sep 11 2022
|
|
CROSSREFS
|
A version with reflected rows is A263484.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|