##########################################################################
#  Copyright (C) 2006 Jaap Spies ,jaapspies@gmail.com
#
#  Distributed under the terms of the GNU General Public License (GPL):
#
#                  http://www.gnu.org/licenses/
##########################################################################

"""
        Usage from sage

        sage: attach 'dancing.sage'

        sage: dance(4)
        h^4 - 2*h^3 + 9*h^2 - 8*h + 6
        
"""

# use variable 'h' in the polynomial ring over the rationals

h = QQ['h'].gen()

def dance(m):
    """
        Generates the polynomial solutions of the Dancing School Problem
        Based on a modification of theorem 7.2.1 from Brualdi and Ryser,
        Combinatorial Matrix Theory

        INPUT: integer m 

        OUTPUT: polynomial in 'h'

        EXAMPLE:
            sage: dance(4)
            h^4 - 2*h^3 + 9*h^2 - 8*h + 6

        AUTHOR: Jaap Spies (2006)
    """    
    n = 2*m-2
    M = MatrixSpace(QQ, m, n)
    A = M([0 for i in range(m*n)])
    for i in range(m):
        for j in range(n):
            if i > j or j > i + n - m:
                A[i,j] = 1
    rv = A.rook_vector()
    s = sum([(-1)^k*rv[k]*falling_factorial(m+h-k, m-k) for k in range(m+1)])
    return s