Представьте себе n слотов с n-1 пробелами между ними.Размещение разделителей k-1 в промежутках между слотами (макс. 1 разделитель на слот) определяет допустимый выбор: поместите первый цвет во все слоты перед первым разделителем, второй цвет в слоты после первого и перед вторым разделителеми т. д. Поскольку между каждыми двумя разделителями имеется хотя бы один пробел, в каждом цвете будет хотя бы один карандаш.
Отображение однозначно, поскольку каждый выбор также генерирует уникальную конфигурацию разделителей..
Помещение разделителей k-1 в n-1 пробелы может быть выполнено N (n-1, k-1) способами, где N - символ Ньютона, поэтому ответом является N (n-1,k-1).
Другой способ представить это, основанный на ответе djna:
Исправить k карандашей, по одному в каждом цвете - вам нужно по крайней мере по одномуцвет, поэтому они будут гарантировать, что это требование выполнено.Теперь у вас осталось nk пиков, которые вы можете разделить между цветами в любом случае, на этот раз не нужно заботиться о выборе каждого цвета (это гарантировано k карандашами, выбранными первыми.) Количество решений - это количество способов, которые вы можете разделитьnk неразличимых карандашей на k различимых (*) разбиений.
Как это перечислить?Добавьте ручки k-1 к вашим карандашам nk, выровняйте их и раскрасьте слева направо, меняя цвет после встречи с карандашом.Например, представление перьев в виде * и карандашей в виде - с тремя цветами (красный, зеленый, синий):
--**-
представляет два красных карандаша, ноль зеленых и один синий.В таком представлении есть (nk) + (k-1) = n-1 элементов (ручки и карандаши). Из них вам нужно выбрать k-1 позиции пера (или nk позиций карандаша, так как выбор одного набора определяетдругой.) Число способов, которыми вы можете сделать это N (n-1, k-1).
(*) Я предполагаю, что «2 красных, один зеленый» отличается от «2 зеленых,один красный ", в противном случае это совершенно другая задача.