Indovina il seme

[adaBTTLS]

non ho certo risolto il tuo problema, ma ho trovato un modo alternativo di contare le sottosequenze, ricorrendo alle partizioni di un naturale.
lavoro con \( \displaystyle {k}=\frac{{n}}{{2}} \).
te lo illustro con \( \displaystyle {n}={6}\to{k}={3} \) e poi ti scrivo i risultati anche per \( \displaystyle {k}={4} \) e per \( \displaystyle {k}={5} \).
le partizioni di \( \displaystyle {k}={3} \) sono: \( \displaystyle {3},{2}+{1},{1}+{1}+{1} \), e ciò, in termini di sequenze binarie di ordine \( \displaystyle {n}={6} \) ci dice che possiamo avere, come secondo il tuo schema:
- la sequenza composta di un'unica parte (equa irriducibile di ordine 6);
- la sequenza composta da due parti eque irriducibili (di cui una di ordine 4 ed una di ordine 2);
- la sequenza composta da tre parti eque irriducibili di ordine 2.
quante sono le sequenze eque irriducibili le sai trovare (in questo caso sono rispettivamente \( \displaystyle {4},{2},{2} \));
inoltre quando hai due sottosequenze di ordine diverso le puoi solo scambiare fra loro in \( \displaystyle {2}!={2} \) modi;
quando hai tre sottosequenze dello stesso ordine non devi "scambiarle" se le conti opportunamente, infatti \( \displaystyle {\left(\matrix{{3}\\{3}}\right)}={1} \).
dunque:
le sequenze del primo tipo (\( \displaystyle {3} \)) sono \( \displaystyle {4} \);
le sequenze del secondo tipo (\( \displaystyle {2}+{1} \)) sono \( \displaystyle {2}\cdot{2}\cdot{2}={8} \);
le sequenze del terzo tipo (\( \displaystyle {1}+{1}+{1} \)) sono \( \displaystyle {{2}}^{{3}}={8} \).
in totale \( \displaystyle {20} \) come tornava a te.
ma quante volte compaiono sottosequenze di ordine due? ogni volta che troviamo \( \displaystyle {1} \), e cioè: \( \displaystyle {4}\cdot{0}+{8}\cdot{1}+{8}\cdot{3}={32} \);
quante sottosequenze di ordine 2 verificano le richieste? \( \displaystyle {2} \);
per ragioni di simmetria (o regolarità), ciascuna di esse compare \( \displaystyle \frac{{32}}{{2}}={16}={{2}}^{{4}} \) volte.
passiamo alle sottosequenze di ordine quattro, che compaiono \( \displaystyle {4}\cdot{0}+{8}\cdot{1}+{8}\cdot{0}={8} \) volte, dunque, essendo \( \displaystyle {2} \), ciascuna di esse compare \( \displaystyle {4}={{2}}^{{2}} \) volte.
(sotto)sequenze di ordine 6, banalmente compaiono \( \displaystyle {4} \) volte, ed essendo 4, ciascuna compare 1 volta.

ora passo a \( \displaystyle {n}={8}\to{k}={4} \)
\( \displaystyle {4}\to{10} \)
\( \displaystyle {3}+{1}\to{4}\cdot{2}\cdot{2}={16} \)
\( \displaystyle {2}+{2}\to{{2}}^{{2}}={4} \)
\( \displaystyle {2}+{1}+{1}\to{2}\cdot{{2}}^{{2}}\cdot{3}={24} \)
\( \displaystyle {1}+{1}+{1}+{1}\to{{2}}^{{4}}={16} \)
totale \( \displaystyle {70} \)
sottosequenze di ordine 2: \( \displaystyle {16}\cdot{1}+{24}\cdot{2}+{16}\cdot{4}={128}\to\frac{{128}}{{2}}={64}={{2}}^{{6}} \)
sottosequenze di ordine 4: \( \displaystyle {4}\cdot{2}+{24}\cdot{1}={32}\to\frac{{32}}{{2}}={16}={{2}}^{{4}} \)
sottosequenze di ordine 6: \( \displaystyle {16}\cdot{1}={16}\to\frac{{16}}{{4}}={4}={{2}}^{{2}} \)
sequenze di ordine 8: \( \displaystyle {10}\to\frac{{10}}{{10}}={1}={{2}}^{{0}} \)

