A144088 T(n,k) is the number of partial bijections (or subpermutations) of an n-element set with exactly k fixed points.

1, 1, 1, 4, 2, 1, 18, 12, 3, 1, 108, 72, 24, 4, 1, 780, 540, 180, 40, 5, 1, 6600, 4680, 1620, 360, 60, 6, 1, 63840, 46200, 16380, 3780, 630, 84, 7, 1, 693840, 510720, 184800, 43680, 7560, 1008, 112, 8, 1, 8361360, 6244560, 2298240, 554400, 98280, 13608, 1512, 144, 9, 1

Offset

0,4

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows n = 0..50)

A. Laradji and A. Umar, Combinatorial results for the symmetric inverse semigroup, Semigroup Forum 75, (2007), 221-236.

A. Umar, Some combinatorial problems in the theory of symmetric ..., Algebra Disc. Math. 9 (2010) 115-126.

Formula

T(n,k) = C(n,k)*(n-k)! * Sum_{m=0..n-k} (-1^m/m!)*Sum_{j=0..n-m} C(n-m,j)/j!.

(n-k)*T(n,k) = n*(2n-2k-1)*T(n-1,k) - n*(n-1)*(n-k-3)*T(n-2,k) - n*(n-1)*(n-2)*T(n-3,k), T(k,k)=1 and T(n,k)=0 if n < k.

E.g.f.: exp(log(1/(1-x)) - x + y*x)*exp(x/(1-x)). - Geoffrey Critzer, Nov 29 2021

Example

Triangle begins:
      1;
      1,     1;
      4,     2,     1;
     18,    12,     3,    1;
    108,    72,    24,    4,   1;
    780,   540,   180,   40,   5,  1;
   6600,  4680,  1620,  360,  60,  6, 1;
  63840, 46200, 16380, 3780, 630, 84, 7, 1;
  ...
T(3,1) = 12 because there are exactly 12 partial bijections (on a 3-element set) with exactly 1 fixed point, namely: (1)->(1), (2)->(2), (3)->(3), (1,2)->(1,3), (1,2)->(3,2), (1,3)->(1,2), (1,3)->(2,3), (2,3)->(2,1), (2,3)->(1,3), (1,2,3)->(1,3,2), (1,2,3)->(3,2,1), (1,2,3)->(2,1,3) -- the mappings are coordinate-wise.

Mathematica

max = 7; f[x_, k_] := (x^k/k!)*(Exp[x^2/(1-x)]/(1-x)); t[n_, k_] := n!*SeriesCoefficient[ Series[ f[x, k], {x, 0, max}], n]; Flatten[ Table[ t[n, k], {n, 0, max}, {k, 0, n}]](* Jean-François Alcover, Mar 12 2012, from e.g.f. by Joerg Arndt *)

Prog

(PARI)
T(n) = {my(egf=exp(log(1/(1-x) + O(x*x^n)) - x + y*x + x/(1-x))); Vec([Vecrev(p) | p<-Vec(serlaplace(egf))])}
{ my(A=T(10)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Nov 29 2021

Crossrefs

T(n, 0) = A144085, T(n, 1) = A144086, T(n, 2) = A144087.

Row sums give A002720.

Sequence in context: A264535 A256039 A152391 * A039948 A111536 A111559

Adjacent sequences: A144085 A144086 A144087 * A144089 A144090 A144091

Keyword

nice,nonn,tabl

Author

Abdullahi Umar, Sep 11 2008, Sep 16 2008

Extensions

Terms a(36) and beyond from Andrew Howroyd, Nov 29 2021

Status

approved