A189711 Number of non-monotonic functions from [k] to [n-k].

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.

Links

Reinhard Zumkeller, Rows n=5..100 of triangle, flattened

Dennis Walsh, Notes on finite monotonic and non-monotonic functions

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

Adjacent sequences: A189708 A189709 A189710 * A189712 A189713 A189714

Keyword

nonn,easy,nice,tabl

Author

Dennis P. Walsh, Apr 25 2011

Status

approved