passo a \( \displaystyle {n}={10}\to{k}={5} \)
\( \displaystyle {5}\to{28} \)
\( \displaystyle {4}+{1}\to{10}\cdot{2}\cdot{2}={40} \)
\( \displaystyle {3}+{2}\to{4}\cdot{2}\cdot{2}={16} \)
\( \displaystyle {3}+{1}+{1}\to{4}\cdot{{2}}^{{2}}\cdot{3}={48} \)
\( \displaystyle {2}+{2}+{1}\to{{2}}^{{2}}\cdot{2}\cdot{3}={24} \)
\( \displaystyle {2}+{1}+{1}+{1}\to{2}\cdot{{2}}^{{3}}\cdot{4}={64} \)
\( \displaystyle {1}+{1}+{1}+{1}+{1}\to{{2}}^{{5}}={32} \)
tot. \( \displaystyle {252} \)
sott. 2: \( \displaystyle {40}+{48}\cdot{2}+{24}+{64}\cdot{3}+{32}\cdot{5}={{2}}^{{9}}\to\frac{{{{2}}^{{9}}}}{{2}}={{2}}^{{8}} \)
sott. 4: \( \displaystyle {16}+{24}\cdot{2}+{64}={128}\to\frac{{128}}{{2}}={{2}}^{{6}} \)
sott. 6: \( \displaystyle {16}+{48}={64}\to\frac{{64}}{{4}}={{2}}^{{4}} \)
sott. 8: \( \displaystyle {40}\to\frac{{40}}{{10}}={4}={{2}}^{{2}} \)
sott. 10: \( \displaystyle {28}\to\frac{{28}}{{28}}={1}={{2}}^{{0}} \)

spero che ti possa essere utile. ciao.

[chloe]

argomento piacevole

è davvero interessante, davvero fresco e grande informazione, è davvero bello sapere che questo tipo di moduli, davvero divertente e molto da pensare.

[Rggb]

Quindi sono convinto che il lemma sia vero.

Ho seguito con interesse il tuo ragionamento, anche se ero partito da tutt'altro (ragionamento) per il problema originale - che ancora è messo male... siamo solo ai due semi

Comunque stavo cercando di contare quelle che chiami sequenze eque irriducibili, ovvero
- "quante sono le sequenze (eque) irriducibili lunghe \( \displaystyle {n} \)?"
cercando cosi' di aggirare il problema cercando di "dimostrare che è una mucca partendo dalla coda invece che dalle corna".

Non ho ancora fatto un programma, magari ci penso domani; comunque ho fatto varie congetture e (contando) noto che:
- le sequenze irriducibili con \( \displaystyle {n}={2} \) sono 2 (essendo lunghe 2 esse sono irriducibili pd.)
- idem con \( \displaystyle {n}={4} \) sono 2
- idem con \( \displaystyle {n}={6} \) sono 4
- idem con \( \displaystyle {n}={8} \) sono 10
e mi sono fermato nel scrivere a mano. Ma se quelle con \( \displaystyle {n}={10} \) fossero 28 c'è da pensare (hai questo dato?) e forse una dimostrazione si trova.

[Martino]

Comunque stavo cercando di contare quelle che chiami sequenze eque irriducibili, ovvero
- "quante sono le sequenze (eque) irriducibili lunghe \( \displaystyle {n} \)?"
cercando cosi' di aggirare il problema cercando di "dimostrare che è una mucca partendo dalla coda invece che dalle corna".

Non ho ancora fatto un programma, magari ci penso domani; comunque ho fatto varie congetture e (contando) noto che:
- le sequenze irriducibili con \( \displaystyle {n}={2} \) sono 2 (essendo lunghe 2 esse sono irriducibili pd.)
- idem con \( \displaystyle {n}={4} \) sono 2
- idem con \( \displaystyle {n}={6} \) sono 4
- idem con \( \displaystyle {n}={8} \) sono 10
e mi sono fermato nel scrivere a mano. Ma se quelle con \( \displaystyle {n}={10} \) fossero 28 c'è da pensare (hai questo dato?) e forse una dimostrazione si trova.

Considera che nel secondo lemma dimostro (all'inizio non avevo messo la dimostrazione, ma poi l'ho aggiunta) che il numero di sequenze eque irriducibili di lunghezza n è \( \displaystyle \frac{4}{n} \binom{n-2}{(n-2)/2} \) . Quindi questo problema è risolto.

Il problema ancora da risolvere è: quante volte compare una data sequenza irriducibile di lunghezza \( \displaystyle 2k \leq n \) come fattore irriducibile di una qualche sequenza di lunghezza \( \displaystyle n \) ? La risposta è certamente \( \displaystyle 2^{n-2k} \) ma non sembra facile dimostrarlo. Magari lo è però. Boh.

Mi scuso se ti ho detto cose che sapevi già.

[Martino]

Vi ringrazio per il supporto

Ora mi sono ridotto a dimostrare la seguente uguaglianza.

\( \displaystyle \displaystyle \sum_{a+b=t} \binom{2a}{a} \binom{2b}{b} = 2^{2t} \) ,

dove \( \displaystyle 0 \leq a,b \leq t \) . Di nuovo, questa uguaglianza deve essere vera. Sto cercandone invano un'interpretazione insiemistica. Dietro c'è evidentemente una parametrizzazione delle sequenze binarie di lunghezza 2t (cioè dei sottoinsiemi di \( \displaystyle \{1,...,2t\} \) ), ma ancora non vedo quale. L'induzione non serve. Avete idee?

[gugo82]

Tanto per dirne una...

Col metodo della funzione generatrice si trova:

