A144085 -id:A144085 - cp's OEIS frontend

A261762 Triangle read by rows: T(n,k) is the number of subpermutations of an n-set whose orbits are each of size at most k, and without fixed points. Equivalently, T(n,k) is the number of partial derangements of an n-set each of whose orbits is of size at most k.

1, 1, 1, 1, 1, 4, 1, 1, 10, 18, 1, 1, 46, 78, 108, 1, 1, 166, 486, 636, 780, 1, 1, 856, 3096, 4896, 5760, 6600, 1, 1, 3844, 21204, 40104, 52200, 58080, 63840, 1, 1, 21820, 167868, 363168, 508320, 602400, 648480, 693840, 1, 1, 114076, 1370268, 3490848, 5450400, 6720480

Offset: 0

Samira Stitou, Sep 21 2015

The OEIS values correct the values b(n,k) in the Laradji-Umar Table 2.1 in column k=2. Note that the row sums (meaning: sums up to the diagonal of the triangle) in Table 2.1 in the article are also incorrect.

There were typos in the column (k=2) of the original article. The entry 94 should be 166 and the entry 784 should be 856, which have been corrected. Unlike most triangles the off-diagonal terms are not 0 because T(n, n)= T(n, n+k) for all nonnegative k which is obvious from the definition.

			T(3,2) = 10 because there are 10 subpermutations on {1,2,3}, each of whose orbit is of size at most 2, and without fixed points, namely: Empty map, (1,2) --> (2,1), (1,3) --> (3,1) (2,3) --> (3,2),  1-->2, 1-->3, 2-->1,  2-->3, 3-->1, 3-->2.
Triangle starts:
1;
1, 1;
1, 1, 4;
1, 1, 10, 18;
1, 1, 46, 78, 108;
1, 1, 166, 486, 636, 780;
...

A. Laradji and A. Umar, On the number of subpermutations with fixed orbit size, Ars Combinatoria, 109 (2013), 447-460.

Cf. A157400, A261763, A261764, A261765, A261766, A261767.

A261762 := proc(n,k)
    if k = 0 then
        1;
    else
        if k < 1 then
            g := 1;
        elif k < 2 then
            g := exp(x) ;
        else
            g := exp(x+add((j+1)*x^j/j,j=2..k)) ;
        fi;
        coeftayl(g,x=0,n) *n! ;
    end if;
end proc:
seq(seq( A261762(n,k),k=0..n),n=0..12) ; # R. J. Mathar, Nov 04 2015

T[n_, k_] := SeriesCoefficient[ Exp[ x + Sum[ (j+1)*x^j/j, {j, 2, k}]], {x, 0, n}] * n!; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Apr 13 2017 *)

T(n,k) = T(n-1,k) + 3(n-1)T(n-2,k) + ... +(k+1)(n-1)(n-2)...(n-k+1)T(n-k,k) if k<=n.
T(n,k) = T(n,n) if k>n, not part of the triangle.
T(n,0) = T(n,1) = 1.
T(n,n) = A144085(n). (Diagonal)
G.f.: exp(x+(3x^2)/2+ ... +((k+1)x^k)/k).

More terms from Alois P. Heinz, Oct 07 2015

A261765 Triangle read by rows: T(n,k) is the number of subpermutations of an n-set, whose orbits are each of size at most k with at least one orbit of size exactly k, and without fixed points. Equivalently, T(n,k) is the number of partial derangements of an n-set each of whose orbits is of size at most k with at least one orbit of size exactly k, and without fixed points.

Original entry on oeis.org

1, 1, 0, 1, 0, 3, 1, 0, 9, 8, 1, 0, 45, 32, 30, 1, 0, 165, 320, 150, 144, 1, 0, 855, 2240, 1800, 864, 840, 1, 0, 3843, 17360, 18900, 12096, 5880, 5760, 1, 0, 21819, 146048, 195300, 145152, 94080, 46080, 45360, 1, 0, 114075, 1256192, 2120580, 1959552, 1270080, 829440, 408240, 403200

Offset: 0

Samira Stitou, Sep 21 2015

T(n,n) is A261766. Sum of rows is A144085.

			T(n,1) = 0 because there is no (partial) derangement with an orbit of size 1.
