число n-подмножеств {1,2,...,2n-1} с суммой кратной n

[maxal]

Для натурального $n$ найдите количество подмножеств мощности $n$ множества $\{1,2,\dots,2n-1\}$, сумма элементов которых кратна $n$.

[worm2]

Свеженькая

[Руст]

Добавим ещё 0 и получим полный набор остатков при делении на 2n. Выбору остатков $x_1,...,x_n$ сопоставим $x_0=0,x_1,...,x_n$ выбор n+1 элементов, включая 0.
Каждому набору $(x_0,x_1,..,x_n)$ можно сопоставить $f(x_0,x_1,...,x_n)=(x_0+1,x_1+1,...,x_n+1)$ сложение по модулю 2n. Так как f взаимно однозначное отображение увеличивающее сумму остатков при делении на n на 1, то количество всех остатков суммы одинаковы, т.е. с суммой остатков 0 имеется $\frac 1n C_{2n}^{n+1}=\frac 1n C_{2n}^{n-1}$. Но здесь попали и n+1 -ки без нуля с суммой остатков 0. А им соответсвует набор (дополнение) n-1 элементов, включающих 0 и с суммой делящихся на n. Таким образом $N(n)=N(n-1)=\frac 1n C_{2n}^{n-1}-N(n-2)$, где $N(k)$ - количество k подмножеств с суммой делящийся на n. Аналогично если (k+1,n)=1 получается $N(k)+N(k+1)=\frac 1n C_{2n}^{k+1}$.
Соответственно, если n простое получается формула

$$N(n-1)=(-1)^n+\frac 1n \sum_{k=1}^{n-2} (-1)^{k-1}C_{2n}^{n-k}=(-1)^n+\frac 1n[\frac 12 C_{2n}^n+(-1)^{n-1}(2n-1)]=(-1)^{n-1}+\frac 1n (C_{2n-1}^{n-1}+(-1)^n).$$

По всей видимости эта формула верна и не для простых n. Вижу один способ доказательства с помощью подсчёта $N(k,a)$ с суммой остатков а при делении на n из множества $(0,1,...,2n-1)$, но оно не элегантная при не простых n.

[worm2]

То есть, получается, что N(3-1) = 1+$\frac{1}{3}(C_5^2-1)$=4, что ли?
Неправильно, N(2) = 1.

Добавлено спустя 6 минут 49 секунд:

А. понял, это N(3), а не N(2).
Вроде, похоже.

[Руст]

У меня несколько неудачное обозначение. $N(k)$ надо было обозначать $N(n,k)$, Соответствено $N(n,n)=N(n,n-1)=A_n$. Для него получается $A_n=(-1)^{n-1}+\frac 1n(C_{2n-1}^{n-1}+(-1)^n)$. В частности $A_2=-1+\frac 12 (3+1)=1, \ A_3=1+3=4, \ A_4=8,..$

[maxal]

Руст писал(а):

Для него получается $A_n=(-1)^{n-1}+\frac 1n(C_{2n-1}^{n-1}+(-1)^n)$. В частности $A_2=-1+\frac 12 (3+1)=1, \ A_3=1+3=4, \ A_4=8,..$

Эта формула не работает для составных $n$. Например, для $n=4$ правильный ответ 9, а не 8.

[Руст]

Да, ответ получается более сложный.
Рассмотрим количество k элементных наборов $N(l,m,k)$ множества (1,2,...,lm-1) сумма элементов которых делится на m. Обозначим через $M(l,m,k)$ количество k - элементных подмножеств множества (0,1,...,lm-1) с суммой элементов, делящихся на m. Ясно, что $M(l,m,k)=N(l,m,k)+N(l,m,k-1)$ (путём добавления 0 к k-1 элементным подмножествам), т.е. $N(l,m,k)+(-1)^k=M(l,m,k)-M(l,m,k-1)+M(l,m,k-2)-...+(-1)^{k-1}M(l,m,1).$
Можно учесть ещё, что $N(l,m,k)=N(l,m,lm-1-k)$ чтобы фигурировали суммы только с взаимно простыми (m,k).
Если $(m,k)=1$ получаем (путём добавления 1 к каждому элементу и взятия по модулю lm), что $M(l,m,k)=\frac 1m C_{lm}^k$. Это позволяет выразит указанную величину в виде конечной формулы. Однако из-за сложности выражения не хочется с этим возится.

[maxal]

Существует простая формула, дающая ответ на исходный вопрос для всех натуральных $n$.

[Хорхе]

Я бы не назвал формулу, которая у меня получилась, простой.
Примем такое одноразовое обозначение: $s(A) = \sum_{\alpha\in A} \alpha$, такое многоразовое обозначение: $\zeta_k = e^{2\pi k i/n}$ и такое
распространенное обозначение: $[z^n]f(z)$ --- коэффициент при $z^n$ в разложении Маклорена для $f(z)$.

Используем простой факт:

$$ \sum_{k=0}^{n-1} \zeta_k^m = n 1_{m = 0 \pmod n} $$

Тогда количество наборов, что нас интересует, равно

