155. Somma fattoriale
155. Somma fattoriale
Dimostrare che per ogni numero naturale $n$ esiste un solo numero naturale $k$ e un'unica sequenza di interi $ a_1,..,a_k $ tale che $ n=a_1\cdot 1!+..+a_k\cdot k! $ , dove $ a_k\neq 0 $ e $ 0\leq a_i\leq i $ .
-
Gottinger95
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: 155. Somma fattoriale
E' già stato fatto, però metto un hintarello (di come l'avevo fatto io):
Testo nascosto:
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: 155. Somma fattoriale
Ma è già stato messo sul forum? non lo sapevo 
Dato che è una staffetta se l'hai risolto metti la soluzione, non fa niente che l'hai già visto 
Dato che è una staffetta se l'hai risolto metti la soluzione, non fa niente che l'hai già visto 
-
Gottinger95
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: 155. Somma fattoriale
Osservazione. Vale \(n \cdot n! = (n+1)! - n!\), da cui si ricava il valore di questa somma telescopica:
\(\displaystyle \sum_{i=1}^n{i \cdot i!} = (n+1)!-1\)
Perciò, per le limitazioni imposte, abbiamo, per qualsiasi \(a_1, \ldots, a_n\):
\(\displaystyle \sum_{i=1}^n{a_i \cdot i!} \leq \sum_{i=1}^n{i \cdot i!} = (n+1)!-1 < (n+1)! \)
Poniamo che esistano due diverse rappresentazioni \( ( a_1, \ldots, a_n), \ \ (b_1, \ldots, b_m) \) di un numero con WLOG \(n \geq m\). Allora abbiamo:
\(\displaystyle \sum_{i=0}^n{ a_i i!} = \sum_{i=0}^m{b_i i!}\)
\(\displaystyle \sum_{i=0}^m{(a_i - b_i)i!} + \sum_{i=m+1}^n{a_i i!} = 0\)
Se vogliamo avere qualche speranza di ottenere 0 dall' LHS, i termini \(a_{m+1}, \ldots, a_n\) devono essere 0: infatti i termini della seconda somma sono positivi, e ognuno è maggiore stretto in modulo dell'intera prima somma. Perciò abbiamo ottenuto il primo punto, ossia che se esistono due rappresentazioni, allora hanno la stessa "lunghezza". Sia adesso \(j\) il più grande indice tale che \(a_j \neq b_j\) e ritorniamo alla nostra equazione:
\(\displaystyle \sum_{i=0}^j{(a_i - b_i)i!} = 0\)
\(\displaystyle |(a_j-b_j) j! |= |\sum_{i=0}^{j-1}{(b_i-a_i)i!}| \leq \sum_{i=0}^{j-1}{i \cdot i!} < j! \leq |(a_j-b_j)j! | \)
Assurdo. Perciò esiste una sola rappresentazione. Mmm, ma adesso mi tocca postare un nuovo problema? xD
\(\displaystyle \sum_{i=1}^n{i \cdot i!} = (n+1)!-1\)
Perciò, per le limitazioni imposte, abbiamo, per qualsiasi \(a_1, \ldots, a_n\):
\(\displaystyle \sum_{i=1}^n{a_i \cdot i!} \leq \sum_{i=1}^n{i \cdot i!} = (n+1)!-1 < (n+1)! \)
Poniamo che esistano due diverse rappresentazioni \( ( a_1, \ldots, a_n), \ \ (b_1, \ldots, b_m) \) di un numero con WLOG \(n \geq m\). Allora abbiamo:
\(\displaystyle \sum_{i=0}^n{ a_i i!} = \sum_{i=0}^m{b_i i!}\)
\(\displaystyle \sum_{i=0}^m{(a_i - b_i)i!} + \sum_{i=m+1}^n{a_i i!} = 0\)
Se vogliamo avere qualche speranza di ottenere 0 dall' LHS, i termini \(a_{m+1}, \ldots, a_n\) devono essere 0: infatti i termini della seconda somma sono positivi, e ognuno è maggiore stretto in modulo dell'intera prima somma. Perciò abbiamo ottenuto il primo punto, ossia che se esistono due rappresentazioni, allora hanno la stessa "lunghezza". Sia adesso \(j\) il più grande indice tale che \(a_j \neq b_j\) e ritorniamo alla nostra equazione:
\(\displaystyle \sum_{i=0}^j{(a_i - b_i)i!} = 0\)
\(\displaystyle |(a_j-b_j) j! |= |\sum_{i=0}^{j-1}{(b_i-a_i)i!}| \leq \sum_{i=0}^{j-1}{i \cdot i!} < j! \leq |(a_j-b_j)j! | \)
Assurdo. Perciò esiste una sola rappresentazione. Mmm, ma adesso mi tocca postare un nuovo problema? xD
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: 155. Somma fattoriale
Non bisogna dimostrare anche l'esistenza degli $a_i$ ?
-
Gottinger95
- Messaggi: 486
- Iscritto il: 01 lug 2011, 22:52
Re: 155. Somma fattoriale
Si, ho dimenticato.Si può fare in due modi:
1. Per bezout, visto che il primo termine è 1, posso raggiungere tutti i numeri. Inoltre si può facilmente dimostrare che se una "rappresentazione" non rispetta le limitazioni, allora ne esiste un'altra che fornisce lo stesso numero ma che rispetta le limitazioni (sciogliendo oppure raggruppando gli \(a_i\) che non vanno bene)
2. In modo più elegante, cerchiamo di capire quanti numeri si possono rappresentare usando solo i primi \(k\) termini della "base fattoriale": il coefficiente di \(i!\) può essere scelto in \(i+1\) modi (compreso lo 0), perciò possiamo rappresentare
\(\prod_{i=1}^k{i+1} = (k+1)!\)
numeri. Ma questo numero (considerando che anche lo 0 è incluso nel conteggio) è il massimo a cui posso arrivare con \(k\) termini:
\(1+\sum_{i=1}^k{i \cdot i!} = (k+1)!\)
Perciò, visto che abbiamo dimostrato che esiste un'unica rappresentazione per ogni numero, la rappresentazione fattoriale deve prendere tutti i numeri.
1. Per bezout, visto che il primo termine è 1, posso raggiungere tutti i numeri. Inoltre si può facilmente dimostrare che se una "rappresentazione" non rispetta le limitazioni, allora ne esiste un'altra che fornisce lo stesso numero ma che rispetta le limitazioni (sciogliendo oppure raggruppando gli \(a_i\) che non vanno bene)
2. In modo più elegante, cerchiamo di capire quanti numeri si possono rappresentare usando solo i primi \(k\) termini della "base fattoriale": il coefficiente di \(i!\) può essere scelto in \(i+1\) modi (compreso lo 0), perciò possiamo rappresentare
\(\prod_{i=1}^k{i+1} = (k+1)!\)
numeri. Ma questo numero (considerando che anche lo 0 è incluso nel conteggio) è il massimo a cui posso arrivare con \(k\) termini:
\(1+\sum_{i=1}^k{i \cdot i!} = (k+1)!\)
Perciò, visto che abbiamo dimostrato che esiste un'unica rappresentazione per ogni numero, la rappresentazione fattoriale deve prendere tutti i numeri.
\( \displaystyle \sigma(A,G) \ \ = \sum_{Y \in \mathscr{P}(A) } \dot{\chi_{|G|} } (Y) \) bum babe
Re: 155. Somma fattoriale
La prima non l'ho capita, comunque la seconda funziona 
vai pure
vai pure