Nombres en escalier

[t.itou29]

Bonsoir,
J'essaie de trouver une solution élémentaire au problème suivant (une question bonus d'un devoir de seconde l'année dernière)

On appelle nombre en escalier, les nombres dont les chiffres sont croissants de gauche à droite (123 ou 89 par exemple), combien existe-t-il de nombres en escalier ?

Avec un peu de théorie des ensembles: on voit facilement que l'ensemble N des nombres en escaliers est équipotent à l'ensemble des parties non vides de S={1;2;3;4;5;6;7;8;9}. Donc

Mais comment faire avec des connaissances de seconde ?
Et question supplémentaire que je viens de me poser: quelle est la somme de tous les nombres en escalier ?
Merci

[beagle]

c'est aussi somme de i=1à9 des C(i,9)
et c'est à cause du C(9,9) que l'on a un nombre impair
car le reste est 2x somme i=1à4 des C(i,9)
2(9+36+84+126) + 1 = 511

[t.itou29]

c'est aussi somme de i=1à9 des C(i,9)
et c'est à cause du C(9,9) que l'on a un nombre impair
car le reste est 2x somme i=1à4 des C(i,9)
2(9+36+84+126) + 1 = 511

Oui ça marche aussi
Mais sans connaître les coefficients binomiaux c'est difficile à retrouver, il faudrait que je retrouve ma prof de maths de l'année dernière pour lui demander quelle était la solution élémentaire (s'il y en a une...). Sinon y a-t-il moyen de calculer leur somme ? J'ai essayé mais j'ai rien trouvé.
Finalement j'ai peut-être une piste

[nodjim]

Je trouve 320.214.537 pour la somme. Bien sûr, je n'ai pas identifié tous les nb puis fait la somme.
En cherchant combien de fois le chiffre c était représenté au rang 10^n.
Par exemple, combien de fois le chiffre 4 est il représenté au rang 10^2, c'est à dire la 3ème position à partir de la droite ?

[t.itou29]

Je trouve 320.214.537 pour la somme. Bien sûr, je n'ai pas identifié tous les nb puis fait la somme.
En cherchant combien de fois le chiffre c était représenté au rang 10^n.
Par exemple, combien de fois le chiffre 4 est il représenté au rang 10^2, c'est à dire la 3ème position à partir de la droite ?

C'est justement la piste que j'étais en train d'étudier !
Je renvoie un message quand j'ai fini pour dire si je trouve bien le bon résultat

[nodjim]

ça ne fera pas de mal, une erreur de calcul est si vite arrivée.
Donne le détail par rang si tu peux.

[Darkwolftech]

Perso, je vois pas vraiment ...

Ta solution et celle de Beagle ne sont pas accessibles niveau seconde !
J'ai réussi à les dénombrer bêtement, mais c'est franchement long et c***** :ptdr:
On peut s'en sortir en utilisant des sommes de nombres triangulaires emboîtées mais je ne pense pas que c'est ce qu'attendait ta prof !

Moi aussi ça m'intéresse, si quelqu'un a une idée ....

Lucas

[t.itou29]

ça ne fera pas de mal, une erreur de calcul est si vite arrivée.
Donne le détail par rang si tu peux.

Je n'ai pas trouvé la même chose:
Soit i un chiffre d'un nombre en escalier et n son rang dans ce nombre (en partant de gauche).
- nombres en escalier ayant le chiffre i au rang n :
- valeur associée à i :
En notant la somme des valeurs associées à i on a:

En sommant pour i allant de 1 à 9 je trouve 259 374 245
J'ai du me tromper quelque part

[t.itou29]

ça ne fera pas de mal, une erreur de calcul est si vite arrivée.
Donne le détail par rang si tu peux.

Je n'ai pas trouvé la même chose:
Soit i un chiffre d'un nombre en escalier et n son rang dans ce nombre (en partant de gauche).
- nombre de nombres en escalier possédant le chiffre i au rang n :
- valeur associée à ces nombres :
En notant la somme des valeurs associées à i on a:

En sommant pour i allant de 1 à 9 je trouve 259 374 245
J'ai du me tromper quelque part !

[Ben314]

Juste une question avant de regarder (vu les deux exemples que tu donne, c'est un peu ambigüe) :
le nombre 1389 il est bien "en escalier" (i.e. les chiffres ne sont pas obligés d'être consécutifs ?)

[beagle]

Juste une question avant de regarder (vu les deux exemples que tu donne, c'est un peu ambigüe) :
le nombre 1389 il est bien "en escalier" (i.e. les chiffres ne sont pas obligés d'être consécutifs ?)

vivi 1389 est en escalier,tu peux y aller,
bon faut pas chipoter les marches sont pas d'aplomb...

et c'est un escalier qui monte,
tu peux pas descendre, mais t'inquiète Ben314, on viendra te chercher à la fin de l'exo!

[t.itou29]

Juste une question avant de regarder (vu les deux exemples que tu donne, c'est un peu ambigüe) :
le nombre 1389 il est bien "en escalier" (i.e. les chiffres ne sont pas obligés d'être consécutifs ?)

Oui ils sont pas obligés d'être consécutifs, 1389 convient bien

[Ben314]

Dans ce cas, il y en a 2^9-1=511 et je comprend pas trop pourquoi le truc que tu propose n'est "pas accessible" au niveau seconde vu qu'à mon sens ça ne demande aucune conaissance particulière mais juste un peu de reflexion (et c'est bien ce qui me semble attendu dans une "question subsidiaire")

Pour former un tel nombre, il suffit de se donner un certain nombre de chiffres de 1 à 9 vu qu'ensuite on est obligé de les mettre dans l'ordre. (c'est pas compréhesible par un seconde ça ?)

Aprés, qu'il y ait 2^9 façon de prendre des chiffres parmi les chiffres de 1 à 9, ça me semble complètement trivial : le 1, soit je le prend, soit je le prend pas, le 2, soit je le prend, soit je le prend pas et ça me semble pas hors de porté de comprendre que 2 choix puis 2 choix puis 2 choix... , pen au total ça fait 2^9 choix.
A la limite, si on a un minimum de culture informatique, on peut aussi dire que choisir un certain nombre d'objets parmi k, ça revient à choisir un nombre de longueur k en binaire (à la i-ième position, 0=je prend pas l'objet; 1=je le prend)

Enfin, le -1 vient du fait qu'à priori, on ne doit pas prendre l'ensemble vide comme parti de {1,2,...,9}

[t.itou29]

Dans ce cas, il y en a 2^9-1=511 et je comprend pas trop pourquoi le truc que tu propose n'est "pas accessible" au niveau seconde vu qu'à mon sens ça ne demande aucune conaissance particulière mais juste un peu de reflexion (et c'est bien ce qui me semble attendu dans une "question subsidiaire")

Pour former un tel nombre, il suffit de se donner un certain nombre de chiffres de 1 à 9 vu qu'ensuite on est obligé de les mettre dans l'ordre. (c'est pas compréhesible par un seconde ça ?)

Aprés, qu'il y ait 2^9 façon de prendre des chiffres parmi les chiffres de 1 à 9, ça me semble complètement trivial : le 1, soit je le prend, soit je le prend pas, le 2, soit je le prend, soit je le prend pas et ça me semble pas hors de porté de comprendre que 2 choix puis 2 choix puis 2 choix... , pen au total ça fait 2^9 choix.
A la limite, si on a un minimum de culture informatique, on peut aussi dire que choisir un certain nombre d'objets parmi k, ça revient à choisir un nombre de longueur k en binaire (à la i-ième position, 0=je prend pas l'objet; 1=je le prend)

Enfin, le -1 vient du fait qu'à priori, on ne doit pas prendre l'ensemble vide comme parti de {1,2,...,9}

Vu comme ça c'est vraiment trivial, je suis vraiment c.. de ne pas y avoir pensé, j'ai pas capté qu'on pouvait prendre n'importe quels chiffres de 1 à 9 et les remettre dans l'ordre...
Quand je devais le résoudre en seconde j'étais pas habitué a résoudre des problèmes et maintenant j'ai tout de suite pensé a la combinatoire sans comprendre "d'où venait la solution."
Et sinon pour la somme des nombres où je me suis-je trompé ?

[nodjim]

Je ne suis pas tout à fait d'accord avec le C(9-i, 9-n).
Pour le chiffre 3 au rang 4, par exemple, ça donnerait C(6,5)=6. il me semble que c'est seulement bon pour les nombres qui commencent par 3. On peut les citer:
345678, 345679, 345689, 345789, 346789, 356789.
Il manque les mêmes nombres avec les préfixes 1,2 et 12.
D'où le fait que tu en trouves moins que moi.

[Ben314]

Concernant la somme de ces 511 nombres, perso, je procèderais comme ça (peut-être déjà fait : j'ai évidement et comme d'habitude pas lu tout le fil... :mur:)

Si on fixe une position (où la "position 0" désigne le chiffre des unité, c'est à dire le dernier chiffre), alors, à cette position là, on peut avoir n'importe quel chiffre et, pour fixé, il y a possibilités concernant les éventuels chiffres placés avant et il y a possibilités pour les chiffres placés aprés donc au total, il y a nombres "en escalier" contenant un à la -ième position.
La somme cherchée est donc :



En regardant ce qui a été fait, c'est la même valeur que Nodjim !!! :++:

[Ben314]

... je trouve 259 374 245

ça, c'est clairement faux : parmi les "nombres escalier", le plus grand est évidement 123 456 789 donc la somme doit être supérieure à ce nombre là !!!
Aprés, elle peut pas être super vachement plus grande vu qu'il y a que 511 nombres à ajouter, qu'en plus celui là est le seul de 9 chiffres, et qu'il y en a que 9 de 8 chiffres (et en plus 8 des 9 commencent par 1 et le 9em commence par 2)

Donc le 320 214 537 de nodgim semble trés "plausible"

EDIT : Je raconte nimporte quoi : à froid, ton résultat est lui même "assez plausible" vu ça taille, mais il semble quand même un peu trop petit vu que, si tu ajoute (à la machine) 123 456 789 et les 9 "en escalier" de 8 chiffres, ça fait déjà
246 913 569 qui est super proche de ta somme (il y en quand même 36 "en escalier" de 7 chiffres)

[nodjim]

ça m'impressionne les étapes de la simplif, je ne les comprends même pas...

[Ben314]

a) On "réordonne" la somme vu qu'une somme finie, ça se fait dans l'ordre qu'on veut : ici, le seul truc c'est de comprendre que la condition c<=9-k pour k fixé devient k<=9-c pour c fixé : le reste c'est de la recopie (et évidement, tu sort des sommes ce qui ne dépend pas de l'indice qui bouge dans la somme)
b) Binôme de newton : développement de (10+1)^(9-c)
c) On réordonne le truc pour avoir un seul truc à la puissance c-1 dans la somme et pas deux
d) (le moins évident) J'utilise la "formule" : je ne connais évidement pas le résultat par coeur (pas trop de neurones...), mais c'est super simple à retrouver en écrivant que le terme de gauche, c'est la dérivée (par rapport à q) de et, là, par contre, je connais par coeur la valeur de cette somme (donc y'a plus qu'à dériver et légèrement simplifier au brouillon pour retrouver le truc pourri)

[Sa Majesté]

Enfin, le -1 vient du fait qu'à priori, on ne doit pas prendre l'ensemble vide comme parti de {1,2,...,9}

Par contre tout le monde semble considérer que les chiffres sont des nombres en escalier, ce qui ne me semble pas évident vu la définition :

On appelle nombre en escalier, les nombres dont les chiffres sont croissants de gauche à droite (123 ou 89 par exemple)