T(3,2) = 9 because there are 9 subpermutations on {1,2,3}, whose orbits are each of size at most 2 with at least one orbit of size exactly 2, and without fixed points, namely: (1 2 --> 2 1), (1 3 --> 3 1), (2 3 --> 3 2), (1-->2), (1-->3), (2-->1), (2-->3), (3-->1), (3-->2).
Triangle starts:
1;
1, 0;
1, 0, 3;
1, 0, 9, 8;
1, 0, 45, 32, 30;
1, 0, 165, 320, 150, 144;
1, 0, 855, 2240, 1800, 864, 840;
...

A. Laradji and A. Umar, On the number of subpermutations with fixed orbit size, Ars Combinatoria, 109 (2013), 447-460.

Cf. A157400, A261762, A261763, A261764, A261766, A261767.

T(n,k) = A261762(n,k) - A261762(n,k-1).

More terms from Alois P. Heinz, Nov 04 2015

A144087 a(n) is the number of partial bijections (or subpermutations) of an n-element set with exactly 2 fixed points.

Original entry on oeis.org

0, 0, 1, 3, 24, 180, 1620, 16380, 184800, 2298240, 31222800, 459874800, 7296791040, 124047443520, 2248897210560, 43301275617600, 882304501478400, 18964350332928000, 428768570841811200, 10170992126597702400, 252555415474602240000, 6550785133563775104000, 177151172210521513804800

Offset: 0

Abdullahi Umar, Sep 11 2008

nonn

			a(3) = 3 because there are exactly 3 partial bijections (on a 3-element set) with exactly 2 fixed points, namely: (1,2)->(1,2), (1,3)->(1,3), (2,3)->(2,3) - the mappings are coordinate-wise.

Vaclav Kotesovec, Table of n, a(n) for n = 0..440
A. Laradji and A. Umar, Combinatorial results for the symmetric inverse semigroup, Semigroup Forum 75, (2007), 221-236.

Column k=2 of A144088.

Cf. A144085.

x='x+O('x^66); /* that many terms */
k=2; egf=x^k/k!*exp(x^2/(1-x))/(1-x);
Vec(serlaplace(egf)) /* show terms, starting with 1 */
/* Joerg Arndt, Jul 11 2011 */

a(n) = (n*(n-1)/2)*A144085(n-2).
E.g.f.: (x^k/k!)*exp(x^2/(1-x))/(1-x) where k=2. - Joerg Arndt, Jul 11 2011
a(n) = (n!/2)*Sum_{m=0..n-2} (-1^m/m!)*Sum_{j=0..n-m} C(n-m,j)/j!;
(n-2)*a(n) = n*(2*n-5)*a(n-1) - n*(n-1)*(n-5)*a(n-2) - n*(n-1)*(n-2)*a(n-3), a(2)=1 and a(n)=0 if n < 2.
a(n) ~ n^(n + 1/4) * exp(2*sqrt(n) - 3/2 - n) / 2^(3/2) * (1 - 17/(48*sqrt(n))). - Vaclav Kotesovec, Dec 01 2021
a(n) = (n!/2) * Sum_{k=0..n-2} binomial(k,n-2-k)/(n-2-k)!. - Seiichi Manyama, Aug 06 2024

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

Original entry on oeis.org

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

A144086 Number of partial bijections (or subpermutations) of an n-element set with exactly 1 fixed point.

Original entry on oeis.org

0, 1, 2, 12, 72, 540, 4680, 46200, 510720, 6244560, 83613600, 1216131840, 19084222080, 321271030080, 5773503415680, 110288062684800, 2231100039168000, 47640952315756800, 1070630750168179200, 25255541547460224000, 623884298434645248000, 16104652019138319436800

Offset: 0

Abdullahi Umar, Sep 10 2008, Sep 15 2008

nonn

			a(3) = 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.

Vincenzo Librandi, Table of n, a(n) for n = 0..200
A. Laradji and A. Umar, Combinatorial results for the symmetric inverse semigroup, Semigroup Forum 75, (2007), 221-236.

Column k=1 of A144088.

Cf. A144085.

CoefficientList[Series[x*E^(x^2/(1-x))/(1-x), {x, 0, 20}], x] * Range[0, 20]! (* Vaclav Kotesovec, Feb 24 2014 *)

