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

def A079914(n):
    r"""
    function returns solutions to the Dancing School problem with 9 girls

    The value is $per(B)$, the permanent of the (0,1)-matrix $B$
    of size $9 \times n+9$ with $b(i,j)=1$ if and only if $i \le j \le i+n$.

    We use precalculated values for $n = 0, ..., 6$ For $n > 6$ we use
    the polynomial
    $n^9-27n^8+414n^7-4158n^6+29421n^5-148743n^4+530796n^3-1276992n^2+1866384n-1255608$
    calculated with the function dance.

    See http://www.jaapspies.nl/mathfiles/dancing.sage

    See Nieuw Archief voor Wiskunde 5/7 nr. 4 December 2006 p. 283-285

    INPUT:
        n -- non negative number

    OUTPUT
        integer

    EXAMPLES:
        sage: A079914(4)
        40296

        sage: A079914(10)
        157175032

        sage: A079914(20)
        158727963272


    AUTHOR:
        - Jaap Spies (2006-12-10)
    """
    b = [1, 10, 364, 4664, 40296, 253072, 1249768]

    if n >= 0 and n <= 6:
        return b[n]
    else:
        return 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
def A079914_list(n):
    r"""
    function returns list of solutions to the Dancing School problem with 9 girls

    We use precalculated values for $n = 0, ..., 7$. For $n > 7$ we use the
    polynomial

    calculated with the function dance.
    See http://www.jaapspies.nl/mathfiles/dancing.sage

    INPUT:
        n -- non negative number

    OUTPUT
        list of integers

    EXAMPLES:
        sage: print A079914_list(10)
        [1, 10, 364, 4664, 40296, 253072, 1249768, 5112544, 17990600, 56010096, 157175032]

        sage: print A079914_list(1)
        [1, 10]


    AUTHOR:
        - Jaap Spies (2006-12-10)
    """

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

    b = [1, 10, 364, 4664, 40296, 253072, 1249768]
    if n >= 0 and n <= 6:
        return b[:n+1]
    else:
        pol = h^9-27*h^8+414*h^7-4158*h^6+29421*h^5-148743*h^4+530796*h^3-1276992*h^2+1866384*h-1255608
        a = [pol(i) for i in range(7, n+1)]
        for i in range(7):
            a.insert(i,b[i])
        return a