Количество комбинаций с C -парой из N элементов - PullRequest
Новая
       139

Количество комбинаций с C -парой из N элементов

1 голос
/ 07 апреля 2020

У меня есть N ведер. Каждое ведро может содержать 0 или 1. C - это число, представляющее, сколько цифр 1 отображается непрерывно (например, если C = 3, то у меня будет 111).

Например, для N = 5 и C = 2, общее количество всех комбинаций составляет 19 (здесь C = 2, поэтому у меня всегда должно быть как минимум две из них - 11 в строке):

enter image description here

И это расчет для первых 20 N и C чисел (я пометил желтый регистр выше):

enter image description here

Как добраться до формулы, которая зависит от C и N?

1 Ответ

0 голосов
/ 22 апреля 2020

Эта python программа 

import scipy.special
import fractions
def bi(n, m):
    return scipy.special.comb(n, m, exact=True)
def fr(*args):
    return fractions.Fraction(*args)
def f(N, k):
    N = fr(N)
    k = fr(k)
    s = 1
    m = 0
    while m <= k - 1:
        if m % k == N % k:
            x = (N - m)/k
            s -= bi(m, x) * (-1)**x * 2**(-(k + 1)*x)
        m += 1
    while m <= N:
        if m % k == N % k:
            x = (N - m)/k
            s -= (bi(m, x) - fr(1, 2)**k * bi(m - k, x) ) * (-1)**x * 2**(-(k + 1)*x)
        m += 1
    return(s * 2**N)
for N in range(1, 20):
    for C in range(1, N + 1):
        print("%6.d" % f(N, C), end = ' ')
    print()

Выходы: 

     1 
     3      1 
     7      3      1 
    15      8      3      1 
    31     19      8      3      1 
    63     43     20      8      3      1 
   127     94     47     20      8      3      1 
   255    201    107     48     20      8      3      1 
   511    423    238    111     48     20      8      3      1 
  1023    880    520    251    112     48     20      8      3      1 
  2047   1815   1121    558    255    112     48     20      8      3      1 
  4095   3719   2391   1224    571    256    112     48     20      8      3      1 
  8191   7582   5056   2656   1262    575    256    112     48     20      8      3      1 
 16383  15397  10616   5713   2760   1275    576    256    112     48     20      8      3      1 
 32767  31171  22159  12199   5984   2798   1279    576    256    112     48     20      8      3      1 
 65535  62952  46023  25888  12880   6088   2811   1280    576    256    112     48     20      8      3      1 
131071 126891  95182  54648  27553  13152   6126   2815   1280    576    256    112     48     20      8      3      1 
262143 255379 196132 114832  58631  28240  13256   6139   2816   1280    576    256    112     48     20      8      3      1 
524287 513342 402873 240335 124192  60320  28512  13294   6143   2816   1280    576    256    112     48     20      8      3      1

Формула от Маркус Шойер .

...