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
Examples
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.
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.
Programs
-
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 *) -
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
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
T(n,k) = (n!/k!) * Sum_{j=0..n-k} binomial(j,n-k-j)/(n-k-j)!. - Seiichi Manyama, Aug 06 2024
Extensions
Terms a(36) and beyond from Andrew Howroyd, Nov 29 2021