login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

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: A300016 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 21 22:12 EDT 2019. Contains 322328 sequences. (Running on oeis4.)