A144086 -id:A144086 - 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.

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

Abdullahi Umar, Sep 11 2008, Sep 16 2008

			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.

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.

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

Row sums give A002720.

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 *)

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

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

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

A144090 Triangle read by rows: T(n,k) is the number of partial bijections (or subpermutations) of an n-element set of height k (height(alpha) = |Im(alpha)|) and with exactly 1 fixed point.

Original entry on oeis.org

1, 2, 0, 3, 6, 3, 4, 24, 36, 8, 5, 60, 210, 220, 45, 6, 120, 780, 1920, 1590, 264, 7, 210, 2205, 9940, 19005, 12978, 1855, 8, 336, 5208, 37520, 130200, 203952, 118664, 14832, 9, 504, 10836, 114408, 630630, 1783656, 2369556, 1201464, 133497

Offset: 1

Abdullahi Umar, Sep 11 2008

			T(3,2) = 6 because there are exactly 6 partial bijections (on a 3-element set) with exactly 1 fixed point and of height 2, namely: (1,2)->(1,3), (1,2)->(3,2), (1,3)->(1,2), (1,3)->(2,3), (2,3)->(2,1), (2,3)->(1,3)- the mappings are coordinate-wise.
First six rows:
1
2      0
3      6      3
4     24     36       8
5     60    210     220      45
6    120    780    1920    1590    264

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

Rows sums are A144086.

Main diagonal gives A000240.

Table[(n!/(n - k)!) Sum[ ((-1)^m/m!) Binomial[n - 1 - m, k - 1 - m], {m, 0, k - 1}], {n, 9}, {k, n}] // Flatten (* Michael De Vlieger, Apr 27 2016 *)

T(n,k) = (n!/(n-k)!)*sum(m=0,k-1,((-1)^m/m!)*binomial(n-1-m,k-1-m));
for (n=1, 10, for (k=1, n, print1(T(n,k), ", "))) \\ Michel Marcus, Apr 27 2016

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

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions