Sottoinsiemi con somma un multiplo di \(n\).

[3m0o]

Siano \(n, m \) due interi positivi tale che \(m \equiv 0 \mod n \).
Dire qual è il numero di sottoinsiemi \( A \subseteq \{1,2,\ldots,m\} \) tale che possiedono la proprietà seguente
\[ \left( \sum_{a \in A} a \right) \equiv 0 \mod n \]

[dan952]

Qualche idea...

Sia $q: \mathbb{N}^{\ast} \mapsto \mathbb{N}^{\ast}$ la funzione partizione degli interni positivi a parti distinte, per ogni $n \in \mathbb{N}^{\ast}$ si ha

$$q(n)=\sum_{k=1}^{[\frac{n+1}{2}]} q(k)$$

dove $[•]$ denota la parte intera inferiore, questa uguaglianza è giustificata dal fatto che ci sono $q(k)$ sottoinsiemi contenenti il numero $n-k$ tali che la somma dei loro elementi è $n$.

Detto questo dobbiamo calcolare la somma

$$\sum_{a=1}^{\frac{m}{n}} q(an) =\sum_{a=1}^{\frac{m}{n}}\sum_{k=1}^{[\frac{an+1}{2}]} q(k)$$

[3m0o]

Non so se riesci così (davvero non lo so)
se vuoi un hint

Pensa a
\[ (x+1)(x+1)^2\ldots(x+1)^m = \sum_{k=1}^{m(m+1)/2} a_k x^k \].

[dan952]

Sei sicuro che le potenze stanno fuori le parentesi?

[3m0o]

Si hai ragione è un typo che ho fatto sta sulle \(x\) l'esponente, e \(k\) parte da 0 ovviamente, scusa l'ora tardi mi ha fatto scrivere sbagliato.

[dan952]

Come immaginavo...

Infatti quella che hai scritto tu è proprio la troncata della generatrice della funzione di partizioni a parti distinte

[3m0o]

Ulteriori Hint:

\[ f(x)=(x+1)(x^2+1)\ldots(x^m+1) = \sum_{k=0}^{m(m+1)/2} a_kx^k \]
a noi interessa
\[ \sum_{\substack{ k \geq 0 \\ 0 \leq nk \leq m(m+1)/2 } } a_{nk} \]
per trovare quanto vale questa somma è sufficiente valutare il polinomio nelle potenze di una radice \(n\)-esime dell'unità. Indichiamo con \( \zeta_n \) una radice \(n\)-esima e primitiva dell'unità.

Dimostrare:
\[ \sum_{\substack{ k \geq 0 \\ 0 \leq nk \leq m(m+1)/2 } } a_{nk} = \frac{1}{n} \sum_{k=0}^{n-1} f(\zeta_n^k) \]

Dimostrare il Claim 1
Claim 1: Se \(2 \nmid d \) e \( d \mid n \) allora \( f(\zeta_d) = 2^{m/d} \) e \( f(\zeta_d)=0 \) se \(2 \mid d \).

E dedurre quindi che
\[ \frac{1}{n} \sum_{k=0}^{n-1} f(\zeta_n^k) = \frac{1}{n}\sum_{ \substack{d \mid n \\ 2 \nmid d}} \varphi(d)2^{m/d} \]
Dove \( \varphi \) è la funzione toziente di Euler.

[dan952]

Dimostriamo che

$\sum_{i \geq 0,\ 0\leq ni \leq \frac{m(m+1)}{2}} a_{ni}=\frac{1}{n}\sum_{k=0}^{n-1} f(\zeta_n^k)$

infatti

$\sum_{k=0}^{n-1} f(\zeta_n^k)=\sum_{k=0}^{n-1} \sum_{j=0}^{m(m+1)/2} a_j\zeta_n^{jk}=\sum_{j=0}^{m(m+1)/2} a_j(1+\zeta_n^{j}+\zeta_n^{2j}+ \cdots + \zeta_n^{(n-1)j})$

Se $n$ non divide $j$ allora $1+\zeta_n^{j}+\zeta_n^{2j}+ \cdots + \zeta_n^{(n-1)j}=0$ poiché $\zeta_n^{j} \ne 1$ e $(\zeta_n^{j})^n-1=0$.

Se $n|j$ allora $1+\zeta_n^{j}+\zeta_n^{2j}+ \cdots + \zeta_n^{(n-1)j}=1+1+ \cdots +1=n$

Ora dimostriamo che se $2$ non divide $d$ e $d|n$ allora $f(\zeta_d)=2^(m/d)$ e se $2$ divide $d$ allora $f(\zeta_d)=0$.

$f(\zeta_d)=(\zeta_d+1)(\zeta_d^2+1) \cdots (\zeta_d^m+1)=$

$=2^(m/d) \prod_{k=1}^{m/d} \prod_{i=1}^{kd-1}(\zeta_d^i+1)=2^{m/d} \prod_{k=1}^{m/d}(-1)^{d-1} \Phi_d(-1)$

Dove $\Phi_d(x)=1+x+x^2+\cdots+x^{d-1}$ e

$\Phi_d(-1)={( 0\ se\ 2|d ),( 1\ \text{altrimenti} ):} $

Da qui si deduce che $f(\zeta_d^l)=2^{m/d}$ se $(l,d)=1$ e $2 \not | d$ inoltre si ha

$\sum_{k=0}^{n-1} f(\zeta_n^k)=\sum_{d|n}\sum_{1\leq h \leq n,\ (h,n)=d}f(\zeta_n^h)$

sia $h=dl$ segue che
$\sum_{d|n}\sum_{1 \leq l \leq \frac{n}{d}, \ (l,n/d)=1}f(\zeta_{\frac{n}{d}}^l)=\sum_{d|n,\ 2 \not | d} \psi(n/d)2^{\frac{m}{n/d}}=\sum_{d|n, 2\not | d}\psi(d)2^{m/d}$

[3m0o]