Numero di sottoinsiemi di ordine due e somma limitata

[vl4d]

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}$.

[TomSawyer]

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à.

[vl4d]

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$

[zorn]

Così come lo hai posto, il problema viene a dipendere da $k$ e non da $n$. Provo a farlo

[TomSawyer]

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?

[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<b$") e ho contato
nei due casi. Nel primo e' un semplice binomiale, nel secondo diventa una somma ben nota,
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$

[TomSawyer]

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.

[TomSawyer]

Io ho trovato questa sommatoria, per i sottoinsiemi di ordine 3 di ${1,...,n}$, con $6 \le k \le 3n-3$:

Testo nascosto, fai click qui per vederlo

$f_3(k)=\sum_{j=6}^k ((j-3)[j/6]-3[j/6]^2)+[k/6]$

Secondo me è molto difficile trovare una forma chiusa decente, dato che le parti intere sono un problema qui.

[vl4d]

Mi chiedo, tra l'altro, se la forma chiusa esista veramente

[TomSawyer]

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.