##########################################################################
#  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 A079913(n):
    r"""
    function returns solutions to the Dancing School problem with 8 girls

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

    We use precalculated values for $n = 0, ..., 5$ For $n > 5$ we use
    the polynomial
    $n^8-20*n^7+238*n^6-1820*n^5+9625*n^4-35000*n^3+84448*n^2-122240*n+80680$
    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. 285

    INPUT:
        n -- non negative number

    OUTPUT
        integer

    EXAMPLES:
        sage: A079913(4)
        15458

        sage: A079913(10)
        24553080

        sage: A079913(20)
        10699415080


    AUTHOR:
        - Jaap Spies (2006-12-10)
    """
    b = [1, 9, 221, 2227, 15458, 80196]

    if n >= 0 and n <= 5:
        return b[n]
    else:
        return n^8-20*n^7+238*n^6-1820*n^5+9625*n^4-35000*n^3+84448*n^2-122240*n+80680

def A079913_list(n):
    r"""
    function returns list of solutions to the Dancing School problem with 8 girls

    We use precalculated values for $n = 0, ..., 5$. For $n > 5$ we use the
    polynomial $n^8-20*n^7+238*n^6-1820*n^5+9625*n^4-35000*n^3+84448*n^2-122240*n+80680$    
    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 A079913_list(10)
        [1, 9, 221, 2227, 15458, 80196, 334072, 1173240, 3598120, 9856552, 24553080]

        sage: print A079913_list(1)
        [1, 9]

        sage: print A079913_list(0)
        [1]


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

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

    b = [1, 9, 221, 2227, 15458, 80196]

    if n >= 0 and n <= 5:
        return b[:n+1]
    else:
        pol = h^8-20*h^7+238*h^6-1820*h^5+9625*h^4-35000*h^3+84448*h^2-122240*h+80680 
        a = [pol(i) for i in range(6, n+1)]
        for i in range(6):
            a.insert(i,b[i])
        return a