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

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

Author

Jaap Spies, Jan 28 2003

Keywords

• nonn
• easy

Comments

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.

Links

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

Crossrefs

Cf. A079908-A079928.

Programs

Maple

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

Mathematica

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

PARI

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

Formula

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