

A079908


Solution to the Dancing School Problem with 3 girls and n+3 boys: f(3,n).


33



1, 4, 14, 36, 76, 140, 234, 364, 536, 756, 1030, 1364, 1764, 2236, 2786, 3420, 4144, 4964, 5886, 6916, 8060, 9324, 10714, 12236, 13896, 15700, 17654, 19764, 22036, 24476, 27090, 29884, 32864, 36036, 39406, 42980, 46764, 50764, 54986, 59436
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

The Dancing School Problem: a line of g girls (g>0) with integer heights ranging from m to m+g1 cm and a line of g+h boys (h>=0) ranging in height from m to m+g+h1 cm are facing each other in a dancing school (m is the minimal height of both girls and boys).
A girl of height l can choose a boy of her own height or taller with a maximum of l+h cm. We call the number of possible matchings f(g,h).
This problem is equivalent to a rooks problem: The number of possible placings of g nonattacking rooks on a g X g+h chessboard with the restriction i <= j <= i+h for the placement of a rook on square (i,j): f(g,h) = per(B), the permanent of the corresponding (0,1)matrix B, b(i, j)=1 if and only if i <= j <= i+h
f(g,h) = per(B), the permanent of the (0,1)matrix B of size g X g+h with b(i,j)=1 if and only if i <= j <= i+h.
For fixed g, f(g,n) is polynomial in n for n >= g2. See reference.


REFERENCES

Jaap Spies, Dancing School Problems, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283285.


LINKS

Table of n, a(n) for n=0..39.
Lute Kamstra, Problem 29 in Vol. 5/3, No. 1, Mar 2002, p. 96. See also Vol. 5/3, Nos. 3 and 4.
Jaap Spies, Dancing School Problems, Permanent solutions of Problem 29.
Jaap Spies, Sage program to compute f(g,h).
Index entries for linear recurrences with constant coefficients, signature (4,6,4,1).


FORMULA

a(n) = max(1, n^3 + 3*n), found by elementary counting.
G.f.: 1+2*x*(2x+2*x^2)/(1x)^4.  R. J. Mathar, Nov 19 2007


MATHEMATICA

Join[{1}, Array[#^3+3*#&, 5!, 1]] (* Vladimir Joseph Stephan Orlovsky, Jan 08 2011 *)


PROG

(PARI) concat(1, vector(30, n, n^3+3*n)) \\ Derek Orr, Jun 18 2015


CROSSREFS

Cf. A061989, A079909A079928.
Cf. Essentially the same as A061989.
Sequence in context: A177110 A213045 A061989 * A038164 A193522 A187091
Adjacent sequences: A079905 A079906 A079907 * A079909 A079910 A079911


KEYWORD

nonn,easy


AUTHOR

Jaap Spies, Jan 28 2003


STATUS

approved



