A373182 Number of ways that people can sit in n linearly arranged seats such that there are one or two empty seats between any two persons, zero or one empty seats at the start and end, and at least one person gets seated.

1, 2, 3, 6, 12, 26, 60, 144, 366, 960, 2640, 7464, 21960, 66240, 206760, 660240, 2172240, 7298640, 25179840, 88583040, 319097520, 1170650880, 4387582080, 16728808320, 65040796800, 256987987200, 1033805566080, 4222598688000, 17536408243200, 73886160096000

Offset

1,2

Comments

These occupied seats are an independent dominating set in the path graph of n vertices, and here also with an ordering of which person takes which seat.

a(n-2), n>2 counts the case where the first person who sits takes the leftmost seat (since that leaves all ways to fill the remaining n-2 seats).

Links

Table of n, a(n) for n=1..30.

Formula

a(n) = Sum_{k>=1} A245963(n,k)*k!.

a(n) = ((n-1)*a(n-4) + 2*n*a(n-3) + (n+1)*a(n-2) - 3*a(n-1))/2, n>4.

Example

a(4)=6 since the seating arrangements in this case (where _ denotes an empty seat) are:
   1 _ 2 _
   1 _ _ 2
   _ 1 _ 2
   2 _ 1 _
   _ 2 _ 1
   2 _ _ 1.
a(3)=3 by the following seating arrangements (notice the number of people seated is not the same in each case),
   1 _ 2
   _ 1 _
   2 _ 1.
For n=7, the following are not valid seating arrangements since a fourth person can be seated in both cases:
   1 _ 2 _ _ _ 3
   _ _ 1 _ 3 _ 2.

Crossrefs

Cf. A095236, A245963.

Sequence in context: A086625 A152172 A001677 * A339150 A024422 A186771

Adjacent sequences: A373179 A373180 A373181 * A373183 A373184 A373185

Keyword

nonn

Author

Enrique Navarrete, May 27 2024

Extensions

a(11)-a(24) from Sean A. Irvine, Jun 17 2024

Status

approved