OFFSET
0,10
COMMENTS
East and Gray (p. 24) give a combinatorial interpretation of the numbers: A function f: Y -> X with Y <= X (<= inclusion) has a 2-cycle if there exists x, y in Y with x != y, f(x) = y and f(y) = x. Then T(n,k) = card({f: [k] -> [n]: f has 2-cycles}).
LINKS
J. East, R. D. Gray, Idempotent generators in finite partition monoids and related semigroups, arXiv preprint arXiv:1404.2359 [math.GR], 2014.
FORMULA
T(n,k) = n^k - 2^(-k/2)*HermiteH(k, n/sqrt(2)).
T(n,k) = n^k - Sum_{i=0..k/2} k!/((-2)^i*i!*(k-2*i)!)*n^(k-2*i).
T(n,k) = n^k*(1-hypergeom([-k/2, (1-k)/2], [], -2/n^2)) for n>=1.
T(n,k) ~ n^k*(((k-1)*k)/(2*n^2)-(k*(k^3-6*k^2+11*k-6))/(8*n^4)+(k*(k^5-15*k^4 +85*k^3-225*k^2+274*k-120))/(48*n^6)+O((1/n)^7)).
EXAMPLE
Triangle begins:
0;
0, 0;
0, 0, 1;
0, 0, 1, 9;
0, 0, 1, 12, 93;
0, 0, 1, 15, 147, 1175;
0, 0, 1, 18, 213, 2070, 17835;
0, 0, 1, 21, 291, 3325, 33825, 317667;
0, 0, 1, 24, 381, 5000, 58575, 635208, 6506647;
0, 0, 1, 27, 483, 7155, 94785, 1164429, 13536453, 150776397;
.
For instance T(3,3) = 9 because there are 27 functions [3]->[3], 18 of which have
no 2-cycles. The 9 functions which have 2-cycles are (represented as [f(1), f(2),
f(3)]): [1, 3, 2], [2, 1, 1], [2, 1, 2], [2, 1, 3], [2, 3, 2], [3, 1, 1],
[3, 2, 1], [3, 3, 1], [3, 3, 2].
MAPLE
T := (n, k) -> n^k - 2^(k/2)*KummerU(-k/2, 1/2, n^2/2):
seq(seq(simplify(T(n, k)), k=0..n), n=0..9);
MATHEMATICA
Table[Simplify[n^k - 2^(-k/2) HermiteH[k, n/Sqrt[2]]], {n, 0, 10}, {k, 0, n}] // Flatten
PROG
(Sage)
def T(n, k):
@cached_function
def h(n, x):
if n == 0: return 1
if n == 1: return 2*x
return 2*(x*h(n-1, x)-(n-1)*h(n-2, x))
return n^k - h(k, n/sqrt(2))/2^(k/2)
for n in range(10):
print([T(n, k) for k in (0..n)])
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Oct 06 2016
STATUS
approved