login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
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.
FORMULA
T(n,k)=(n-k)^k-2*C(n-1,k)+(n-k).
T(n,3) = A006331(n-4) for n>=5.
T(n+2,n) = A005803(n) for n>=3.
T(2n,n) = A056174(n) for n>=3.
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..]
-- Reinhard Zumkeller, May 16 2014
CROSSREFS
Cf. A007318.
Sequence in context: A368559 A166542 A316967 * A092939 A006610 A227716
KEYWORD
nonn,easy,nice,tabl
AUTHOR
Dennis P. Walsh, Apr 25 2011
STATUS
approved