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

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

    We use precalculated values for $n = 0, ..., 8$ For $n > 8$ we use
    the polynomial
    $n^10-35*n^9+675*n^8-8610*n^7+78435*n^6-523467*n^5+2562525*n^4-9008160*n^3+21623220*n^2-31840760*n+21750840$
    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: A079915(4)
        103129

        sage: A079915(10)
        971055240

        sage: A079915(20)
        2269918543640


    AUTHOR:
        - Jaap Spies (2006-12-10)
    """
    b = [1, 11, 596, 9627, 103129, 780902, 4557284, 21670160]

    if n >= 0 and n <= 7:
        return b[n]
    else:
        return n^10-35*n^9+675*n^8-8610*n^7+78435*n^6-523467*n^5+2562525*n^4-9008160*n^3+21623220*n^2-31840760*n+21750840

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

    We use precalculated values for $n = 0, ..., 7$. For $n > 7$ we use the polynomial
    $n^10-35*n^9+675*n^8-8610*n^7+78435*n^6-523467*n^5+2562525*n^4-9008160*n^3+21623220*n^2-31840760*n+21750840$
    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 A079915_list(8)
        [1, 11, 596, 9627, 103129, 780902, 4557284, 21670160, 87396728]

        sage: print A079915_list(10)
        [1, 11, 596, 9627, 103129, 780902, 4557284, 21670160, 87396728, 308055528, 971055240]


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

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

    b = [1, 11, 596, 9627, 103129, 780902, 4557284, 21670160]

    if n >= 0 and n <= 7:
        return b[:n+1]
    else:
        pol=h^10-35*h^9+675*h^8-8610*h^7+78435*h^6-523467*h^5+2562525*h^4-9008160*h^3+21623220*h^2-31840760*h+21750840
        a = [pol(i) for i in range(8, n+1)]
        for i in range(8):
            a.insert(i,b[i])
        return a