Olympiades exo combinatoire

[beagle]

peut-être pour compter avec deux permutations


on choisit deux nombres parmi les 10 (par exemple 1 et 5: ça donne les permutations 1-2 et 5-6 )
ils ne doivent pas être consécutifs d'où le -10

I agree.
Si on reprend la série de 0 et 1,
on place deux fois le 1 dans 10 trous, C(2,10)
les doublons sont pour chaque 1 placé il a un adjaccent horaire (ou antihoraire,mais on se fixe juste un coté), donc il faut enlever C(1,10)
ça marche!

[beagle]

Avec les séries de 1 et 0, c'est frisouille!
Les triples, je choisis dans C(3,10) et j'enlève les cas qui ne marchent pas:
les 111 accolés, ben c'est encore du C(1,10)
les 11 accolés avec l'autre 1 à distance
c'est du C(1,10) choisir le 11, fois 10-4= 6 emplacements pour le troisième 1
donc 6xC(1,10)

donc C(3,10)-7xC(1,10) = 120-70=50 cas

[beagle]

Pour les quadruples:
C(4,10)=210
on enlève les 1111 accolés, 1xC(1,10)
on enlève les 111 accolés 5xC(1,10)
on enlève les 11 accolés
il y a peut-ètre plus malin, mais comme je me suis gourré j'ai continué sur le mème schéma:
11 et les autres 1 sont non accolés:
C(1,10) x [C(2,6)-5)= 10xC(1,10)
11 et encore 11, c'est par exemple:
C(1,10) x 5 à diviser par 2 = 25

donc 210-16 (c1,10)-25= 25 quadruples

Bon alors, je suis à
1 pas de changements
10 permutations simples isolées
35 doubles
50 triples
25 quadruples
2 cinquuples

et les 2 vagues ou hola

les 125 cas de Chan, ouf!

[beagle]

Bonjour beagle,
pour les quadruples, te vexe pas , mais cela me fait pitié de te voir utiliser une méthode qui enlève 185 cas à 210.Tu pourrais pas calculer sans la soustraction,en positif directos, non?

[beagle]

suis pas vexé, donc toi tu calcules directement les séries:
1010101000
1010010100
1010100100
et tout se passe comme s'il y en avait 10, 10 et 10/2 quoi, c'est ça?

[Ben314]

Sauf erreur, s'il y a chevaliers, il y a effectivement 2 types de solutions :
1) Les chevaliers se déplacent tous d'un cran vers la droite (ou la gauche) -> 2 solutions
2) Un certain nombre chevaliers échangent leur place avec le chevalier suivant (dans l'ordre trigo par exemple).
Pour fixé (où est la partie entière), on cherche donc le nombre de -uplets tels que pour tout et, dans le cas où , on doit aussi avoir .
a) Si , on cherche donc tels que .
Il y a donc (coeff. binomial) solutions dans ce cas avec évidement une seule solution si .
b) Si , on cherche donc tels que .
Il y a donc solutions et il faut évidement que dans ce cas.

Au total, il y a donc permutations possibles.
On en déduit que , et en utilisant le fait que que, pour , on a :

[beagle]

Dans ces conditions je passe sélectioneur,
je choisis Ben314 pour les olympiades.

darkwoltech ne soit pas déçu, je te qualifie comme premier remplaçant.
Donc des fois où Ben314 se blesse avec un exo, tu auras ta place.

[chan79]

Sauf erreur, s'il y a chevaliers, il y a effectivement 2 types de solutions :
1) Les chevaliers se déplacent tous d'un cran vers la droite (ou la gauche) -> 2 solutions
2) Un certain nombre chevaliers échangent leur place avec le chevalier suivant (dans l'ordre trigo par exemple).
Pour fixé (où est la partie entière), on cherche donc le nombre de -uplets tels que pour tout et, dans le cas où , on doit aussi avoir .
a) Si , on cherche donc tels que .
Il y a donc (coeff. binomial) solutions dans ce cas avec évidement une seule solution si .
b) Si , on cherche donc tels que .
Il y a donc solutions et il faut évidement que dans ce cas.

