# [seqfan] Two Sequences Related To Permutations of (1,2,...,n)

Leroy Quet q1qq2qqq3qqqq at yahoo.com
Sun Jan 18 00:15:57 CET 2009

```(1)

Let a(n) = the number of permutations (p(1),p(2),p(3)...,p(n)) of (1,2,3,...,n) where, if each (m,p(m)) is plotted on a graph, then the entire set P of the n of these plotted points would be on the perimeter of the convex hull of P.

For instance, for n = 5:

(p(1),p(2),p(3),p(4),p(5)) = (1,3,5,2,4) would be included in the count, but
(1,4,3,2,5) would not because point (3,3) is not on the perimeter of the convex hull of P.

First, I am sure there must be a better way to describe this sequence {a(n)}.

Second, is this sequence {a(n)} already in the EIS?

Third, is there a direct way (not a brute-force search) to calculate each a(n)?

---

(2)

Let a(n) = the number of ways to fill the squares of an n-by-n grid such that there are exactly 2 filled squares, no more, no fewer, in each row and in each column of the grid.

Is sequence {a(m)} already in the EIS?

Is there a direct way to calculate each a(n)? It seems to me that it is VERY likely there is indeed a formula for calculating each a(n).

(The reason I say this sequence is related to permutations of (1,2,...,n) is that if instead we wanted exactly ONE filled square in each row and in each column of an n-by-n grid, then the number of ways to do this would be n!, since each way represents a permutation of (1,2,3,...,n), obviously.)

Thanks,
Leroy Quet

```