Problema di Matematica Combinatoria

[MaxPyero]

Ciao a tutti, ho un problema di matematica combinatoria che non so come affrontare, volevo chiedervi se qualcuno di voi può dami una mano...

Sia dato $S$ intero positivo diverso da zero
$ S \in NN^+ $
Per ogni valore di $S$ si vuole trovare la quantità di possibili permutazioni di $A$ addendi tali per cui:

1) Ogni addendo possa assumere solamente valore $1$ o valore $2$. Per ogni serie non ordinata di addendi (e successivamente per ogni permutazione) indicheremo con $A_1$ e $A_2$ rispettivamente la quantità di addendi di valore $1$ e di valore $2$.
Dunque

$A = A_1+A_2$

e sapendo che la somma degli addendi deve essere $S$

$S = A_1+2A_2$

da cui si ricava facilmente che
$
A-A_2 = S-2A_2$

si può quindi ricavare $A$ in funzione di $A_2$ dato $S$
$
A = S-A_2$

Chiaramente avremo come limite

$0 ≤ A_2 ≤ |__S//2__|$
(l'approssimazione al più vicino intero è necessaria dato che $S$ può essere sia pari che dispari).


Dalle premesse è facile ricavare che, per ogni $S$ avremo $p_s$ serie di addendi non ordinate

$p_s = |__S//2__|+1$


Esempio, per $S=5$ avremo $p_5 =|__5//2__|+1 = 3$ serie non ordinate di addendi $(...)_S^{A_2}$

$
p_5 \Rightarrow (2;2;1)_5^2$ $(2;1;1)_5^1$ $(1;1;1;1;1)_5^0$
dove l’apice delle serie indica $A_2$ e il pedice $S$.

2) Per ogni serie non ordinata $(...)_S^{A_2}$ si potranno avere $x$ permutazioni, tali per cui ciascuna permutazione possa essere “letta” a partire da ognuno dei suoi elementi. In altre parole, ciascuna permutazione è ordinata ma senza origine, ovvero è ciclica.


Esempio per $S=6
$

$A_2=3 \Rightarrow p_6^3 \Rightarrow (2;2;2)_6^{3'}$ una sola permutazione possibile


$A_2=2 \Rightarrow p_6^2 \Rightarrow (2;2;1;1)_6^{2'}$ che quindi comprende anche $(2;1;1;2)$ e $(1;1;2;2)$ e $(1;2;2;1)$

$A_2=2 \Rightarrow p_6^2 \Rightarrow (2;1;2;1)_6^{2''}$ che quindi comprende anche $(1;2;1;2)$

$A_2=1 \Rightarrow p_6^1 \Rightarrow (2;1;1;1;1)_6^{1'}$ che quindi comprende anche $(1;1;1;1;2)$ ecc…


$A_2=0 \Rightarrow p_6^0 \Rightarrow (1;1;1;1;1;1)_6^{0'}$


dove l’apice della serie ordinata indica $A_2$ e la permutazione mentre il pedice indica $S$.
Quindi per $S=6$ abbiamo $X_6=5$ permutazioni possibili.


È chiaro che per $A_2=|__S//2__|$, $A_2=1$ e $A_2=0$ avremo sempre una e una sola permutazione, qualunque sia $S$.

Il problema è capire come calcolare le possibili permutazioni per $1
Ho fatto una tabella per $S$ fino a $12$ con alle ascisse in alto (verdi) $S$, alle ordinate $A_2$ e alle ascisse in basso (rosse) la somma delle permutazioni totali per ogni $S$, ma non riesco a trovare un modo per affrontare il problema...

Qualcuno ha idee, suggerimenti, ecc...?

[MaxPyero]

Trovato

chiamando $M_S$ il numero di permutazioni consentite per ogni $S$

$ M_S=\sum_{i=0}^{|__S//2__|} |__{(S-i)!}/{(S-i)*(S-2i)!*i!}__| + \lceil {{(S-i)!}/{(S-2i)!*i!} - (S-i)|__{(S-i)!}/{(S-i)*(S-2i)!*i!}__|}/{S-i} \rceil $

dove $i=A_2$ del precedente post, ovvero gli elementi con valore $2$.

Quindi $S-i=A$ ovvero il totale degli elementi per ogni permutazione ed $S-2i=A_1$ ovvero gli elementi con valore $1$

Sostituendo:
$ M_S=\sum_{A_2=0}^{|__S//2__|} |__{A!}/{A A_1!A_2!}__| + \lceil {{A!}/{A_1!A_2!} - A|__{A!}/{A A_1!A_2!}__|}/{A} \rceil $

Sapendo che $A!//(A_2!A_1!)$ è il totale delle permutazioni con ripetizione di $A$ elementi ($A_1$ e $A_2$) e chiamandolo $P$ abbiamo che

$ M_S=\sum_{A_2=0}^{|__S//2__|} |__P/A__| + \lceil {P - A|__P/A__|}/{A} \rceil $

ovvero dividiamo il totale $P$ delle permutazioni con ripetizione di $A{A_1;A_2}$ per $A$ stesso dato che ogni serie non ordinata di $A$ elementi contiene $A$ permutazioni di cui solo una è consentita dalle regole; poi aggiungiamo un eventuale resto del quoziente, che si riscontra nel caso in cui $A_1/A_2$ e/o $A_2/A_1$ $in NN$.