|
| |
|
|
A187105
|
|
Triangle T(n,k) read by rows: number of height-2-restricted finite functions.
|
|
2
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
