Jeu japonais
Un jeu japonais vu dans le Figaro considère en particulier pour $n=5$ tous les sous-ensembles $T$ de $\{1,\ldots,2n\}$ de taille $n$ (et leurs complémentaires $T'$) tels que on n'ait jamais trois éléments de $T$ à la suite, et jamais trois éléments de $T'$ à la suite...
Exemple $0011011010$. Combien y a-t-il de tels $T$ ?
Exemple $0011011010$. Combien y a-t-il de tels $T$ ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Si c’est un double, le suivant doit commencer par l’autre élément ce qui nous fait deux possibilités dont un double.
Sinon, on a trois possibilités (toutes sauf le double qui ne va pas), un double et deux non.
Il reste à dénombrer dans un arbre.
-- Schnoebelen, Philippe
Avec ta notation, je les ai écrits tous du plus petit au plus grand
0010011011
0010101011
…
1101010100
1101100100
J'en compte 84.:-S
« Dénombrer les parties $T$ de $E_n=\{1,\ldots,2n\}$, à $n$ éléments, qui ne comportent pas 3 nombres consécutifs, et dont le complémentaire $T'$ dans $E_n$ ne comporte pas non plus 3 nombres consécutifs » ?
Et la suite de $ 0, 1$ représente la fonction caractéristique ( ou indicatrice) d'une telle partie ?
Bonne journée, avec les orages désirés.
Fr. Ch.
Nous avons compris la même chose.
On a la relation de récurrence $a_{n,k}=a_{n-2,n-k}+a_{n-1,n-k}$, ce qui permet de calculer $a_{n,k}$ de proche en proche. Je trouve aussi $2a_{10,5}=84$.
$a_{n,k}=a_{n-2,n-k-2}+a_{n-1,n-k-1}$
$$f(x,y)=\frac{y}{1-y}+y(1+y)f(y,x)$$ qui me mene a la rebarbative fraction rationnelle (mais symetrique en $x,y)$)
$$\frac{1}{y}f(x,y)=\frac{1+xy}{(1-x)[1-y)[1-xy(1+x)(1+y)]}
.$$ Pour verifier que le coefficient de $x^5y^4$ est 42, bonjour. Mais je suis bien maladroit avec Mathematica.Une approche pour calculer $b_{k,k}$ est
$$g(z)=\sum_{k=1}^{\infty}b_{kk}z^k=\frac{1}{2\pi}\int_{0}^{2\pi}f(e^{it},ze^{-it})dt$$ avec bon petit calcul par residus.
Avec la méthode des résidus, j'ai l'intégrale $b_{k,k} = \frac{1}{(2 \pi)^2} \int_{0}^{2\pi} \int_0^{2\pi} f(e^{it}, e^{iu}) e^{-ikt} e^{-iku} du\,dt$, et il y a des techniques pour trouver une formule close ?
edit : Par une autre méthode, je trouve en posant $a_{u,v} = \sum_{n=0}^\infty \binom{n}{u-n} \binom{n}{v-n}$, que $b_{k,k} = a_{k,k} + a_{k-1,k} + a_{k-2,k}$.
Il y a aussi la suite A177790.
Apparemment il n'y a pas de formule simple.
Ainsi un tiers exactement des $\binom {10}{5}= 3\times 84$ séquences équilibrées de $10$ bits ne contient aucun "train" de trois bits égaux. Coïncidence?
Amicalement
Paul
Avec $\dfrac{\binom{10}{5}}6$ on retrouve même le cinquième nombre de Catalan.
Pour construire les mots répondants à la question, je pars d' une suite de 0 et 1 alternés sans double. Je prends n=5.
Cas a : la suite commence par 0 et se termine par 1.
si c'est 0101010101 rien à faire, il est bon
si c' est 01010101, on doit transformer un 0 en 00 et un 1 en 11, il y a 4x4 façons
si c' est 010101, on doit transformer deux 0 en 00 et deux 1 en 11, il y a 3x3 façons
si c'est 0101 il est trop court.
Pour ce cas il y a 1+16+9=26 suites.
010101010, on transforme un 1 en 11, il y a 4 façons
0101010 , on transforme deux 1 et un seul zéros, il y a 3x4 façons
01010 est trop court.
Pour ce cas, on a 16 suites et on retouve bien en tout 26+16=42 suites.
Cette méthode se généralise facilement. La formule est simple, une somme de produits de combinaisons, mais avec cet ipad de m&€@¥% ! je ne peux l'écrire.
$$2\sum_{k=0}^n \binom{k}{n-k}\left(\binom{k}{n-k}+\binom{k+1}{n-k-1}\right)\;,$$
n'est-ce pas ? Bravo !
Dans la formule de GaBuZoMeu c'est $\binom{k-1}{n-k+1}$ pour le dernier coefficient (avec somme de $1$ à $n$).
Edit: en fait ma formule donne la même chose que celle de GaBuZoMeu.
Est-ce qu'il y a une manière algébrique de voir que le $x$ dans la question de Cidrolin est racine de $x^3 - x$ ?