VOOZH about

URL: https://oeis.org/A373182

⇱ A373182 - OEIS

login
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.
2
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).
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
Sequence in context: A086625 A152172 A001677 * A339150 A024422 A186771
KEYWORD
nonn
AUTHOR
Enrique Navarrete, May 27 2024
EXTENSIONS
a(11)-a(24) from Sean A. Irvine, Jun 17 2024
STATUS
approved