OFFSET
1,8
COMMENTS
Triangle of coefficients of the polynomial f(n, h), introduced in A079908 in the context of the "Dancing School" problem.
The problem is inspired by a classic dancing school setting. Imagine a row of n girls facing a row of n+h boys on the dance floor. The girls engage a partner from the opposite line based on height: a girl (number i) chooses a boy (number j) who is at least her own height but not more than h units taller.
This situation is modeled by the n X (n+h) band matrix A where A(i,j) = 1 if and only if i <= j <= i+h, and 0 otherwise.
The polynomial f(n, h) corresponds to the permanent of this matrix, counting the total number of valid complete matchings between the girls and the boys.
Equivalently this corresponds to the number of ways to place n non-attacking rooks on the allowed cells of an n X (n+h) board.
For fixed n, the function f(n, h) is a polynomial in h of degree n (valid for h >= n-2).
The table lists the coefficients of f(n, h) in descending powers of h (from h^n down to h^0).
T(n, k) is the coefficient of h^(n-k) in the polynomial f(n, h).
The algorithm used for this sequence demonstrates a reduction in computational complexity for this class of permanents. While fast general permanent computation is of order O(n2^n), this specific band structure allows for an O(n^4) algorithm (the "Stirling-Glue" method), reducing the problem from exponential to polynomial time.
This allows exact computation of polynomials for n=50 and beyond, which was previously intractable using standard Ryser expansion or even with Butera-Pernici in SageMath.
In 2024 it took 18 minutes to calculate f(24, h) on a 24-core computer. Now it takes only 1.1627 sec to calculate f(50, h).
REFERENCES
Jaap Spies, A Bit of Math, The Art of Problem Solving, Spies Publishers ISBN: 9789402171914 (2025), Chapter 32, for a history of The Dancing School Problems.
LINKS
Jaap Spies, Dancing School Problems, Nieuw Archief voor Wiskunde 5/7 nr. 4, Dec 2006, pp. 283-285.
EXAMPLE
The triangle T(n, k) begins:
n\k 0 1 2 3 4 5 6 ...
1: 1 1
2: 1 1 1
3: 1 0 3 0
4: 1 -2 9 -8 6
5: 1 -5 25 -55 80 -46
6: 1 -9 60 -225 555 -774 484
...
T(4,2)=9 because f(4,h) = h^4 - 2*h^3 + 9*h^2 - 8*h + 6
PROG
(SageMath)
def A_new_row(m):
# Computes the coefficient row for dimension m using Stirling-Glue algorithm
# Returns coefficients for h^m down to h^0
total_rv = [0] * (m + 1)
# Iterate target number of rooks in Right Corner (N_R)
for N_R in range(m):
dp = {(0, 0): 1} # State: (k_L, k_R) -> count
for i in range(m):
new_dp = {}
for (kL, kR), ways in dp.items():
# 1. Skip row
new_dp[(kL, kR)] = new_dp.get((kL, kR), 0) + ways
# 2. Place in Left (L) - Stirling structure
if i >= 1:
factor_L = i - kL
if factor_L > 0:
st = (kL + 1, kR)
new_dp[st] = new_dp.get(st, 0) + ways * factor_L
# 3. Place in Right (R) - Stirling structure
if i <= m - 2 and kR < N_R:
factor_R = (m - 1 - i) - (N_R - 1 - kR)
if factor_R > 0:
st = (kL, kR + 1)
new_dp[st] = new_dp.get(st, 0) + ways * factor_R
dp = new_dp
for (kL, kR), ways in dp.items():
if kR == N_R:
total_rv[kL + kR] += ways
# Convert rook vector to polynomial coefficients (Brualdi-Ryser)
# Implementation of expansion logic omitted for brevity, results in:
# f(m, h) = sum_{k=0}^m (-1)^k * total_rv[k] * falling_factorial(m+h-k, m-k)
# returns list of coefficients
CROSSREFS
KEYWORD
sign,tabf
AUTHOR
Jaap Spies, Jan 14 2026
STATUS
approved