$$ \gathered M_n = \frac1n \sum_{\substack{A\subset\overline{1,2n-1}\\|A|=n}} \sum_{k=0}^{n-1} \zeta_k^{s(A)} =\frac1n [z^n]\sum_{k=0}^{n-1} \sum_{A\subset\overline{1,2n-1}} z^{|A|}\prod_{\alpha\in A} \zeta_k^{\alpha} \\ =\frac1n [z^n]\sum_{k=0}^{n-1} \prod_{\alpha=\mathbf 1}^{2n-1}} (1+z\zeta_k^\alpha) = \frac1n [z^n]\frac1{1+z}\sum_{k=0}^{n-1} \prod_{\alpha=\mathbf 0}^{2n-1}} (1+z\zeta_k^\alpha) = \frac1n [z^n]\frac1{1+z}\sum_{k=0}^{n-1} \left[\prod_{\alpha=0}^{n-1}} (1+z\zeta_k^\alpha)\right]^2 \endgathered $$

Разберемся с произведением в скобках. Если $(k,n) = d$, то около $z$ стоят все корни $n/d$-й степени из 1, причем каждый в точности $d$ раз. Значит,

$$ \prod_{\alpha=0}^{n-1}} (1+z\zeta_k^\alpha) = (1 - (-z)^{n/d})^{d} = \pm (z^{n/d} + (-1)^{n/d-1})^d, $$

знак нам не очень важен, поскольку мы потом в квадрат возведем. Итак, при $(k,n)=d$ (тут $m=n/d$)

$$ \gathered{} [z^n]\frac1{1+z} \left[\prod_{\alpha=0}^{n-1}} (1+z\zeta_k^\alpha)\right]^2 = [z^n]\frac1{1+z} (z^{m} + (-1)^{m-1})^{2d} \\= [z^n] (z^{m} + (-1)^{m-1})^{2d-1}(z^{m-1} - z^{m-2} + \dots + (-1)^{m-1}) = C_{2d-1}^d(-1)^{(m-1)(d-1)}(-1)^{m-1} = C_{2d-1}^d (-1)^{n-d} \endgathered $$

Количество тех $k\in\{0,\dots,n-1\}$, что $(k,n) = d$, равно $\varphi(n/d)$ (я считаю, что $(0,n) = n$), потому

$$ M_n = \frac1n \sum_{d|n} \varphi\Big(\frac nd\Big) C_{2d-1}^d (-1)^{n+d}. $$

Боюсь, что вряд ли именно эту формулу maxal назвал простою. Упростить не получилось. Единственное, что пришло в голову --- написать производящую функцию, потом если поменять порядок суммирования, получается естественным образом ``логарифм Пойа'', но поскольку логарифм этот берется не от производящей функции, а от чего-то с коэффициентами обоих знаков, придумать альтернативное комбинаторное описание не вышло.

[maxal]

Хорхе писал(а):

$$ M_n = \frac1n \sum_{d|n} \varphi\Big(\frac nd\Big) C_{2d-1}^d (-1)^{n+d}. $$

Боюсь, что вряд ли именно эту формулу maxal назвал простою.

Ага, это именно она. Вполне себе простая формулка

Кстати, ее вид наводит на мысль, что должно существовать простое комбинаторное доказательство с использованием обращения Мёбиуса...

[Хорхе]

На самом деле, логарифм Пойа почти выходит. Он выходит для нечетных $n$. Точнее, если записать производящую функцию, заменить $n/d$ на $k$ и поменять порядок суммирования, получим

$$ \mathcal{M} (z) = \sum_{k=1}^{\infty} \frac{\varphi(k)}{k} \sum_{d=1}^\infty \frac1d C_{2d-1}^d (-1)^d (-z)^{kd} = \sum_{k=1}^{\infty} \frac{\varphi(k)}{k} \ln\frac1{1-\mathcal{C}(-(-z)^k)}, $$

где $\mathcal C(z) = \frac12(1-\sqrt{1-4z})$ --- производящая функция смещенных чисел Каталана. Отсюда очевидно, что для нечетных $n$

$$ M_n = [z^n]\mathcal{M} (z) = [z^n]\sum_{k=1}^{\infty} \frac{\varphi(k)}{k} \ln\frac1{1-\mathcal{C}(z^k)}, $$

последнее и есть логарифм Пойа, то есть (обычная) производящая функция (ориентированных) циклов, составленных из объектов, чья (обычная) производящая функция --- $\mathcal{C}$, в данном случае --- из каталановых объектов.

То есть для нечетного $n$ есть еще одно комбинаторное описание --- например, "клумбы" --- ориентированные циклы, составленные из плоских корневых деревьев, у которых $n$ вершин на всех или "бинарные клумбы" --- то же самое, только деревья бинарные, и на всех $n$ листьев.

Мне больше всего нравится скобочная интерпретация --- "кольцевые поездки по МКАДу со сменой водителей".

Есть автобус, который ездит по кольцевой дороге и по пути подсаживает и высаживает пассажиров, включая водителя. Единственное ограничение --- водитель всегда входит первым и выходит последним, то есть автобус без водителя не едет. Ну и считаем по количеству входов. Вот нарисованы "поездки по МКАДу" для трех входов, их, как и должно быть, $M_3 = 4$ (в --- выход=вход водителя, х --- вход пассажира, ы --- выход). Мне лень рисовать кружки, я пишу в линию. Для наглядности упорядочил по количеству водителей ( = количество каталановых объектов в цикле)

1) в х х ы ы
в х ы х ы
2) в х ы в
3) в в в

Хотелось бы иметь какую-нибудь интерпретацию и для четных $n$. Ну и конечно, мне совершенно непонятно, как для нечетных $n$ построить биекцию между такими наборами и каталановыми циклами.