A052567 E.g.f.: (1-x)^2/(1-3*x+x^2).

1, 1, 6, 48, 504, 6600, 103680, 1900080, 39795840, 937681920, 24548832000, 706966444800, 22210346188800, 755916735974400, 27706219904563200, 1088037381150720000, 45576301518139392000, 2028445209752113152000, 95589693062063456256000, 4754884242802394308608000

Offset

0,3

Comments

Number of ways to seat n people on benches, linearly order the benches and choose one person from each bench (see Example). - Enrique Navarrete, Oct 09 2025

Links

Table of n, a(n) for n=0..19.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 509

Formula

E.g.f.: (-1+x)^2/(1-3*x+x^2).

Recurrence: {a(1)=1, a(0)=1, a(2)=6, (n^2+3*n+2)*a(n)+(-6-3*n)*a(n+1)+a(n+2)=0}

Sum(-1/5*(3*_alpha-2)*_alpha^(-1-n), _alpha=RootOf(_Z^2-3*_Z+1))*n!

a(n) = n! * Fibonacci(2*n) for n > 0. - Ilya Gutkovskiy, Jul 17 2021

Example

From Enrique Navarrete, Oct 09 2025: (Start)
For n=5 we have (number of seatings on linearly ordered benches given by A002866 and "/" denoting the split between benches):
  1 bench:   12345 (120 such seatings), 600 ways;
  2 benches: 1234/5 (240 such seatings), 960 ways;
  2 benches: 123/45 (240 such seatings), 1440 ways;
  3 benches: 123/4/5 (360 such seatings), 1080 ways;
  3 benches: 12/34/5 (360 such seatings), 1440 ways;
  4 benches: 12/3/4/5 (480 such seatings), 960 ways;
  5 benches: 1/2/3/4/5 (120 such seatings), 120 ways.
The number of seatings is A002866(5)=1920 and the number of ways is a(5)=6600. (End)

Maple

spec := [S, {S=Sequence(Prod(Z, Sequence(Z), Sequence(Z)))}, labeled]: seq(combstruct[count](spec, size=n), n=0..20);

Mathematica

With[{nn=20}, CoefficientList[Series[(1-x)^2/(1-3x+x^2), {x, 0, nn}], x] Range[0, nn]!] (* Harvey P. Dale, Jul 06 2021 *)

Crossrefs

Cf. A000142, A001906, A005443, A088305.

Sequence in context: A261900 A055861 A053506 * A351340 A368323 A002170

Adjacent sequences: A052564 A052565 A052566 * A052568 A052569 A052570

Keyword

easy,nonn

Author

INRIA Encyclopedia of Combinatorial Structures, Jan 25 2000

Status

approved