Se încarcă...
4,70 stele / 109 voturi ale cititorilor
În abordarea unor probleme aparte de combinatorică, este mai ușor să considerăm o calculare a valorii de pas $ n $ în funcție de valorile anterioare, rezultând într-un șir definit recursiv. Termenul general poate fi, la final, aflat chiar fără a interveni cu inducția simplă după $ i $, care se folosește în mod normal pentru a găsi și demonstra termenul general al unui șir.
1. Combinatorică aritmetică recursivă.
În primul rând, prin combinatorică aritmetică ne referim la ramura din combinatorică care se ocupă cu determinarea unor proprietăți cantitative ale unor mulțimi cu elemente numerice. De exemplu, numărul de numere care au cel mult $ m $ cifre în baza $ k $ este o problemă de combinatorică aritmetică (răspunsul este $ k^m $).
Exemplu: Determinați numărul de numere naturale nenule mai mici decât $ 10^n $ care au oricare două cifre alăturate diferite (***)
Soluție: Pentru fiecare număr de $ k - 1 $ cifre, care are ultima cifră $ a $, se pot forma $ 9 $ astfel de numere de $ k $ cifre, prin adăugarea la finalul numărului inițial o cifră diferită de $ a $.
Formal, dacă definim funcția $ f : \mathbb{N} \to \mathbb{N} $ care reprezintă numărul de numere de $ k $ cifre cu proprietatea dată, $ f(k) = 9f(k - 1) $. Știm $ f(1) = 1 $
Cerința problemei este: $$ \sum_{i = 1}^n f(k) = \sum_{i = 1}^n 9^{i - 1} = \frac{9^{n} - 1}{8}.$$
O problemă mai grea: Să se determine numărul de numere naturale nenule binare mai mici decât $ 2^n $ care nu au în componența lor $ 3 $ cifre consecutive egale. (folclorul informatic)
Soluție: Definim următoarele funcții $ t : \mathbb{N}^* \to \mathbb{N} $, unde $ t(x) $ reprezintă numărul de numere binare cu $ x $ cifre, $ r : \mathbb{N}^* \to \mathbb{N} $, unde $ r(x) $ reprezintă reprezintă numărul de numere binare cu $ x $ cifre care nu respectă proprietatea și $ p : \mathbb{N}^* \to \mathbb{N} $, unde $ p(x) $ reprezintă numărul de numere binare cu $ x $ cifre care au două cifre identice la final și respectă proprietatea.
Pentru un $ x $ dat, știm $ t(x) = 2^{(x - 1)} $. Fiecărui număr cu $ x - 2 $ care respectă proprietatea, îi corespunde un singur număr cu $ x $ cifre care respectă proprietatea, adăugând două cifre identice la sfârșit, ca să nu se formeze $ 3 $ cifre identice la sfârșit. Fiecărui număr care nu respectă proprietatea cu $ x - 1 $ cifre îi corespund două numere care nu respectă proprietatea cu $ x $ cifre și fiecărui număr care are două cifre identice la sfârșit și respectă proprietatea cu $ x - 1 $ cifre îi corespunde un număr care nu respectă proprietatea cu $ x $ cifre.
Formal, $ t(x) = 2^{x - 1} $, $ p(x) = t(x - 2) - r(x - 2) $, $ r(x) = 2r(x - 1) + p(x - 1) $.
În urma calculelor, se obține numărul natural cerut $ \sum t(x) - \sum r(x) $. Se poate observa că, după efectuarea calculelor, numărul căutat este $ \sum_{i = 2}^{n + 1} F[i] $, unde $ F[i] $ este termenul $ i $ al binecunoscutului șir al lui Fibonacci.
2. Combinatorică geometrică recursivă:
Mai întâi, combinatorica geometrică este ramura combinatoricii care studiază proprietățile cantitative ale unor mulțimi cu elemente geometrice (ex. puncte, drepte, plane, figuri și ansamble geometrice etc.).
Exemplu: Determinați numărul maxim de puncte de intersecție dintre $ n $ drepte în plan. (problemă celebră de combinatorică)
Soluție: Adăugând o dreaptă la o colecție de $ k - 1 $ drepte, numărul punctelor de intersecție crește cu $ k - 1 $, dreapta nouă putându-se intersecta cu fiecare din celelalte.
Formal, fie $ f : \mathbb{N} \to \mathbb{N} $, $ f(x) $ reprezintă cerința problemei pentru $ x $ numere. $ f(x) = x - 1 + f(x - 1) $. Știm $ f(1) = 0 $.
Obținem $ f(n) = \frac{(n - 1)n}{2} $.
3. Combinatorica configurațiilor pe tablă recursivă:
Înainte de toate, combinatorica configurațiilor pe tablă este ramura combinatoricii care studiază proprietățile cantitative ale tabelelor cu dimensiuni și forme bine definite, care au celule care pot primi valori numerice, logice (adevărat sau fals) ori de alte tipuri (un caracter, o culoare, poziția unei piese etc.).
Exemplu: Se dă o tablă $ n * 2 $. Determinați numărul de moduri în care poate fi acoperită o tablă cu piese $ 2 * 1 $. (folclor)
Soluție: O tablă $ n * 2 $ poate începe cu: două piese orizontale, deci fiecărei table $ (n - 2) * 2 $ îi corespunde o tablă $ n * 2 $ sau cu o piesă verticală, așadar fiecărei table $ (n - 1) * 1 $ îi corespunde o tablă $ n * 2 $.
Formal, $ f : \mathbb{N} \to \mathbb{N} $, $ f(x) $ reprezintă cerința problemei. Avem $ f(1) = 1 $, $ f(2) = 2 $.
Prin urmare, $ f(n) = F[n + 1] $, păstrând $ F[i] $ termenul $ i $ al șirului Fibonacci.
O generalizare a problemei inițiale: Se dă o tablă $ n * k $. Determinați numărul de moduri în care poate fi acoperită o tablă cu piese $ k * 1 $.
Soluție: O tablă $ n * k $ poate începe cu: $ k $ piese orizontale, deci fiecărei table $ (n - k) * 2 $ îi corespunde o tablă $ n * 2 $ sau cu o piesă verticală, așadar fiecărei table $ (n - 1) * 2 $ îi corespunde o tablă $ n * 2 $.
Formal, $ f : \mathbb{N} \to \mathbb{N} $, $ f(x) $ reprezintă cerința problemei. Avem $ f(n) = f(n - k) + f(n - 1) $, de unde se poate calcula $ f(n) $.
Fă click pe stele pentru a selecta o opțiune și votează articolul! Părerea ta este importantă pentru noi.