x='x+O('x^66); /* that many terms */
k=1; egf=x^k/k!*exp(x^2/(1-x))/(1-x);
Vec(serlaplace(egf)) /* show terms, starting with 1 */
/* Joerg Arndt, Jul 11 2011 */

a(n) = n*A144085(n-1).
E.g.f.: (x^k/k!)*exp(x^2/(1-x))/(1-x) where k=1. - Joerg Arndt, Jul 11 2011
a(n) = n!*Sum_{m=0..n-1} (-1^m/m!)*Sum_{j=0..n-m} C(n-m)/j!;
(n-1)*a(n) = n*(2*n-3)*a(n-1) - n*(n-1)*(n-4)*a(n-2) - n*(n-1)*(n-2)*a(n-3), a(1)=1 and a(n)=0 if n < 1.
a(n) ~ n^(n+1/4) * exp(2*sqrt(n)-n-3/2) / sqrt(2) * (1 + 31/(48*sqrt(n))). - Vaclav Kotesovec, Feb 24 2014
a(n) = n! * Sum_{k=0..n-1} binomial(k,n-1-k)/(n-1-k)!. - Seiichi Manyama, Aug 06 2024

A144089 T(n,k) is the number of partial bijections (or subpermutations) of an n-element set of height k (height(alpha) = |Im(alpha)|) and without fixed points.

Original entry on oeis.org

1, 1, 0, 1, 2, 1, 1, 6, 9, 2, 1, 12, 42, 44, 9, 1, 20, 130, 320, 265, 44, 1, 30, 315, 1420, 2715, 1854, 265, 1, 42, 651, 4690, 16275, 25494, 14833, 1854, 1, 56, 1204, 12712, 70070, 198184, 263284, 133496, 14833, 1, 72, 2052, 29904, 240534, 1076544, 2573508

Offset: 0

Abdullahi Umar, Sep 11 2008

Rows also give coefficients of the matching-generating polynomial of the n-crown graph. - Eric W. Weisstein May 19 2017

			T(3,2) = 9 because there are exactly 9 partial bijections (on a 3-element set) without fixed points and of height 2, namely: (1,2)->(2,1), (1,2)->(2,3), (1,2)->(3,1), (1,3)->(2,1), (1,3)->(3,1), (1,3)->(3,2), (2,3)->(1,2), (2,3)->(3,1), (2,3)->(3,2),- the mappings are coordinate-wise.
Triangle starts:
  1;
  1,  0;
  1,  2,   1;
  1,  6,   9,   2;
  1, 12,  42,  44,   9;
  1, 20, 130, 320, 265, 44;

A. Laradji and A. Umar, Combinatorial results for the symmetric inverse semigroup, Semigroup Forum 75, (2007), 221-236.
Eric Weisstein's World of Mathematics, Crown Graph
Eric Weisstein's World of Mathematics, Matching-Generating Polynomial

Row sums give A144085.

Cf. A000166.

t[n_, k_] := n!^2*Hypergeometric1F1[-k, -n, -1]/(k!*(n-k)!^2); Flatten[ Table[ t[n, k], {n, 0, 7}, {k, 0, n}]] (* Jean-François Alcover, Oct 13 2011 *)
CoefficientList[Table[x^n n! Sum[(-1)^k/k! LaguerreL[n - k, -1/x], {k, 0, n}], {n, 2, 10}], x] // Flatten (* Eric W. Weisstein, May 19 2017 *)

def A144089_triangle(dim): # computes rows in reversed order
    M = matrix(ZZ,dim,dim)
    for n in (0..dim-1): M[n,n] = 1
    for n in (1..dim-1):
        for k in (0..n-1):
            M[n,k] = M[n-1,k-1]+(2*k)*M[n-1,k]+(k+1)^2*M[n-1,k+1]
    return M
A144089_triangle(9) # Peter Luschny, Sep 19 2012

T(n,k) = (n!/(n-k)!)*Sum_{m=0..k}(-1^m/m!)*binomial(n-m,k-m).
T(n,n-1) = A000166(n+1) and T(n,n) = A000166(n).
E.g.f.:  exp(log(1/(1-y*x))-y*x)*exp(x/(1 - y*x)). - Geoffrey Critzer, Feb 18 2022

