A276999 Triangle read by rows, T(n,k) = n^k - 2^(k/2)*KummerU(-k/2,1/2,n^2/2) for 0<=k<=n.

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

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

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

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

T(n,k) = n^k - A244490(n,k), T(n,3) = A008585(n) for n>=3, T(n,4) = A224334(n-1) for n>=4, T(n,5) = A127694(n-3) for n>=5.

Sequence in context: A353803 A275153 A019313 * A223082 A318374 A259107

Adjacent sequences: A276996 A276997 A276998 * A277000 A277001 A277002

Keyword

nonn,tabl

Author

Peter Luschny, Oct 06 2016

Status

approved