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,6

Comments

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.

Links

Table of n, a(n) for n=0..51.

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

Formula

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

Example

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

Maple

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

Mathematica

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

Crossrefs

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

Sequence in context: A164366 A121692 A264614 * A225062 A145271 A232774

Adjacent sequences: A261759 A261760 A261761 * A261763 A261764 A261765

Keyword

nonn,tabl

Author

Samira Stitou, Sep 21 2015

Extensions

More terms from Alois P. Heinz, Oct 07 2015

Status

approved