A211709 T(n,k) = number of n X k nonnegative integer arrays with new values 0 upwards introduced in row major order and every value unique in its row and column.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 18, 18, 1, 1, 108, 588, 108, 1, 1, 780, 30240, 30240, 780, 1, 1, 6600, 2277600, 17427192, 2277600, 6600, 1, 1, 63840, 234440280, 17741309400, 17741309400, 234440280, 63840, 1, 1, 693840, 31448589480

Offset: 1

R. H. Hardin, Apr 19 2012

			Table starts:
  1     1         1           1           1         1           1      1 1
  1     4        18         108         780      6600       63840 693840
  1    18       588       30240     2277600 234440280 31448589480
  1   108     30240    17427192 17741309400
  1   780   2277600 17741309400
  1  6600 234440280
  1 63840
  1
Some solutions for n=4, k=4:
  0 1 2 3    0 1 2 3    0 1 2 3    0 1 2 3    0 1 2 3
  1 4 0 2    1 2 0 4    4 2 0 1    1 0 3 2    1 0 3 2
  2 0 5 1    2 0 1 5    1 0 3 2    2 3 0 4    4 2 0 1
  3 2 1 4    3 4 5 0    2 3 1 0    3 2 1 0    5 3 1 0

Column 2 is A144085.

A369292 Array read by downward antidiagonals: A(n,k) = -A(n-1,k) + (k+1)*A(n-1,k+1) + A(n-1,k+2) with A(0,k) = 1, n >= 0, k >= 0.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 1, 3, 8, 18, 1, 4, 14, 42, 108, 1, 5, 22, 84, 276, 780, 1, 6, 32, 150, 612, 2160, 6600, 1, 7, 44, 246, 1212, 5220, 19560, 63840, 1, 8, 58, 378, 2196, 11280, 50880, 200760, 693840, 1, 9, 74, 552, 3708, 22260, 118560, 556920, 2299920, 8361360

Offset: 0

Mikhail Kurkov, Jan 24 2024

			Array begins:
=====================================================
n\k|    0     1     2      3      4      5      6 ...
---+-------------------------------------------------
0  |    1     1     1      1      1      1      1 ...
1  |    1     2     3      4      5      6      7 ...
2  |    4     8    14     22     32     44     58 ...
3  |   18    42    84    150    246    378    552 ...
4  |  108   276   612   1212   2196   3708   5916 ...
5  |  780  2160  5220  11280  22260  40800  70380 ...
6  | 6600 19560 50880 118560 252120 496920 919200 ...
  ...

Column k=0 is A144085.

Rows n=0..2 are A000012, A000027(n+1), A014206(n+1).

A(m,n=m)={my(r=vectorv(m+1), v=vector(n+2*m+1,k,1)); r[1] = v[1..n+1];
for(i=1, m, v=vector(#v-2, k, -v[k] + k*v[k+1] + v[k+2]); r[1+i] = v[1..n+1]); Mat(r)}
{ A(6) } \\ Andrew Howroyd, Jan 24 2024

cp's OEIS Frontend

A261762 Triangle read by rows: T(n,k) is the number of subpermutations of an n-set whose orbits are each of size at most k, and without fixed points. Equivalently, T(n,k) is the number of partial derangements of an n-set each of whose orbits is of size at most k.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Formula

Extensions

A144087 a(n) is the number of partial bijections (or subpermutations) of an n-element set with exactly 2 fixed points.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

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

A144086 Number of partial bijections (or subpermutations) of an n-element set with exactly 1 fixed point.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A144089 T(n,k) is the number of partial bijections (or subpermutations) of an n-element set of height k (height(alpha) = |Im(alpha)|) and without fixed points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

A211709 T(n,k) = number of n X k nonnegative integer arrays with new values 0 upwards introduced in row major order and every value unique in its row and column.

Views

Author

Keywords

Examples

Crossrefs

A369292 Array read by downward antidiagonals: A(n,k) = -A(n-1,k) + (k+1)*A(n-1,k+1) + A(n-1,k+2) with A(0,k) = 1, n >= 0, k >= 0.

Views

Author

Keywords

Examples

Crossrefs