|
|
A189711
|
|
Number of non-monotonic functions from [k] to [n-k].
|
|
1
|
|
|
2, 10, 8, 28, 54, 22, 60, 190, 204, 52, 110, 490, 916, 676, 114, 182, 1050, 2878, 3932, 2118, 240, 280, 1988, 7278, 15210, 16148, 6474, 494, 408, 3444, 15890, 45738, 77470, 65210, 19576, 1004, 570, 5580, 31192, 115808, 278358, 389640, 261708, 58920, 2026, 770, 8580, 56484, 258720, 820118, 1677048, 1951700, 1048008, 176994, 4072, 1012, 12650, 96006, 525444, 2090296, 5758802, 10073698, 9763628, 4193580, 531262, 8166
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
5,1
|
|
COMMENTS
|
Triangle T(n,k), 3<=k<=n-2, given by (n-k)^k-2*C(n-1,k)+(n-k) is derived using inclusion/exclusion. The triangle contains several other listed sequences: T(2n,n) is sequence A056174(n), number of monotonic functions from [n] to [n]; T(n+2,n) is sequence A005803(n), second-order Eulerian numbers; and T(n,3) is A006331(n-4), maximum accumulated number of electrons at energy level n.
|
|
LINKS
|
|
|
FORMULA
|
T(n,k)=(n-k)^k-2*C(n-1,k)+(n-k).
|
|
EXAMPLE
|
Triangle T(n,k) begins
n\k 3 4 5 6 7 8 9
5 2
6 10 8
7 28 54 22
8 60 190 204 52
9 110 490 916 676 114
10 182 1050 2878 3932 2118 240
11 280 1988 7278 15210 16148 6474 494
...
For n=6 and k=4, T(6,4)=8 since there are 8 non-monotonic functions f from [4] to [2], namely, f = <f(1),f(2),f(3),f(4)> given by <1,1,2,1>, <1,2,1,1>, <1,2,2,1>, <1,2,1,2>, <2,2,1,2>, <2,1,2,2>, <2,1,1,2>, and <2,1,2,1>.
|
|
MAPLE
|
seq(seq((n-k)^k-2*binomial(n-1, k)+(n-k), k=3..(n-2)), n=5..15);
|
|
MATHEMATICA
|
nmax = 15; t[n_, k_] := (n-k)^k-2*Binomial[n-1, k]+(n-k); Flatten[ Table[ t[n, k], {n, 5, nmax}, {k, 3, n-2}]](* Jean-François Alcover, Nov 18 2011, after Maple *)
|
|
PROG
|
(Haskell)
a189711 n k = (n - k) ^ k - 2 * a007318 (n - 1) k + n - k
a189711_row n = map (a189711 n) [3..n-2]
a189711_tabl = map a189711_row [5..]
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|