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.

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

References

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

Links

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

Formula

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

Example

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

Crossrefs

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

Sequence in context: A221035 A221499 A059579 * A091320 A225468 A048787

Adjacent sequences: A261760 A261761 A261762 * A261764 A261765 A261766

Keyword

nonn,tabl

Author

Samira Stitou, Sep 21 2015

Extensions

More terms from Alois P. Heinz, Oct 07 2015

Status

approved