A079928 -id:A079928 - cp's OEIS frontend

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

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

Offset: 0

Jaap Spies, Jan 28 2003

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.

Michael De Vlieger, Table of n, a(n) for n = 0..10000
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, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
Jaap Spies, Dancing School Problems, Permanent solutions of Problem 29.
Jaap Spies, Sage program to compute f(g,h).
Jaap Spies, A Bit of Math, The Art of Problem Solving, Jaap Spies Publishers (2019).
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A061989, A079909-A079928.

Cf. Essentially the same as A061989.

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

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

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

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

Original entry on oeis.org

1, 5, 26, 90, 246, 566, 1146, 2106, 3590, 5766, 8826, 12986, 18486, 25590, 34586, 45786, 59526, 76166, 96090, 119706, 147446, 179766, 217146, 260090, 309126, 364806, 427706, 498426, 577590, 665846, 763866, 872346, 992006, 1123590

Offset: 0

Jaap Spies, Jan 28 2003

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. See A079908 for more information.

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

Colin Barker, Table of n, a(n) for n = 0..1000
Jaap Spies, Dancing School Problems, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
Jaap Spies, Dancing School Problems, Permanent solutions of Problem 29.
Jaap Spies, Sage program for computing A079909.
Jaap Spies, Sage program for computing the polynomial a(n).
Jaap Spies, A Bit of Math, The Art of Problem Solving, Jaap Spies Publishers (2019).
Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

Cf. A079908-A079928.

Vec(-(x^2+1)*(x^4+10*x^2+1)/(x-1)^5 + O(x^100)) \\ Colin Barker, Jan 04 2015

a(0)=1, a(1)=5, a(n)=n^4 - 2*n^3 + 9*n^2 - 8*n + 6 (n>=2) found by applying theorem 7.2.1 of Brualdi, Ryser: Combinatorial Matrix Theory.
G.f.: -(x^2+1)*(x^4+10*x^2+1) / (x-1)^5. - Colin Barker, Jan 04 2015
E.g.f.: exp(x)*(6 + 10*x^2 + 4*x^3 + x^4) - 5 - x. - Stefano Spezia, Dec 18 2019

More terms from Benoit Cloitre, Jan 29 2003

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

Original entry on oeis.org

1, 6, 46, 212, 738, 2104, 5150, 11196, 22162, 40688, 70254, 115300, 181346, 275112, 404638, 579404, 810450, 1110496, 1494062, 1977588, 2579554, 3320600, 4223646, 5314012, 6619538, 8170704, 10000750, 12145796, 14644962, 17540488, 20877854

Offset: 0

Jaap Spies, Jan 28 2003

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. See A079908 for more information.

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

Colin Barker, Table of n, a(n) for n = 0..1000
Jaap Spies, Dancing School Problems, Permanent solutions of Problem 29, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
Jaap Spies, Sage program for computing A079910.
Jaap Spies, Sage program for computing the polynomial a(n).
Jaap Spies, A Bit of Math, The Art of Problem Solving, Jaap Spies Publishers (2019).
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Cf. A079908-A079928.

[1,6] cat [n^5-5*n^4+25*n^3-55*n^2+80*n-46: n in [2..30]]; // Vincenzo Librandi, Feb 17 2015

CoefficientList[Series[(6 x^7 + 11 x^6 + 20 x^5 + 51 x^4 + 6 x^3 + 25 x^2 + 1) / (x - 1)^6, {x, 0, 30}], x] (* Vincenzo Librandi, Feb 17 2015 *)

Vec((6*x^7+11*x^6+20*x^5+51*x^4+6*x^3+25*x^2+1)/(x-1)^6 + O(x^100)) \\ Colin Barker, Jan 04 2015

a(0)=1, a(1)=6, a(2)=46, a(n) = n^5 - 5*n^4 + 25*n^3 - 55*n^2 + 80*n - 46.
G.f.: (6*x^7 + 11*x^6 + 20*x^5 + 51*x^4 + 6*x^3 + 25*x^2 + 1) / (x-1)^6. - Colin Barker, Jan 04 2015
E.g.f.: 47 + 6*x + exp(x)*(-46 + 46*x + 20*x^3 + 5*x^4 + x^5). - Stefano Spezia, Dec 18 2019

