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

Author

Enrique Navarrete, May 27 2024

Keywords

• nonn

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).

Examples

			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.

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.

Extensions

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