login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A079908 Solution to the Dancing School Problem with 3 girls and n+3 boys: f(3,n). 32
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+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.

REFERENCES

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

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*(2-x+2*x^2)/(1-x)^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, A079909-A079928.

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified March 24 22:17 EDT 2017. Contains 284035 sequences.