A187105 Triangle T(n,k) read by rows: number of height-2-restricted finite functions.

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, 6322, 10156, 5028, 1424, 290, 48, 7, 1, 41393, 80838, 44217, 13204, 2745, 450, 63, 8, 1, 293608, 698704, 424434, 134680, 28900, 4776, 658, 80, 9, 1

Offset: 1

Author

Dennis P. Walsh, Mar 04 2011

Keywords

• nonn
• nice
• easy
• tabl

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.]

Examples

			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>.
		

Links

• Dennis Walsh, Notes on height-restricted finite functions

Crossrefs

Cf. A000248, A275707, A355501.

Programs

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

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).