Quanti sottoinsiemi di $\{1,2,…,n\}$ non contengono tre numeri interi consecutivi?

Aug 24 2020

Il mio tentativo. Supponiamo$n$ è un grande intero positivo. ${n \choose 0},{n \choose 1},{n \choose 2}$ sono i numeri di tali sottoinsiemi aventi $0,1,2$elementi rispettivamente, il che è banale. Per$3$ elementi, il numero di tali sottoinsiemi è ${n \choose 3}-(n-2)$. Partendo da$4$elementi, il mio cervello inizia a confondersi; Non ho idea di come procedere ulteriormente in modo sistematico. Qualsiasi suggerimento o idea sarebbe apprezzato.


Nota. Grazie alle soluzioni parziali di VIVID e Masacroso, ho risolto completamente questo problema. Seguendo la risposta di VIVID, ho pubblicato una risposta che completa la soluzione principalmente per riferimento futuro.
Darò la risposta accettata a VIVID che è stato molto dedito a questo problema visto dal suo numero di modifiche. Inoltre, cosa più importante, VIVID è stata la prima persona che ha pubblicato la parte centrale della soluzione. Masacroso, spero che non ti dispiaccia.

Infine, sebbene questo problema sia stato completamente risolto, qualsiasi nuovo approccio è sempre il benvenuto.

Risposte

12 VIVID Aug 24 2020 at 14:42

Soluzione parziale: denotiamo con$S \subseteq \{1,2,\dots,n\}$tutti i set che soddisfano la condizione. E lascia$a_n$ essere il numero di tali insiemi.

Potrebbero esserci alcuni casi:

  1. $n \not \in S \implies$ ci sono $a_{n-1}$ possibilità di $S$ (chiaro)
  2. $n \in S$:
  • un) $n-1 \not \in S \implies$ ci sono $a_{n-2}$ possibilità di $S$ (perché?)
  • b) $n-1 \in S, \ \ n-2 \not \in S \implies$ ci sono $a_{n-3}$ possibilità di $S$. (perché?)

Quindi, otteniamo la formula della ricorrenza $$\boxed{a_n = a_{n-1} + a_{n-2} + a_{n-3}}$$


Rispondi a due (perché?) Parti sopra e diventerà una soluzione completa.

5 Masacroso Aug 24 2020 at 14:48

Schizzo per la soluzione : puoi costruire una ricorsione per trovare questo numero. Permettere$x_k$ il numero di sottoinsiemi in $\{1,\ldots ,k\}$ che non contiene tre numeri consecutivi, quindi $x_{k+1}=x_k+x_{k-1}+x_{k-2}$ perché

  • $x_k$ è il numero di sottoinsiemi in $\{1,\ldots ,k+1\}$ che non contiene $k+1$ e non avere tre numeri consecutivi
  • $x_{k-1}$ è il numero di sottoinsiemi in $\{1,\ldots ,k+1\}$ quello contiene $k+1$ ma non contiene $k$ e non contiene tre numeri consecutivi
  • $x_{k-2}$ rimani per i sottoinsiemi in $\{1,\ldots ,k+1\}$ quello contiene $k+1$ e $k$ ma non contiene tre numeri consecutivi.
3 ploosu2 Aug 24 2020 at 23:07

Ecco forse un altro approccio. (Beh, è ​​fondamentalmente equivalente alle risposte già fornite, ma forse la rappresentazione di stringa binaria rende il problema più facile da pensare. Almeno lo fa per me, ma potrebbe essere perché mi è capitato di avere già familiarità con questi "problemi di lunghezza di esecuzione" .)

Puoi pensare a un sottoinsieme $S$ di $\{1,\dots, n\}$ come stringa binaria di lunghezza $n$, dove $1$ in posizione $j$ si intende $j\in S$ e $0$ si intende $j\notin S$. Ora, i sottoinsiemi che vogliamo contare corrispondono a stringhe binarie senza un$3$-run di $1$'S.

Per risolvere questo nuovo problema, denotiamo

$$A_n = \{\text{length } n \text{ binary strings without a run of three 1's} \}$$

Ora pensa a un file $w\in A_n$ e il numero di $1$E 'all'inizio. Può essere l'uno o l'altro$0$, $1$ o $2$. Poi c'è uno zero e il resto è una parola$A_{n-1}$, $A_{n-2}$ o $A_{n-3}$, rispettivamente. Stiamo assumendo$n>3$; i primi sono casi base. Puoi vedere il tribonacci-ricorsione per la dimensione$|A_n|$.

1 IncredibleSimon Aug 24 2020 at 20:19

Prima di tutto, grazie mille a VIVID e Masacroso per le loro soluzioni parziali con un approccio ricorsivo che è davvero meraviglioso. Di seguito, voglio solo finire ciò che hanno lasciato (il che è positivo per poter pensare) per riferimento futuro e per rafforzare la mia comprensione.

Fammi seguire le annotazioni di VIVID.
Permettere$s$ denotano un elemento generale di $S$.

  • Per quelli $s$ che non contengono $n$, ci sono $a_{n-1}$ come $s$, il che è banale.
  • Per quelli $s$ che contengono $n$ ma non contengono $n-1$, ci sono $a_{n-2}$ come $s$. Perché "isolando"$n$ dobbiamo solo considerare la selezione del resto $n-2$ interi.
  • Per quelli $s$ che contengono entrambi $n$ e $n-1$, non dobbiamo includere $n-2$ in tale $s$, quindi "isolando" $n$ e $n-1$ dobbiamo solo considerare la selezione del resto $n-3$interi. Quindi ci sono$a_{n-3}$ come $s$.

Quindi, riconosciamo che questi tre set di diversi $s$ sono disgiunti, e in effetti lo è la loro unione $S$. Da qui la relazione ricorsiva$a_n=a_{n-1}+a_{n-2}+a_{n-3}$. Quindi possiamo formare una sequenza simile ai numeri di Fibonacci ma questa volta aggiungendo i tre numeri precedenti per ottenere il successivo, cioè$1,2,4,7,13,24,44,81,...$, dove indica il primo numero $a_0$ che corrisponde al set vuoto.

Nota. Mi rendo conto che usando questa ideologia ricorsiva, possiamo derivarne ulteriori sequenze$a_n$ con la condizione sostituita da non avere $r$ interi consecutivi dove $r$ può essere qualsiasi numero intero positivo.