Combinaisons

[Galt]

Suite au post précédent :
Combien y a-t-il de suites ordonnées de p entiers tous distincts appartenant à [1 .. n ] comportant une suite de q entiers consécutifs ?
Galt

[scelerat]

Suite au post précédent :
Combien y a-t-il de suites ordonnées de p entiers tous distincts appartenant à [1 .. n ] comportant une suite de q entiers consécutifs ?
Galt

S'agit-il d'exactement une suite d'exactement q entiers, ou d'au moins une suite
d'au moins q entiers ?

[Galt]

Je précise mon énoncé :
La plus grande suite d'entiers consécutifs a exactement q termes.

[Alpha]

Salut!


A mon avis, il s'agit d'une suite au moins qui contient q entiers consécutifs, puisque Galt dit "comportant" une suite de q entiers consécutifs. S'il avait voulu dire exactement une suite de q entiers, il aurait dit : comportant une et une seule suite de q entiers consécutifs.

:happy3:

[Galt]

J'ajoute que je ne connais pas la réponse à cette énigme.
Je pense qu'il faut se restreindre à pour que le problème soit faisable (au moins, on a une seule suite de q termes).

[Chimerade]

Salut!


A mon avis, il s'agit d'une suite au moins qui contient q entiers consécutifs, puisque Galt dit "comportant" une suite de q entiers consécutifs. S'il avait voulu dire exactement une suite de q entiers, il aurait dit : comportant une et une seule suite de q entiers consécutifs.

:happy3:

D'accord avec Alpha. Si on parle de "suites ordonnées de p entiers tous distincts appartenant à [1 .. n ] comportant une suite de q entiers consécutifs ?", il n'y a qu'une seule interprétation : il ne peut s'agir que d'une suite ordonnée, contenant au moins une suite d'au moins q entiers consécutifs ; elle peut en contenir plusieurs qui peuvent toutes être plus longues que q ; une suite de q+2 entiers consécutifs exactement doit être considérée comme "contenant 3 suites distinctes (mais non disjointes) de q entiers consécutifs, etc...
Galt, il semble que tu n'aies pas compris qu'Alpha te contredisait : la balle est dans ton camp. Nous attendons tous ta réponse...

[scelerat]

J'ajoute que je ne conais pas la réponse à cette énigme.
Je pense qu'il faut se restreindre à pour que le problème soit faisable (au moins, on a une seule suite de q termes).

Ouf !
Alors, on choisit q entiers consecutifs dans 1...n, on a n-q+1 choix possibles,
puis on choisit p-q entiers parmi ceux qui restent, en evitant celui ou ceux qui
sont adjacents a la suite des q consecutifs pour eviter de l'allonger.

Quand la suite des q est calee sur une des extremites, on choisit p-q parmi
n-q-1 (2 cas), et sinon parmi n-q-2 (n-q+1-2 cas).
Donc


Mais il semble qu'on peut aussi etablir une relation de recurrence dans
le cas general.
Soit X(n,p,q) le nombre cherche, P l'ensemble des p nombres choisis, Q
l'ensemble des q nombres consecutifs (le dernier s'il y en a plusieurs).

Individualisons l'element n et comptons les combinaisons.
1. n n'appartient pas a P : X(n-1,p,q) cas
2. n appartient a Q et donc Q = {n-q+1,...,n}, n-q n'appartient pas a P (sinon on
aurait une suite de q+1), et donc les autres elements de P sont choisis
parmi {1,...,n-q-1}, et on elimine les cas ou il y aurait une suite de plus
de q dans ce choix :
3. n appartient a P mais pas a Q, les autres elements de P nous fournissent
X(n-1,p-1,q) cas, dont il faut retrancher ceux ou la suite Q se terminerait
en n-1, et serait donc allongee par l'element n. On calcule ce dernier nombre
comme au 2. : X(n-1,p-1,q) -

Donc :


Comme on sait des choses genre X(q,q,q) = 1, X(n,q,q) = n-q+1 = X(n,n,q),
etc., et meme la formule plus haut pour q > p/2, on peut remplir la matrice
jusqu'au X(n,p,q) qui nous interesse.

[scelerat]

On calcule ce dernier nombre
comme au 2. : X(n-1,p-1,q) -

Il manque des parentheses, mais ca avait ete rectifie dans la formule
suivante.

X(n-1,p-1,q) -

[scelerat]

Il manque des parentheses, mais ca avait ete rectifie dans la formule
suivante.

X(n-1,p-1,q) -

J'ai decidement ete un peu presse au moment de transposer la formule du 2.

X(n-1,p-1,q) -
et, dans la formule finale,
X(n,p,q)=X(n-1,p,q)+X(n-1,p-1,q)+