Бөлу ережесі (комбинаторика) - Rule of division (combinatorics)

Жылы комбинаторика, бөлу ережесі санау принципі. Онда бар екендігі айтылған n/г. егер орындалатын процедураны қолдану арқылы орындалатын болса, тапсырманы орындау тәсілдері n жолдары және әрқайсысы үшін w, дәл г. туралы n жолдар жолға сәйкес келеді w. Қысқаша айтқанда, бөлу ережесі - заттарды санау кезінде «маңызды емес» айырмашылықтарды ескермеудің кең таралған тәсілі.[1]

Жинақтарға қолданылады

Жиын шартында: «Егер ақырлы жиынтық болса A - әрқайсысының n жұптық бөлінетін ішкі жиындарының бірігуі г. элементтер, содан кейін n = |A|/г.."[1]

Функция ретінде

Функциялар тұрғысынан тұжырымдалған бөлу ережесі: «Егер f функциясы болып табылады A дейін B қайда A және B ақырлы жиындар, және бұл әрбір мән үшін ж ∈ B дәл бар г. құндылықтар х ∈ A осындай f (х) = ж (бұл жағдайда біз мұны айтамыз f болып табылады г.- біреуіне), содан кейін |B| = |A|/г.."[1]

Мысалдар

Дөңгелек үстел мысалының визуалды көрінісі

1-мысал

- Дөңгелек үстел айналасында төрт адамды отырғызудың неше түрлі тәсілі бар, мұнда әр адамның сол жақ көршісі және оң көршісі бірдей болғанда екі орындық бірдей саналады?

Бұл жаттығуды шешу үшін алдымен кездейсоқ орынды таңдап, оны 1 адамға тағайындау керек, қалған орындар кесте бойынша сағат тілімен айналу арқылы сандық тәртіпте белгіленеді. Біз бірінші орынды таңдаған кезде таңдайтын 4 орын бар, екіншісіне 3, үшіншісіне 2, соңғысына 1 опция қалды. Осылайша 4 бар! = Оларды орналастырудың 24 мүмкін тәсілі. Алайда, егер біз олардың көршілері оң және сол жақтары бірдей болмаған кезде ғана басқа орналасуды қарастыратын болсақ, әр 4 орыннан тек 1-і ғана маңызды.
Бөлу ережесі бойынша 1 орынды таңдаудың 4 әдісі бар (n/г.) Сонда 24/4 = 6 4 адамға арналған әр түрлі орындықтар.

2-мысал

- Бізде барлығы 6 түсті кірпіш, оның 4-уі қызыл, 2-уі ақ түсті, оларды неше әдіспен орналастыруға болады?

Егер барлық кірпіштердің түсі бірдей болса, оларды орналастырудың жалпы тәсілдері болар еді 6! = 720, бірақ олардың түсі бірдей болмағандықтан, біз оны келесідей есептейтін едік:
4 қызыл кірпіш бар 4! = 24 келісімдер
2 ақ кірпіш бар 2! = 2 келісімдер
4 қызыл және 2 ақ кірпіштің жиынтығы = 6!/4!2! = 15.

Сондай-ақ қараңыз

Ескертулер

  1. ^ а б c Розен 2012, с.385-386

Әдебиеттер тізімі

  • Розен, Кеннет Н (2012). Дискретті математика және оның қолданылуы. McGraw-Hill білімі. ISBN  978-0077418939.

Әрі қарай оқу