More terms from Benoit Cloitre, Jan 29 2003

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

Original entry on oeis.org

1, 7, 79, 478, 2108, 7364, 21652, 55532, 127604, 268108, 523244, 960212, 1672972, 2788724, 4475108, 6948124, 10480772, 15412412, 22158844, 31223108, 43207004, 58823332, 78908852, 104437964, 136537108, 176499884, 225802892, 286122292

Offset: 0

Jaap Spies, Jan 28 2003

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. See A079908 for more information.

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

Colin Barker, Table of n, a(n) for n = 0..1000
Jaap Spies, Dancing School Problems, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
Jaap Spies, Dancing School Problems, Permanent solutions of Problem 29.
Jaap Spies, Sage program for computing A079911.
Jaap Spies, Sage program for computing the polynomial a(n).
Jaap Spies, A Bit of Math, The Art of Problem Solving, Jaap Spies Publishers (2019).
Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Cf. A079908-A079928.

seq(n^6-9*n^5+60*n^4-225*n^3+555*n^2-774*n+484,n=4..40);

CoefficientList[Series[-(6 x^10 - 29 x^9 + 120 x^8 - 49 x^7 + 267 x^6 + 105 x^5 + 211 x^4 + 37 x^3 + 51 x^2 + 1)/(x - 1)^7, {x, 0, 28}], x] (* Michael De Vlieger, Dec 23 2019 *)
LinearRecurrence[{7,-21,35,-35,21,-7,1},{1,7,79,478,2108,7364,21652,55532,127604,268108,523244},40] (* Harvey P. Dale, Jul 02 2022 *)

Vec(-(6*x^10 -29*x^9 +120*x^8 -49*x^7 +267*x^6 +105*x^5 +211*x^4 +37*x^3 +51*x^2 +1) / (x -1)^7 + O(x^100)) \\ Colin Barker, Jan 04 2015

a(0)=1, a(2)=7, a(3)=79, a(n)=n^6-9*n^5+60*n^4-225*n^3+555*n^3-774*n+484.

G.f.: -(6*x^10 -29*x^9 +120*x^8 -49*x^7 +267*x^6 +105*x^5 +211*x^4 +37*x^3 +51*x^2 +1) / (x -1)^7. - Colin Barker, Jan 04 2015

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

Original entry on oeis.org

1, 8, 133, 1044, 5794, 24720, 86608, 260720, 693552, 1666000, 3675680, 7549488, 14591440, 26770832, 46955760, 79197040, 129067568, 204062160, 314062912, 471875120, 693838800, 1000520848, 1417492880, 1976199792, 2714924080

Offset: 0

Jaap Spies, Jan 28 2003

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. See A079908 for more information.

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

Colin Barker, Table of n, a(n) for n = 0..1000
Jaap Spies, Dancing School Problems, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
Jaap Spies, Dancing School Problems, Permanent solutions of Problem 29.
Jaap Spies, Sage program for computing A079912.
Jaap Spies, Sage program for computing the polynomial a(n).
Jaap Spies, A Bit of Math, The Art of Problem Solving, Jaap Spies Publishers (2019).
Index entries for linear recurrences with constant coefficients, signature (8,-28,56,-70,56,-28,8,-1).

Cf. A079908-A079928.

seq(n^7-14*n^6+126*n^5-700*n^4+2625*n^3-6342*n^2+9072*n-5840,n=5..20);

Join[{1,8,133,1044,5794},Table[n^7-14n^6+126n^5-700n^4+2625n^3- 6342n^2 +9072n-5840,{n,5,30}]] (* Harvey P. Dale, May 03 2011 *)

Vec(-(46*x^12 -340*x^11 +931*x^10 -1808*x^9 +727*x^8 -1400*x^7 -1506*x^6 -656*x^5 -788*x^4 -148*x^3 -97*x^2 -1) / (x -1)^8 + O(x^100)) \\ Colin Barker, Jan 04 2015

a(0) = 1, a(1) = 8, a(2) = 133, a(3) = 1044, a(4) = 5794; for n>4, a(n) = n^7-14*n^6+126*n^5-700*n^4+2625*n^3-6342*n^2+9072*n-5840.

