n elementos en k cajas, admitiendo cajas vacías

Sea P_0(n, k) el número de formas en las que pueden distribuirse n elementos distinguibles entre k cajas idénticas (pudiendo dejar cajas vacías). Si “ignoramos” la cajas vacías, esto es equivalente a buscar todas las posibles formas de distribuir n elementos distinguibles entre no más de k cajas idénticas:

\displaystyle P_0(n, k) = \sum_{i=1}^k \left\{\begin{matrix} n \\ i \end{matrix}\right\}.

Podemos chequearlo con el siguiente script:

def stirling_2nd(n, k):
    if n == 0 and k == 0:
        return 1
    elif n == 0 or k == 0:
        return 0
    else:
        return stirling_2nd(n - 1, k - 1) + k * stirling_2nd(n - 1, k)
 
def p0_st(n, k):
    return sum(stirling_2nd(n, i) for i in range(1, k + 1))
 
def p0_emp(n, k):
    from itertools import product
    assignments_set = set()
    for slot_assign in product(range(k), repeat=n):
        assignment = [list() for _ in range(k)]
        for ball, slot in enumerate(slot_assign):
            assignment[slot].append(ball)
        assignments_set.add(tuple(sorted(tuple(slot) for slot in assignment)))
    return len(assignments_set)
 
if __name__ == '__main__':
    for i in range(1, 6):
        for j in range(1, 6):
            assert p0_st(i, j) == p0_emp(i, j), (i, j)

One thought on “n elementos en k cajas, admitiendo cajas vacías

  1. […] Contar la cantidad de formas en que pueden distribuirse elementos en cajas es bastante simple, una vez que descubrimos el truco de pensarlo como asignarle un número de caja a cada elemento. Claramente esto nos da posibles formas. Si ignoramos el “etiquetado” de las cajas, claramente esto nos deja formas. [Nota 22/7/13: este análisis es incorrecto, como indica Jon abajo. El análisis correcto de este se encuentra en una nueva página.] […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s