%I #27 Jun 21 2024 09:34:44
%S 1,2,3,6,12,26,60,144,366,960,2640,7464,21960,66240,206760,660240,
%T 2172240,7298640,25179840,88583040,319097520,1170650880,4387582080,
%U 16728808320,65040796800,256987987200,1033805566080,4222598688000,17536408243200,73886160096000
%N 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.
%C 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.
%C 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).
%F a(n) = Sum_{k>=1} A245963(n,k)*k!.
%F a(n) = ((n-1)*a(n-4) + 2*n*a(n-3) + (n+1)*a(n-2) - 3*a(n-1))/2, n>4.
%e a(4)=6 since the seating arrangements in this case (where _ denotes an empty seat) are:
%e 1 _ 2 _
%e 1 _ _ 2
%e _ 1 _ 2
%e 2 _ 1 _
%e _ 2 _ 1
%e 2 _ _ 1.
%e a(3)=3 by the following seating arrangements (notice the number of people seated is not the same in each case),
%e 1 _ 2
%e _ 1 _
%e 2 _ 1.
%e For n=7, the following are not valid seating arrangements since a fourth person can be seated in both cases:
%e 1 _ 2 _ _ _ 3
%e _ _ 1 _ 3 _ 2.
%Y Cf. A095236, A245963.
%K nonn
%O 1,2
%A _Enrique Navarrete_, May 27 2024
%E a(11)-a(24) from _Sean A. Irvine_, Jun 17 2024