Analyse combinatoire

[GaBuZoMeu]

Vraiment, c'est se fatiguer pour pas grand chose alors que la réponse est sans difficulté à la main en utilisant les combinaisons avec répétition.
Plus ardu :
Compter le nombre d'entiers plus petits que dont la somme des chiffres vaut 20.

[fatal_error]

tldr: 80439789

j'ai une méthode mais c'est laborieux...
on calcule toutes les repartitions et on enlève les invalides:

on enlève les uplets qui ont soit un 11, soit un 12,...soit un 20
je traite le cas 10 à part

donc: e.g pour 11, on le place parmi les x_i=1 à 12, et on cherche 9 avec les 11 possibilités restantes
Je nomme S(k,n) le nombre de possibilités pour répartir la somme n parmi les k containeurs (aka x_i)

et pour 11 choisi assigné à un x_i, on a S(11, 9)

On a pour un k (dans 11, 20), 12*S(k, 20-k) solutions "invalides"

Pour le cas 10, même combat mais il faut enlever C(2, 12) car une répartition donnée avec deux 10 (e.g(10,0,0..,10,..) est comptée deux fois

au final:

[GaBuZoMeu]

Là, ça vaut le coup de faire une procédure. Je la fais en python.

Code: Tout sélectionner

def Comptage(n,t) :
    if n==0 :
        return [1]+t*[0]
    if n>0 :
        LI=Comptage(n-1,t)
        LO=[]
        for u in range(t+1) :
            m=max(0,u-9)
            s=sum(LI[m:u+1])
            LO.append(s)
        return LO

Ça va bien, et assez vite :

Code: Tout sélectionner

%time Comptage(6,10)[-1]

CPU times: user 56 µs, sys: 5 µs, total: 61 µs
Wall time: 64.4 µs

2997

Code: Tout sélectionner

%time Comptage(12,20)[-1]

CPU times: user 412 µs, sys: 39 µs, total: 451 µs
Wall time: 461 µs

80439789

[fatal_error]

ah oui ce u-9 javais déjà vu ce trick dans un autre de tes codes. Tres gbzm

une version un peu différente que javais faite pour vérifier mon compte:

Code: Tout sélectionner

const f = (K, N) => {
  let old = new Map([[0, 1]]) // sum -> number of combination leading to sum
  for (let i = 0; i < K; ++i) {
    const m = new Map()
    for (const [sum, n] of old) {
      for (let j = 0; j < 10; ++j) {
        const newSum = j + sum
        if (newSum > N) {
          break
        }
        m.set(newSum, (m.get(newSum) || 0) + n)
      }
    }
    old = m
  }
  return old.get(N)
}
console.log('tot:', f(12, 20))


oui, la map est overkill vu que on a la "continuité" des entiers de 0 à 20...