\( \displaystyle \sum_{n=0}^{+\infty} \binom{2n}{n}\ x^n=\frac{1}{\sqrt{1-4x}} \) *;

quindi, tenendo a mente lo sviluppo del prodotto secondo Cauchy di due serie, si ha:

\( \displaystyle \frac{1}{1-4x} = \left( \frac{1}{\sqrt{1-4x}} \right)^2 =\sum_{n=0}^{+\infty} \left\{\sum_{a+b=n} \binom{2a}{a} \binom{2b}{b}\right\}\ x^n \) .

Confrontando lo sviluppo di Taylor/McLaurin di \( \displaystyle \tfrac{1}{1-4x} \) con la serie precedente, per fissato \( \displaystyle n \) naturale si ricava che:

\( \displaystyle \sum_{a+b=n} \binom{2a}{a} \binom{2b}{b} =\frac{1}{n!}\ \frac{\text{d}^n}{\text{d} x^n} \left[ \frac{1}{1-4x}\right] \Big|_{x=0} \) .

Per induzione si prova facilmente che:

\( \displaystyle \frac{\text{d}^n}{\text{d} x^n} \left[ \frac{1}{1-4x}\right] =\frac{4^n\ n!}{(1-4x)^{n+1}} \)

ergo:

\( \displaystyle \sum_{a+b=n} \binom{2a}{a} \binom{2b}{b} =\frac{4^n}{(1-4x)^{n+1}}\Big|_{x=0} =4^n=2^{2n} \) ,

come volevi.


P.S.: Si sarà capito che a me ragionare in maniera combinatoria secca parecchio...

L'idea della dimostrazione mi è venuta appena ho notato che le somme finite \( \displaystyle \sum_{a+b=t} \binom{2a}{a}\ \binom{2b}{b} \) erano i termini della convoluzione della successione di termine generale \( \displaystyle f(n):=\binom{2n}{n} \) con sé stessa; visto che la convoluzione \( \displaystyle f(n)*f(n) \) è la successione dei coefficienti di Taylor del quadrato della serie \( \displaystyle \sum f(n)\ x^n \) , per terminare bastava determinare la somma di \( \displaystyle \sum f(n)\ x^n \) e vedere se i conti venivano facili.


__________
* Si ricava dallo sviluppo della serie binomiale:

\( \displaystyle (1-y)^\alpha =\sum_{n=0}^{+\infty} (-1)^n\ \binom{\alpha}{n}\ y^n \)

ponendo \( \displaystyle \alpha=-\tfrac{1}{2} \) e facendo un po' di conti.

[Martino]

Onore all'analisi

Accidenti, sapevo che avevo già incontrato espressioni di quel tipo, ma la convoluzione non mi è proprio venuta in mente!

(OT: qual è il significato di \( \displaystyle \binom{\alpha}{n} \) quando \( \displaystyle \alpha=-1/2 \) ?)

PS.

Tanto per dirne una...

Significa che hai trovato altre dimostrazioni dell'uguaglianza?

[gugo82]

Onore all'analisi

Accidenti, sapevo che avevo già incontrato espressioni di quel tipo, ma la convoluzione non mi è proprio venuta in mente!

Visto che sotto-sotto sono un fan delle serie di potenze e delle funzioni analitiche, mi è venuto proprio naturale vedere quella somma in questo modo.

(OT: qual è il significato di \( \displaystyle \binom{\alpha}{n} \) quando \( \displaystyle \alpha=-1/2 \) ?)

Se \( \displaystyle \alpha \) non è naturale, il coefficiente binomiale si definisce come:

\( \displaystyle \binom{\alpha}{n} := \frac{1}{n!}\ \prod_{k=0}^{n-1} \alpha -k \) ;

tale definizione, se \( \displaystyle \alpha \in \mathbb{N} \) , restituisce il solito numerillo (infatti basta moltiplicare e dividere per \( \displaystyle (\alpha -n)! \) ).

PS.

Tanto per dirne una...

Significa che hai trovato altre dimostrazioni dell'uguaglianza?

Nono... Significa che l'ho buttata lì senza grosse pretese che ti piacesse.
E comunque confido che si possa dimostrare anche con metodi combinatori; dopotutto sono pur sempre permutazioni...

[Martino]

Significa che l'ho buttata lì senza grosse pretese che ti piacesse.

Scherzi? Mi piace moltissimo invece.

Inserisco la dimostrazione del lemma.
Fatto.

[gugo82]

Significa che l'ho buttata lì senza grosse pretese che ti piacesse.

Scherzi? Mi piace moltissimo invece.

Inserisco la dimostrazione del lemma.
Fatto.

Ad ogni modo non ho la più pallida idea di dove uscisse la tua relazione, perchè dopo la seconda pagina di conti tuoi e di ada mi perdo... Avete una bella pazienza, voi due!

Se metti tutto per iscritto, poi mi mandi il file pdf? Così ci do uno sguardo con calma e sangue freddo.

Grazie mille Martino.