Numero di sottoinsiemi di ordine due e somma limitata
Ho creato un piccolo esercizio 
Siano $n,k$ naturali e $3 \le k \le n$.
Esprimere in forma chiusa il numero di sottoinsiemi $S \subseteq {1,2,\cdots,n}$
di cardinalita' due e aventi somma degli elementi non maggiore di $k$, $a+b \le k$ se $S={a,b}$.
Siano $n,k$ naturali e $3 \le k \le n$.
Esprimere in forma chiusa il numero di sottoinsiemi $S \subseteq {1,2,\cdots,n}$
di cardinalita' due e aventi somma degli elementi non maggiore di $k$, $a+b \le k$ se $S={a,b}$.
Risposte
Sia $f(*)$ il numero di sottoinsimi richiesto. $f(3)=1$. Ragionando induttivamente, si ha che $f(n)=f(n-1)+[(n-1)/2]$, cioè il numero di sottoinisiemi per $n-1$, chiaramente, più quelli la cui somma degli elementi è esattamente $n$. La parte intera serve per escludere le partizioni del tipo $n/2+n/2=n$, per $n$ pari. Quindi $f(n)=\sum_{j=3}^n [(j-1)/2]$. Per $n$ pari la si può scrivere anche nella forma $f(n)=2\sum_{j=1}^{[(n-1)/2]} j $.
Sarebbe interessante trovare una formula generale per sottoinsiemi di qualsiasi cardinalità.
Sarebbe interessante trovare una formula generale per sottoinsiemi di qualsiasi cardinalità.
"TomSawyer":
Quindi $f(n)=\sum_{j=3}^n [(j-1)/2]$. Per $n$ pari la si può scrivere anche nella forma $f(n)=2\sum_{j=1}^{[(n-1)/2]} j $.
Forse dovevo precisare che per "forma chiusa" intendevo proprio senza sommatorie, indipendentemente
dalla parita' di $n$ o di $k$
Così come lo hai posto, il problema viene a dipendere da $k$ e non da $n$. Provo a farlo
Certo. Io ho solo scritto $n$ al posto di $k$.
La forma chiusissima (:D) è $((k(k-1))/2-1-[(k-2)/2])/2$. Bruttina. Ne hai una equivalente più carina, vl4d?
La forma chiusissima (:D) è $((k(k-1))/2-1-[(k-2)/2])/2$. Bruttina. Ne hai una equivalente più carina, vl4d?
Eccola li fine esercizietto 
Come l'hai trovata ? Io ho posto condizione su $b \le "fl"(k/2)$, $b > "fl"(k/2)$ (dopo un "wlog $a
e il tutto poi diventa, dopo qualche considerazione, $"fl"(k/2)("ceil"(k/2)-1)$, che e' equivalente alla tua.
@zorn, certo, hai ragione. Ma ll problema l'ho posto come mi e' venuto
naturale pormi il quesito quando ancora non sapevo la risposta, se poi diventa indipendente da $n$,
ci mettiamo un bel WLOG e consideriamo solo $k$
fine esercizietto Come l'hai trovata ? Io ho posto condizione su $b \le "fl"(k/2)$, $b > "fl"(k/2)$ (dopo un "wlog $a
e il tutto poi diventa, dopo qualche considerazione, $"fl"(k/2)("ceil"(k/2)-1)$, che e' equivalente alla tua.
@zorn, certo, hai ragione. Ma ll problema l'ho posto come mi e' venuto
naturale pormi il quesito quando ancora non sapevo la risposta, se poi diventa indipendente da $n$,
ci mettiamo un bel WLOG e consideriamo solo $k$
Molto rudimentalmente, ho scritto in forma chiusa la sommatoria senza le floor, poi ho tolto quello che dovevo .
Direi che è indipendente da $n$, dato che serve solo come bound per $k$. Comunque, rilancio: risolvere lo stesso problema per i sottoinsiemi di cardinalità $3$.
ps: non ho ancora la soluzione. Generalizzare a sottoinsiemi di cardinalità $m$, per $2 \le m \le n$ diventa molto difficile.
.Direi che è indipendente da $n$, dato che serve solo come bound per $k$. Comunque, rilancio: risolvere lo stesso problema per i sottoinsiemi di cardinalità $3$.
ps: non ho ancora la soluzione. Generalizzare a sottoinsiemi di cardinalità $m$, per $2 \le m \le n$ diventa molto difficile.
Io ho trovato questa sommatoria, per i sottoinsiemi di ordine 3 di ${1,...,n}$, con $6 \le k \le 3n-3$:
Secondo me è molto difficile trovare una forma chiusa decente, dato che le parti intere sono un problema qui.
Secondo me è molto difficile trovare una forma chiusa decente, dato che le parti intere sono un problema qui.
Mi chiedo, tra l'altro, se la forma chiusa esista veramente 
Me lo stavo chiedendo anch'io. Ho provato un po' a lavorarci, ma escludendo le sommatorie si arriva ad espressioni orribili, quindi ho preferito non continuare. Ma può essere anche che, calcolando $f_3$ in maniera diversa da come l'ho fatto io, si possa arrivare ad una forma carina.
Per quanto riguarda i sottoinsiemi di cardinalità $m$ maggiore di 3, bisognerebbe conoscere le formule chiuse delle partizioni di un intero in $m$ interi positivi distinti, e dubito che ci siano.
Per quanto riguarda i sottoinsiemi di cardinalità $m$ maggiore di 3, bisognerebbe conoscere le formule chiuse delle partizioni di un intero in $m$ interi positivi distinti, e dubito che ci siano.
"TomSawyer":
Io ho trovato questa sommatoria, per i sottoinsiemi di ordine 3 di ${1,...,n}$, con $6 \le k \le 3n-3$:
Secondo me è molto difficile trovare una forma chiusa decente, dato che le parti intere sono un problema qui.
Non so se sia giusta la formula che hai trovato comunque ti assicuro che le parti intere non sono un problema, puoi usare la proprietà:
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo