login
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.
5
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.
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
KEYWORD
nonn,tabl
AUTHOR
Samira Stitou, Sep 21 2015
EXTENSIONS
More terms from Alois P. Heinz, Oct 07 2015
STATUS
approved