login
Triangle read by rows: T(n,k) (0 <= k <= n) = Sum_{i=0..[k/2]} (-1)^i*binomial(k,2*i)*(2*i-1)!!*n^(k-2*i).
3

%I #36 Mar 07 2020 14:57:40

%S 1,1,1,1,2,3,1,3,8,18,1,4,15,52,163,1,5,24,110,478,1950,1,6,35,198,

%T 1083,5706,28821,1,7,48,322,2110,13482,83824,505876,1,8,63,488,3715,

%U 27768,203569,1461944,10270569,1,9,80,702,6078,51894,436656,3618540,29510268,236644092,1,10,99,970,9403,90150,854485,8003950,74058105,676549450,6098971555

%N Triangle read by rows: T(n,k) (0 <= k <= n) = Sum_{i=0..[k/2]} (-1)^i*binomial(k,2*i)*(2*i-1)!!*n^(k-2*i).

%C 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 no 2-cycles}). For instance T(3,3) = 18 because there are 27 functions [3] -> [3], 9 of which have a 2-cycle. - _Peter Luschny_, Oct 05 2016

%H J. East, R. D. Gray, <a href="http://arxiv.org/abs/1404.2359">Idempotent generators in finite partition monoids and related semigroups</a>, arXiv preprint arXiv:1404.2359 [math.GR], 2014.

%F From _Peter Luschny_, Oct 05 2016: (Start)

%F T(n,k) = 2^(-k/2)*HermiteH(k, n/sqrt(2)).

%F T(n,k) = 2^((k-1)/2)*n*KummerU((1-k)/2, 3/2, n^2/2) for n>=1.

%F T(n,k) = n^k*hypergeom([-k/2, (1-k)/2], [], -2/n^2) for n>=1. (End)

%e Triangle begins:

%e 1

%e 1 1

%e 1 2 3

%e 1 3 8 18

%e 1 4 15 52 163

%e 1 5 24 110 478 1950

%e 1 6 35 198 1083 5706 28821

%e 1 7 48 322 2110 13482 83824 505876

%e 1 8 63 488 3715 27768 203569 1461944 10270569

%e 1 9 80 702 6078 51894 436656 3618540 29510268 236644092

%e ...

%p T := (n,k) -> add((-1)^i*binomial(k,2*i)*doublefactorial(2*i-1)*n^(k-2*i), i=0..k/2):

%p seq(seq(T(n,k), k=0..n), n=0..10); # _Peter Luschny_, Oct 05 2016

%t Table[Simplify[2^(-k/2) HermiteH[k, n/Sqrt[2]]], {n, 0, 10}, {k,0,n}] // Flatten (* _Peter Luschny_, Oct 05 2016 *)

%o (Sage)

%o def T(n, k):

%o @cached_function

%o def h(n, x):

%o if n == 0: return 1

%o if n == 1: return 2*x

%o return 2*(x*h(n-1,x)-(n-1)*h(n-2,x))

%o return h(k, n/sqrt(2))/2^(k/2)

%o for n in range(10):

%o print([T(n,k) for k in (0..n)]) # _Peter Luschny_, Oct 05 2016

%Y As has been noticed by _Tom Copeland_: T(n,0) = A000012(n), T(n,1) = A001477(n) for n>=1, T(n,2) = A067998(n+1) for n>=3, T(n,3) = A121670(n) for n>=3.

%Y Cf. A276999.

%K nonn,tabl

%O 0,5

%A _N. J. A. Sloane_, Jul 05 2014