OFFSET
1,4
COMMENTS
Triangle T(n,k) with 1 <= k <= n+1 is the number of functions f:[n+1-k]->[n+1] such that f(f(f(x))) is undefined, that is, either f(x) or f(f(x)) is in {n+2-k,...,n+1}. Such functions are called height-2 restricted functions. Note that the null function, which occurs when k=n+1, vacuously satisfies the conditions for a height-2 restricted function, and hence T(n,n+1)=1. The sequence a(n)=T(n,1) is sequence A000248, the number of forests with n nodes and height at most 1. The height of a function f:D->C, with D a proper subset of finite C, is the maximum h such that (f^h)(x) exists for some x in D. A height restricted function f is acyclic since, if x is in a cycle of f, then (f^z)(x) exists for all positive integers z. [Note that [m] denotes the set of the first m positive integers and that f^m denotes the m-fold self-composition of f so that (f^0)(x)=x, (f^1)(x)=f(x),(f^2)(x)=f(f(x)), etc.]
LINKS
FORMULA
T(n,k) = Sum_{j=0..n+1-k}binomial(n+1-k,j)*k^j*j^(n+1-k-j) for n>=0 and T(0,k) for k>=1.
E.g.f. of column k: exp(k*x*exp(x)).
With t(n,k) = T(n+k-1,k), t(n,k+j) = Sum_{i=0..n}binomial(n,i)*t(i,k)*t(n-i,j).
EXAMPLE
Triangle of initial terms:
1
1 1
3 2 1
10 8 3 1
41 38 15 4 1
196 216 90 24 5 1
1057 1402 633 172 35 6 1
T(4,3) = 15 since there are 15 functions f:[2]->[5] such that either f(x) or f(f(x)) is in {3,4,5}. Using <f(1),f(2)> to denote these functions we have the following 15 functions: <2,3>, <2,4>, <2,5>, <3,1>, <3,3>, <3,4>, <3,5>, <4,1>, <4,3>, <4,4>, <4,5>, <5,1>, <5,3>, <5,4>, <5,5>.
MAPLE
seq(seq(sum(binomial(n+1-k, j)*k^j*j^(n+1-k-j), j=0..(n+1-k)), k=1..n), n=1..15); # triangle's right edge of ones is omitted with this program
MATHEMATICA
t[n_, k_] := If[ k == n + 1, 1, Sum[ Binomial[n + 1 - k, j]*k^j*j^(n + 1 - k - j), {j, 0, n + 1 - k}]]; Table[ t[n, k], {n, 0, 9}, {k, n + 1}] // Flatten
CROSSREFS
KEYWORD
AUTHOR
Dennis P. Walsh, Mar 04 2011
STATUS
approved