Spaces:
Sleeping
Sleeping
File size: 5,073 Bytes
6a86ad5 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 |
from sympy.utilities.misc import as_int
def binomial_coefficients(n):
"""Return a dictionary containing pairs :math:`{(k1,k2) : C_kn}` where
:math:`C_kn` are binomial coefficients and :math:`n=k1+k2`.
Examples
========
>>> from sympy.ntheory import binomial_coefficients
>>> binomial_coefficients(9)
{(0, 9): 1, (1, 8): 9, (2, 7): 36, (3, 6): 84,
(4, 5): 126, (5, 4): 126, (6, 3): 84, (7, 2): 36, (8, 1): 9, (9, 0): 1}
See Also
========
binomial_coefficients_list, multinomial_coefficients
"""
n = as_int(n)
d = {(0, n): 1, (n, 0): 1}
a = 1
for k in range(1, n//2 + 1):
a = (a * (n - k + 1))//k
d[k, n - k] = d[n - k, k] = a
return d
def binomial_coefficients_list(n):
""" Return a list of binomial coefficients as rows of the Pascal's
triangle.
Examples
========
>>> from sympy.ntheory import binomial_coefficients_list
>>> binomial_coefficients_list(9)
[1, 9, 36, 84, 126, 126, 84, 36, 9, 1]
See Also
========
binomial_coefficients, multinomial_coefficients
"""
n = as_int(n)
d = [1] * (n + 1)
a = 1
for k in range(1, n//2 + 1):
a = (a * (n - k + 1))//k
d[k] = d[n - k] = a
return d
def multinomial_coefficients(m, n):
r"""Return a dictionary containing pairs ``{(k1,k2,..,km) : C_kn}``
where ``C_kn`` are multinomial coefficients such that
``n=k1+k2+..+km``.
Examples
========
>>> from sympy.ntheory import multinomial_coefficients
>>> multinomial_coefficients(2, 5) # indirect doctest
{(0, 5): 1, (1, 4): 5, (2, 3): 10, (3, 2): 10, (4, 1): 5, (5, 0): 1}
Notes
=====
The algorithm is based on the following result:
.. math::
\binom{n}{k_1, \ldots, k_m} =
\frac{k_1 + 1}{n - k_1} \sum_{i=2}^m \binom{n}{k_1 + 1, \ldots, k_i - 1, \ldots}
Code contributed to Sage by Yann Laigle-Chapuy, copied with permission
of the author.
See Also
========
binomial_coefficients_list, binomial_coefficients
"""
m = as_int(m)
n = as_int(n)
if not m:
if n:
return {}
return {(): 1}
if m == 2:
return binomial_coefficients(n)
if m >= 2*n and n > 1:
return dict(multinomial_coefficients_iterator(m, n))
t = [n] + [0] * (m - 1)
r = {tuple(t): 1}
if n:
j = 0 # j will be the leftmost nonzero position
else:
j = m
# enumerate tuples in co-lex order
while j < m - 1:
# compute next tuple
tj = t[j]
if j:
t[j] = 0
t[0] = tj
if tj > 1:
t[j + 1] += 1
j = 0
start = 1
v = 0
else:
j += 1
start = j + 1
v = r[tuple(t)]
t[j] += 1
# compute the value
# NB: the initialization of v was done above
for k in range(start, m):
if t[k]:
t[k] -= 1
v += r[tuple(t)]
t[k] += 1
t[0] -= 1
r[tuple(t)] = (v * tj) // (n - t[0])
return r
def multinomial_coefficients_iterator(m, n, _tuple=tuple):
"""multinomial coefficient iterator
This routine has been optimized for `m` large with respect to `n` by taking
advantage of the fact that when the monomial tuples `t` are stripped of
zeros, their coefficient is the same as that of the monomial tuples from
``multinomial_coefficients(n, n)``. Therefore, the latter coefficients are
precomputed to save memory and time.
>>> from sympy.ntheory.multinomial import multinomial_coefficients
>>> m53, m33 = multinomial_coefficients(5,3), multinomial_coefficients(3,3)
>>> m53[(0,0,0,1,2)] == m53[(0,0,1,0,2)] == m53[(1,0,2,0,0)] == m33[(0,1,2)]
True
Examples
========
>>> from sympy.ntheory.multinomial import multinomial_coefficients_iterator
>>> it = multinomial_coefficients_iterator(20,3)
>>> next(it)
((3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0), 1)
"""
m = as_int(m)
n = as_int(n)
if m < 2*n or n == 1:
mc = multinomial_coefficients(m, n)
yield from mc.items()
else:
mc = multinomial_coefficients(n, n)
mc1 = {}
for k, v in mc.items():
mc1[_tuple(filter(None, k))] = v
mc = mc1
t = [n] + [0] * (m - 1)
t1 = _tuple(t)
b = _tuple(filter(None, t1))
yield (t1, mc[b])
if n:
j = 0 # j will be the leftmost nonzero position
else:
j = m
# enumerate tuples in co-lex order
while j < m - 1:
# compute next tuple
tj = t[j]
if j:
t[j] = 0
t[0] = tj
if tj > 1:
t[j + 1] += 1
j = 0
else:
j += 1
t[j] += 1
t[0] -= 1
t1 = _tuple(t)
b = _tuple(filter(None, t1))
yield (t1, mc[b])
|