|
%I #43 Dec 03 2021 15:43:27
%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.
%H Michael De Vlieger, <a href="/A079908/b079908.txt">Table of n, a(n) for n = 0..10000</a>
%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.nieuwarchief.nl/serie5/pdf/naw5-2006-07-4-283.pdf">Dancing School Problems</a>, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
%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 Jaap Spies, <a href="http://www.jaapspies.nl/bookb5.pdf">A Bit of Math, The Art of Problem Solving</a>, Jaap Spies Publishers (2019).
%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
|