G.f.: -(46*x^12 -340*x^11 +931*x^10 -1808*x^9 +727*x^8 -1400*x^7 -1506*x^6 -656*x^5 -788*x^4 -148*x^3 -97*x^2 -1) / (x -1)^8. - Colin Barker, Jan 04 2015

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 06 2003

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

Original entry on oeis.org

8, 57, 364, 2106, 11196, 55532, 260720, 1173240, 5112544, 21670160, 89700624, 363862092, 1450606028, 5697401802, 22088730348, 84669409935, 321307769052, 1208513572803, 4509661963752, 16709568237540

Offset: 1

Jaap Spies, Jan 28 2003

nonn

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. See A079908 for more information.

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

Cf. A079908-A079928.

Corrected by Jaap Spies, Feb 01 2004

More terms Dec 14 2006

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

Original entry on oeis.org

1, 9, 221, 2227, 15458, 80196, 334072, 1173240, 3598120, 9856552, 24553080, 56423032, 121013800, 244555560, 469343992, 860997880, 1517994792, 2583928360, 4262971000, 6839066232, 10699415080, 16362861352, 24513820920, 36042440440, 52091711272, 74112304680

Offset: 0

Jaap Spies, Jan 28 2003

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. See A079908 for more information.

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

Colin Barker, Table of n, a(n) for n = 0..1000
Jaap Spies, Dancing School Problems, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
Jaap Spies, Dancing School Problems, Permanent solutions of Problem 29.
Jaap Spies, Sage program for computing A079913.
Jaap Spies, Sage program for computing the polynomial a(n).
Jaap Spies, A Bit of Math, The Art of Problem Solving, Jaap Spies Publishers (2019).
Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Cf. A079908-A079928.

A079913 := n->n^8 -20*n^7 +238*n^6 -1820*n^5 +9625*n^4 -35000*n^3 +84448*n^2 -122240*n +80680: (1,9,221,2227,15458,80196, seq(A079913(n), n=6..30)); # edited by Wesley Ivan Hurt, Sep 17 2015

CoefficientList[Series[-(484*x^14 - 3902*x^13 + 13791*x^12 - 25930*x^11 + 32928*x^10 - 15756*x^9 + 14443*x^8 + 8652*x^7 + 8524*x^6 + 3690*x^5 + 2741*x^4 + 478*x^3 + 176*x^2 + 1)/(x - 1)^9, {x, 0, 30}], x] (* Wesley Ivan Hurt, Sep 17 2015 *)

Vec(-(484*x^14 -3902*x^13 +13791*x^12 -25930*x^11 +32928*x^10 -15756*x^9 +14443*x^8 +8652*x^7 +8524*x^6 +3690*x^5 +2741*x^4 +478*x^3 +176*x^2 +1)/(x -1)^9 + O(x^100)) \\ Colin Barker, Jan 05 2015

a(0)=1, a(1)=9, a(2)=221, a(3)=2227, a(4)=15459, a(5)=80196, for n >= 6, a(n)= n^8 -20*n^7 +238*n^6 -1820*n^5 +9625*n^4 -35000*n^3 +84448*n^2 -122240*n +80680.
G.f.: -(484*x^14 -3902*x^13 +13791*x^12 -25930*x^11 +32928*x^10 -15756*x^9 +14443*x^8 +8652*x^7 +8524*x^6 +3690*x^5 +2741*x^4 +478*x^3 +176*x^2 +1) / (x -1)^9. - Colin Barker, Jan 05 2015
a(n) = 9*a(n-1) - 36*a(n-2) + 84*a(n-3) - 126*a(n-4) + 126*a(n-5) - 84*a(n-6) + 36*a(n-7) - 9*a(n-8) + a(n-9), for n>8. - Wesley Ivan Hurt, Sep 17 2015

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

Original entry on oeis.org

1, 10, 364, 4664, 40296, 253072, 1249768, 5112544, 17990600, 56010096, 157175032, 403579328, 959942664, 2136701200, 4488418616, 8961185952, 17105944648, 31378295984, 55549351800, 95256535936, 158727963272, 257719103568

