0,2

The Dancing School Problem: a line of g girls (g>0) with integer heights ranging from m to m+g-1 cm and a line of g+h boys (h>=0) ranging in height from m to m+g+h-1 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 non-attacking 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 >= g-2. See reference.

Jaap Spies, Dancing School Problems, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, p. 283-285.

Index entries for sequences related to linear recurrences with constant coefficients

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

a(n) = max(1, n^3 + 3*n), found by elementary counting.

G.f.: 1+2*x*(2-x+2*x^2)/(-1+x)^4 . - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Nov 19 2007

Cf. A061989, A079909-A079928.

Cf. Essentially the same as A061989.

Sequence in context: A063258 A011852 A061989 this_sequence A038164 A034528 A128758

Adjacent sequences: A079905 A079906 A079907 this_sequence A079909 A079910 A079911

nonn,easy

Jaap Spies (j.spies(AT)hccnet.nl), Jan 28 2003

More terms from Benoit Cloitre (benoit7848c(AT)orange.fr), Jan 29 2003