Au total, il y a donc permutations possibles.
On en déduit que , et en utilisant le fait que que, pour , on a :

Bien vu !!!

[Darkwolftech]

Salut à tous

Merci beaucoup pour vos (nombreuses !!) réponses, je crois pouvoir m'en sortir :zen:

Dans ces conditions je passe sélectioneur,
je choisis Ben314 pour les olympiades.

darkwoltech ne soit pas déçu, je te qualifie comme premier remplaçant.
Donc des fois où Ben314 se blesse avec un exo, tu auras ta place.

Il est vrai que tu fais le bon choix Beagle en sélectionnant Ben314 pour les olympiades ! Perso à la lecture de sa preuve, ce fut plutôt ... violent et ... brutal (en fait j'étais un peu comme ça )

Merci encore ! :++:
Lucas

[chan79]

Salut
Question supplémentaire: Exprimer en fonction de :lol3:

[chan79]

On peut remarquer que , pour :



avec et

[Darkwolftech]

On peut remarquer que , pour :



avec et

Tiens c'est vachement marrant ça !!! Tu saurais me l'expliquer de manière pas trop compliquée ?

[Sourire_banane]

Par récurrence non ?

[Darkwolftech]

Par récurrence non ?

Ok, mais la formule n'est pas tombée de nulle part comme ça non ? :we:

[Ben314]

Sans faire trop de théorie... :

- Partant de tu commence par regarder si, en posant (k=cst) il n'y aurais pas moyen de se ramener à une vrai récurence linéaire, c'est à dire sans le -2 à la fin.
Comme on a :

Donc il suffit de prendre pour que ça marche.

- Ensuite, pour trouver l'expression de en fonction de , on commence par ne pas tenir compte des condition initiales, mais par chercher des suites le plus simple possible vérifiant la relation .
Si on "teste" une suite géométrique (avec et non nuls) on a :

Formule dans laquelle il n'y a plus de n.
Il n'y a plus qu'à résoudfre cette équation du second degrés dont les solutions sont les fameux et du post de chan79.
On constate ensuite que, non seulement les suites de la forme et vérifient , mais que les suites de la forme ( et constante réelles quelconques) vérifient aussi la formule.

- On termine en cherchant quelles valeurs prendre pour et pour de façon à ce que les valeurs initiales soient bien égales à ce qu'on veut (donc ici on veut que et )

[Darkwolftech]

Sans faire trop de théorie... :

- Partant de tu commence par regarder si, en posant (k=cst) il n'y aurais pas moyen de se ramener à une vrai récurence linéaire, c'est à dire sans le -2 à la fin.
Comme on a :

Donc il suffit de prendre pour que ça marche.

- Ensuite, pour trouver l'expression de en fonction de , on commence par ne pas tenir compte des condition initiales, mais par chercher des suites le plus simple possible vérifiant la relation .
Si on "teste" une suite géométrique (avec et non nuls) on a :

Formule dans laquelle il n'y a plus de n.
Il n'y a plus qu'à résoudfre cette équation du second degrés dont les solutions sont les fameux et du post de chan79.
On constate ensuite que, non seulement les suites de la forme et vérifient , mais que les suites de la forme ( et constante réelles quelconques) vérifient aussi la formule.

- On termine en cherchant quelles valeurs prendre pour et pour de façon à ce que les valeurs initiales soient bien égales à ce qu'on veut (donc ici on veut que et )

Ah oui super ! :zen:
Merci beaucoup pour cette explication, c'est vrai que c'est une curiosité assez marrante ... on pourrait rapprocher ça de la suite de Fibonacci peut-être ?

[chan79]

Ah oui super ! :zen:
Merci beaucoup pour cette explication, c'est vrai que c'est une curiosité assez marrante ... on pourrait rapprocher ça de la suite de Fibonacci peut-être ?

Salut
Au vu de la formule de récurrence trouvée par Ben314, j'avais cherché à comparer avec un tableur la suite et la suite de Fibonacci.
Finalement, j'ai fait la conjecture que
Avec c=2, la relation de récurrence est vérifiée quels que soient a et b. (dès que n>2)
avec a=b=1, on a =6 et =9