Samira Stitou - 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

A261767 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.

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 7, 18, 8, 1, 15, 99, 64, 30, 1, 31, 510, 560, 300, 144, 1, 63, 2745, 4800, 3150, 1728, 840

Offset: 0

Samira Stitou, Sep 21 2015

			T(3, 2) = 18 because there are 18 subpermutations on {1,2,3} whose orbits are each of size at most 2 with at least one orbit of size exactly 2, namely: (1 2 --> 2 1), (1 3 --> 3 1), (2 3 --> 3 2), (123 --> 213), (123 --> 321), (123 --> 132); (1-->2), (1-->3), (2-->1), (2-->3), (3-->1), (3-->2); (13-->23), (12-->32), (23-->13), (32-->33), (23-->21), (13-->12).
Triangle starts:
1;
1, 1;
1, 3, 3;
1, 7, 18, 8;
1, 15, 99, 64, 30;
1, 31, 510, 560, 300, 144;
...

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

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

Row sums give A002720.

T(n, k) = A261763(n, k) - A261763(n, k-1), T(n, n) = A261766(n) for all n not equal to 1 and T(1, 1) = 1.

A261766 a(n) is the number of partial derangements of an n-set with at least one orbit of size exactly n.

Original entry on oeis.org

1, 0, 3, 8, 30, 144, 840, 5760, 45360, 403200, 3991680, 43545600, 518918400, 6706022400, 93405312000, 1394852659200, 22230464256000, 376610217984000, 6758061133824000, 128047474114560000, 2554547108585472000, 53523844179886080000, 1175091669949317120000

Offset: 0

Samira Stitou, Sep 21 2015

nonn

			a(3) = 8 because there are 8 partial derangements on {1,2,3} with at least one orbit of size 3 namely: (1,2) --> (2,3), (1,2)  --> (3,1), (1,3)  --> (2,1), (1,3) --> (3,2), (2,3)  --> (3,1), (2,3)  --> (1,2), (1,2,3) --> (2,3,1), (1,2,3)  --> (3,1,2).

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

Cf. A001048, A059171, A157400, A261762, A261763, A261764, A261765, A261767.

a(n) = A261765(n,n) - A261765(n,n-1) for n>0, a(0)=1.

More terms from Alois P. Heinz, Nov 04 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

A261764 Triangle read by rows: T(n,k) is the number of nilpotent subpermutations on an n-set, each of nilpotency index less than or equal to k.

Original entry on oeis.org

1, 0, 1, 0, 1, 3, 0, 1, 7, 13, 0, 1, 25, 49, 73, 0, 1, 81, 261, 381, 501, 0, 1, 331, 1531, 2611, 3331, 4051, 0, 1, 1303, 9073, 19993, 27553, 32593, 37633, 0, 1, 5937, 63393, 165873, 253233, 313713, 354033, 394353, 0, 1, 26785, 465769, 1436473, 2540233, 3326473, 3870793, 4233673, 4596553

Offset: 0

Samira Stitou, Sep 21 2015

			T(3,2) = 7 because there are 7 nilpotent subpermutations on {1,2,3}, each of nilpotency index less than or equal to 2, namely: empty map, 1-->2, 1-->3, 2-->1, 2-->3, 3-->1, 3-->2.
Triangle starts:
1;
0, 1;
0, 1,   3;
0, 1,   7,   13;
0, 1,  25,   49,   73;
0, 1,  81,  261,  381,  501;
0, 1, 331, 1531, 2611, 3331, 4051;
...

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

Alois P. Heinz, Rows n = 0..140, flattened

Cf. A000262, A157400, A261762, A261763, A261765, A261766, A261767.

egf:= k-> exp(add(x^j, j=1..k)):
T:= (n, k)-> n!*coeff(series(egf(k), x, n+1), x, n):
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Oct 10 2015
# second Maple program:
T:= proc(n, k) option remember; `if`(n=0, 1, add(
      T(n-j, k)*binomial(n-1, j-1)*j!, j=1..min(n,k)))
    end:
seq(seq(T(n, k), k=0..n), n=0..10);  # Alois P. Heinz, Sep 29 2017

Table[n!*SeriesCoefficient[Exp[x*(x^k-1)/(x-1)], {x, 0, n}], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 18 2016 *)

T(n, k) = T(n-1, k) + 2(n-1)T(n-2, k) + ... + k(n-1) ... (n-k+1)T(n-k, k), with T(n, 1) = 1 and T(n, n+r) = T(n, n) for every nonnegative integer r.
T(n,n) = A000262(n).
E.g.f. of column k: exp(x + x^2 + ... + x^k).
T(n,k) = Sum_{i=0..k} A157400(n,i).

More terms from Alois P. Heinz, Oct 10 2015

A261763 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.

Original entry on oeis.org

1, 1, 2, 1, 4, 7, 1, 8, 26, 34, 1, 16, 115, 179, 209, 1, 32, 542, 1102, 1402, 1546, 1, 64, 2809, 7609, 10759, 12487, 13327, 1, 128, 15374, 56534, 92234, 113402, 125162, 130922, 1, 256, 89737, 457993, 865393, 1139569, 1304209, 1396369, 1441729

Offset: 0

Samira Stitou, Sep 21 2015

			T(3, 2) = 26 because there are 26 subpermutations on {1,2,3}, each of whose orbit is of size at most 2, namely:
Empty map, 1-->1, 1-->2, 1-->3, 2-->1, 2-->2, 2-->3, 3-->1, 3-->2, 3-->3, (1,2) --> (1,2), (1,3) --> (1,3), (2,3) --> (2,3), (1,2) --> (2,1), (1,3) --> (3,1), (2,3) --> (3,2), (1,2) --> (1,3), (1,3) --> (1,2), (2,3) --> (2,1), (1,2) --> (3,2), (1,3) --> (2,3), (2,3) --> (1,3), (1,2,3) --> (1,3,2), (1,2,3) --> (3,2,1), (1,2,3) --> (2,1,3), (1,2,3) --> (1,2,3).
Triangle starts:
1;
1, 2;
1, 4, 7;
1, 8, 26, 34;
1, 16, 115, 179, 209;
...

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

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

T(n,n) = A002720(n).
T(n,k) = Sum_{i=0..n} binomial(n,i)*A261762(n-i,k).
E.g.f. of column k: exp(Sum_{j=1..k} (j+1)*x^j/j).

More terms from Alois P. Heinz, Oct 07 2015

cp's OEIS Frontend

User: Samira Stitou

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

A261767 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.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

A261766 a(n) is the number of partial derangements of an n-set with at least one orbit of size exactly n.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

Extensions

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Formula

Extensions

A261764 Triangle read by rows: T(n,k) is the number of nilpotent subpermutations on an n-set, each of nilpotency index less than or equal to k.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A261763 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.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

Extensions