Композиция числа

В теории чисел композицией, или разложением, натурального числа называется его представление в виде упорядоченной суммы натуральных слагаемых. Слагаемые, входящие в композицию, называют частями, а их количество — длиной композиции.

В отличие от композиции, разбиение числа не учитывает порядок следования частей. Поэтому число разбиений числа никогда не превосходит числа композиций.

При фиксированной длине композиций в них иногда также допускают нулевые части.

ПримерыПравить

Существует 16 композиций числа 5:

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

Количество композицийПравить

В общем случае существует   композиций числа n, из которых в точности   имеют длину k.

Если в композициях числа n длины k разрешить нулевые части, то количество таких композиций будет равно  , поскольку прибавление 1 к каждой части даёт композицию числа n + k уже без нулевых частей. Вопрос об общем количестве композиций числа n с возможными нулевыми частями лишён смысла, так как оно бесконечно.

Пример кода на JavaПравить

    private ArrayList<ArrayList<Integer>> getCompositions(int n) {
        ArrayList<ArrayList<Integer>> listOfCompositions = new ArrayList<>();
        ArrayList<Integer> composition = new ArrayList<>();
        composition.add(n);
        while (composition != null) {
            listOfCompositions.add(composition);
            composition = getComposition(composition, n);
        }
        return listOfCompositions;
    }

    private static ArrayList<Integer> getComposition(ArrayList<Integer> previousComposition, int n) {
        ArrayList<Integer> currentComposition = new ArrayList<>(previousComposition);
        for (int i = currentComposition.size() - 1; i >= 0; i--) {
            if (currentComposition.get(i) != 1) {
                currentComposition.set(i, currentComposition.get(i) - 1);
                if (currentComposition.size() > i + 1) {
                    if (((currentComposition.size() - (i + 1)) > 1)) {
                        int sumOfOnes = 0;
                        for (int j = currentComposition.size() - 1; j >= i + 1; j--) {
                            sumOfOnes += currentComposition.get(j);
                            if (j != i + 1) currentComposition.remove(j);
                        }
                        currentComposition.set(i + 1, sumOfOnes + 1);
                    } else currentComposition.set(i + 1, currentComposition.get(i + 1) + 1);
                } else currentComposition.add(1);
                return currentComposition;
            }
        }
        return null;
    }

См. такжеПравить

ЛитератураПравить

  • Сачков В. Н. Комбинаторные методы дискретной математики. — М.: Наука, 1977. — С. 241. — 319 с.