This site is supported by donations to The OEIS Foundation.



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


%S 1,4,14,36,76,140,234,364,536,756,1030,1364,1764,2236,2786,3420,4144,

%T 4964,5886,6916,8060,9324,10714,12236,13896,15700,17654,19764,22036,

%U 24476,27090,29884,32864,36036,39406,42980,46764,50764,54986,59436

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

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

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

%C 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

%C 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.

%C For fixed g, f(g,n) is polynomial in n for n >= g-2. See reference.

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

%H Lute Kamstra, <a href="http://www.math.leidenuniv.nl/~naw/">Problem 29 in Vol. 5/3, No. 1, Mar 2002, p. 96</a>. See also Vol. 5/3, Nos. 3 and 4.

%H Jaap Spies, <a href="http://www.jaapspies.nl/mathfiles/dancingschool.pdf">Dancing School Problems, Permanent solutions of Problem 29</a>.

%H Jaap Spies, <a href="http://www.jaapspies.nl/oeis/ds.sage">Sage program to compute f(g,h)</a>.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,4,-1).

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

%F G.f.: 1+2*x*(2-x+2*x^2)/(1-x)^4. - _R. J. Mathar_, Nov 19 2007

%t Join[{1},Array[#^3+3*#&,5!,1]] (* _Vladimir Joseph Stephan Orlovsky_, Jan 08 2011 *)

%o (PARI) concat(1,vector(30,n,n^3+3*n)) \\ _Derek Orr_, Jun 18 2015

%Y Cf. A061989, A079909-A079928.

%Y Cf. Essentially the same as A061989.

%K nonn,easy

%O 0,2

%A _Jaap Spies_, Jan 28 2003

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 26 04:11 EDT 2019. Contains 322469 sequences. (Running on oeis4.)