Матпраздник прошел, попробуем вернуться к компьютерным развлечениям

сколькими способами число N можно представить в виде суммы?

(разбиения 1+2 и 2+1 и т.п. считаются одинаковыми)

начать эксперименты можно и с примитивного перебора — например, такого:

def partitions(n,l=None):
    # все разбиения числа n
    # (на числа не превосходяшие l)
    if l is None: l=n
    if n==0: yield []
    if n>0:
        for i in range(l,0,-1):
            # рекурсивный перебор по максимальному элементу
            yield from map(lambda partition: [i]+partition,
                           partitions(n-i,i))

(упражнение: внесите минимальное исправление в код, чтобы перечислялись разбиения на различные слагаемые)

можно посмотреть на количества таких разбиений для разных N — на картинке Женя Смирнов с ассистентами использует умный способ это считать — а вот, наоборот, предельно прямолинейный (только всё же заменим рекурсию на динамику, чтобы работало и для относительно больших N):

def count_partitions_upto(N):
    partitions = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for l in range(N+1):
        partitions[0][l] = 1
    for n in range(1,N+1):
        for l in range(1,N+1):
            for i in range(1,l+1):
                partitions[n][l] += partitions[n-i][i]
    return partitions

получаются какие-то числа… что дальше с ними делать? как обсуждалось выше, полезно бывает посмотреть на график — и, так как p(N) быстро растет, лучше смотреть на график log p(N)

картинки (и еще пара слов) в комментариях

дальше мб будет что-то про p(N) по разным модулям