cp's OEIS Frontend

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

%I A144088 #36 Aug 07 2024 00:52:09
%S A144088 1,1,1,4,2,1,18,12,3,1,108,72,24,4,1,780,540,180,40,5,1,6600,4680,
%T A144088 1620,360,60,6,1,63840,46200,16380,3780,630,84,7,1,693840,510720,
%U A144088 184800,43680,7560,1008,112,8,1,8361360,6244560,2298240,554400,98280,13608,1512,144,9,1
%N A144088 T(n,k) is the number of partial bijections (or subpermutations) of an n-element set with exactly k fixed points.
%H A144088 Andrew Howroyd, <a href="/A144088/b144088.txt">Table of n, a(n) for n = 0..1325</a> (rows n = 0..50)
%H A144088 A. Laradji and A. Umar, <a href="http://dx.doi.org/10.1007/s00233-007-0732-8">Combinatorial results for the symmetric inverse semigroup</a>, Semigroup Forum 75, (2007), 221-236.
%H A144088 A. Umar, <a href="http://www.mathnet.ru/eng/adm33">Some combinatorial problems in the theory of symmetric ...</a>, Algebra Disc. Math. 9 (2010) 115-126.
%F A144088 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!.
%F A144088 (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.
%F A144088 E.g.f.: exp(log(1/(1-x)) - x + y*x)*exp(x/(1-x)). - _Geoffrey Critzer_, Nov 29 2021
%F A144088 T(n,k) = (n!/k!) * Sum_{j=0..n-k} binomial(j,n-k-j)/(n-k-j)!. - _Seiichi Manyama_, Aug 06 2024
%e A144088 Triangle begins:
%e A144088       1;
%e A144088       1,     1;
%e A144088       4,     2,     1;
%e A144088      18,    12,     3,    1;
%e A144088     108,    72,    24,    4,   1;
%e A144088     780,   540,   180,   40,   5,  1;
%e A144088    6600,  4680,  1620,  360,  60,  6, 1;
%e A144088   63840, 46200, 16380, 3780, 630, 84, 7, 1;
%e A144088   ...
%e A144088 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.
%t A144088 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_ *)
%o A144088 (PARI)
%o A144088 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))])}
%o A144088 { my(A=T(10)); for(n=1, #A, print(A[n])) } \\ _Andrew Howroyd_, Nov 29 2021
%Y A144088 T(n, 0) = A144085, T(n, 1) = A144086, T(n, 2) = A144087.
%Y A144088 Row sums give A002720.
%K A144088 nice,nonn,tabl
%O A144088 0,4
%A A144088 _Abdullahi Umar_, Sep 11 2008, Sep 16 2008
%E A144088 Terms a(36) and beyond from _Andrew Howroyd_, Nov 29 2021