Offset: 0

Jaap Spies, Jan 28 2003

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. See A079908 for more information.

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

Colin Barker, Table of n, a(n) for n = 0..1000
Jaap Spies, Dancing School Problems, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
Jaap Spies, Dancing School Problems, Permanent solutions of Problem 29.
Jaap Spies, Sage program for computing A079914.
Jaap Spies, Sage program for computing the polynomial a(n).
Jaap Spies, A Bit of Math, The Art of Problem Solving, Jaap Spies Publishers (2019).
Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-210,252,-210,120,-45,10,-1).

Cf. A079908-A079928.

f := n->n^9-27*n^8+414*n^7-4158*n^6+29421*n^5-148743*n^4+530796*n^3-1276992*n^2+1866384*n-1255608; seq(f(i),i=7..21);

CoefficientList[Series[-(5840 x^16 - 52960 x^15 + 210480 x^14 - 481464 x^13 + 671100 x^12 - 619882 x^11 + 258311 x^10 - 123144 x^9 - 98197 x^8 - 57276 x^7 - 46818 x^6 - 18160 x^5 - 9046 x^4 - 1354 x^3 - 309 x^2 - 1)/(x - 1)^10, {x, 0, 21}], x] (* Michael De Vlieger, Dec 23 2019 *)

Vec(-(5840*x^16 -52960*x^15 +210480*x^14 -481464*x^13 +671100*x^12 -619882*x^11 +258311*x^10 -123144*x^9 -98197*x^8 -57276*x^7 -46818*x^6 -18160*x^5 -9046*x^4 -1354*x^3 -309*x^2 -1) / (x -1)^10 + O(x^100)) \\ Colin Barker, Jan 05 2015

a(0)=1, a(1)=10, a(2)=364, a(3)=4664, a(4)=40296, a(5)=253072, a(6)=1249768, for n >= 7: a(n)=n^9-27n^8+414n^7-4158n^6+29421n^5-148743n^4+530796n^3-1276992n^2+1866384n-1255608.

G.f.: -(5840*x^16 -52960*x^15 +210480*x^14 -481464*x^13 +671100*x^12 -619882*x^11 +258311*x^10 -123144*x^9 -98197*x^8 -57276*x^7 -46818*x^6 -18160*x^5 -9046*x^4 -1354*x^3 -309*x^2 -1) / (x -1)^10.- Colin Barker, Jan 05 2015

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

Original entry on oeis.org

1, 11, 596, 9627, 103129, 780902, 4557284, 21670160, 87396728, 308055528, 971055240, 2780440664, 7324967640, 17945144328, 41249101928, 89635336440, 185317652664, 366517590440, 696695849928

Offset: 0

Jaap Spies, Jan 28 2003

nonn

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. See A079908 for more information.

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, pp. 283-285.

Jaap Spies, Dancing School Problems, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
Jaap Spies, Dancing School Problems, Permanent solutions of Problem 29.
Jaap Spies, Sage program for computing A079915.
Jaap Spies, Sage program for computing the polynomial a(n).
Jaap Spies, A Bit of Math, The Art of Problem Solving, Jaap Spies Publishers (2019).

Cf. A079908-A079928.

f:= n-> n^10 -35*n^9 +675*n^8 -8610*n^7 +78435*n^6 -523467*n^5 +2562525*n^4 -9008160*n^3 +21623220*n^2 -31840760*n +21750840: seq(f(i), i=8..21);

for n>=8: a(n) = n^10 -35*n^9 +675*n^8 -8610*n^7 +78435*n^6 -523467*n^5 +2562525*n^4 -9008160*n^3 +21623220*n^2 -31840760*n +21750840.

Corrected by Jaap Spies, Feb 01 2004

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

Original entry on oeis.org

1, 14, 2567, 79544, 1596800, 20789082, 196933710, 1450606028, 8719846960, 44321202192, 195717772000, 767025716736, 2713659864832, 8787898861568

Offset: 0

Jaap Spies, Jan 28 2003

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. See A079908 for more information.

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, pp. 283-285.

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

Cf. A079908-A079928.

Corrected by Jaap Spies, Feb 01 2004

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI