A216294 Triangular array read by rows: T(n,k) is the number of partial permutations of {1,2,...,n} that have exactly k cycles, 0<=k<=n.

1, 1, 1, 3, 3, 1, 13, 14, 6, 1, 73, 84, 41, 10, 1, 501, 609, 325, 95, 15, 1, 4051, 5155, 2944, 965, 190, 21, 1, 37633, 49790, 30023, 10689, 2415, 343, 28, 1, 394353, 539616, 340402, 129220, 32179, 5348, 574, 36, 1, 4596553, 6478521, 4246842, 1698374, 455511, 84567, 10794, 906, 45, 1

Offset

0,4

Comments

A partial permutation on a set X is a bijection between two subsets of X.

Row sums are A002720.

First column (corresponding to k=0) is A000262.

Links

Alois P. Heinz, Rows n = 0..50, flattened

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 132.

Formula

E.g.f.: exp(x/(1-x))/(1-x)^y.

From Peter Bala, Aug 23 2013: (Start)

Exponential Riordan array [exp(x/(1-x)), log(1/(1-x))].

The row polynomials R(n,y), n > = 0, satisfy the 2nd order recurrence equation R(n,y) = (2*n + y - 1)*R(n-1,y) - (n - 1)*(n + y - 2)*R(n-2,y) with R(0,y) = 1 and R(1,y) = 1 + y.

Modulo variations in offset we have: R(n,0) = A000262, R(n,1) = A002720, R(n,2) = A000262, R(n,3) = A052852, R(n,4) = A062147, R(n,5) = A062266 and R(n,6) = A062192. In general, for fixed k, the sequence {R(n,k)}n>=1 gives the entries on a diagonal of the square array A088699. (End)

Example

1;
1,     1;
3,     3,   1;
13,   14,   6,  1;
73,   84,  41, 10,  1;
501, 609, 325, 95, 15,  1;

Maple

gf := exp(x / (1 - x)) / (1 - x)^y:
serx := series(gf, x, 10): poly := n -> simplify(coeff(serx, x, n)):
seq(print(seq(n!*coeff(poly(n), y, k), k = 0..n)), n = 0..9); # Peter Luschny, Feb 23 2023

Mathematica

nn=10; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; f[list_]:=Select[list, #>0&]; Map[f, Range[0, nn]!CoefficientList[Series[Exp[ x/(1-x)]/(1-x)^y, {x, 0, nn}], {x, y}]]//Flatten

Crossrefs

Cf. A021009. A000262, A002720, A052852, A062147, A062192, A062266, A088699.

Sequence in context: A062746 A115193 A227343 * A039797 A143171 A112292

Adjacent sequences: A216291 A216292 A216293 * A216295 A216296 A216297

Keyword

nonn,tabl

Author

Geoffrey Critzer, Sep 04 2012

Status

approved