A245963 -id:A245963 - cp's OEIS frontend

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

Enrique Navarrete, May 27 2024

nonn

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

			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.

Cf. A095236, A245963.

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.

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

A245964 Triangle read by rows: T(n,k) is the number of maximal hypercubes Q(p) in the Lucas cube Lambda(n) (i.e., Q(p) is an induced subgraph of Lambda(n) that is not a subgraph of a subgraph of Lambda(n) that is isomorphic to the hypercube Q(p+1)).

Original entry on oeis.org

1, 1, 0, 2, 0, 3, 0, 0, 2, 0, 0, 5, 0, 0, 3, 2, 0, 0, 0, 7, 0, 0, 0, 8, 2, 0, 0, 0, 3, 9, 0, 0, 0, 0, 15, 2, 0, 0, 0, 0, 11, 11, 0, 0, 0, 0, 3, 24, 2, 0, 0, 0, 0, 0, 26, 13, 0, 0, 0, 0, 0, 14, 35, 2, 0, 0, 0, 0, 0, 3, 50, 15, 0, 0, 0, 0, 0, 0, 40, 48, 2, 0, 0, 0, 0, 0, 0, 17, 85, 17

Offset: 0

Emeric Deutsch, Aug 13 2014

Row n contains 1 + floor(n/2) entries.

Sum of entries in row n = A001608(n) (n>=2) (the Perrin sequence).

			Row 4 is 0,0,2. Indeed, the Lucas cube Lambda(4) is the graph <><> obtained by identifying a vertex of a square with a vertex of another square; each square is a maximal Q(2).
Triangle starts:
  1;
  1;
  0, 2;
  0, 3;
  0, 0, 2;
  0, 0, 5;
  0, 0, 3, 2;
  0, 0, 0, 7;
  0, 0, 0, 8, 2;

S. Klavzar, Structure of Fibonacci cubes: a survey, J. Comb. Optim., 25, 2013, 505-522.
M. Mollard, Maximal hypercubes in Fibonacci and Lucas cubes, arXiv:1201.1494 [math.CO], 2012.
M. Mollard, Maximal hypercubes in Fibonacci and Lucas cubes, Discrete Appl. Math., 160, 2012, 2479-2483.

Cf. A001608, A245963.

T := proc (n, k) if n = 0 and k = 0 then 1 elif n = 1 and k = 0 then 1 elif k = 0 then 0 else n*binomial(k, n-2*k)/k end if end proc: for n from 0 to 20 do seq(T(n, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form

T[0|1, 0] = 1; T[, 0] = 0; T[n, k_] := (n/k)*Binomial[k, n - 2k];
Table[T[n, k], {n, 0, 20}, {k, 0, n/2}] // Flatten (* Jean-François Alcover, Dec 01 2017 *)

T(n,k) = (n/k)*binomial(k,n-2k) (k>=1).

G.f.: (1+z+t*z^2+t*z^3-t*z^4)/(1-t*(1+z)*z^2).

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A245964 Triangle read by rows: T(n,k) is the number of maximal hypercubes Q(p) in the Lucas cube Lambda(n) (i.e., Q(p) is an induced subgraph of Lambda(n) that is not a subgraph of a subgraph of Lambda(n) that is isomorphic to the hypercube Q(p+1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula