Duodesimaali tapa

Duodesimaalinen tapa tai kaksitoista skenaariota on systemaattinen luokittelu 12:sta toisiinsa liittyvästä numeratiivisesta ongelmasta, jotka koskevat kahta äärellistä joukkoa, jotka sisältävät klassiset ongelmat laskettaessa permutaatioita , yhdistelmiä , multijoukkoja ja joko joukon tai luvun osioita . Luokitteluajatus johtuu Gian-Carlo Rothista, ja nimen kaksidesimaalipolku ehdotti Joel Spencer [1] analogisesti fysiikan termin kahdeksankertaisen polun kanssa, joka puolestaan tulee buddhalaisuuden käsitteestä kahdeksankertainen polku . [2] . Nimi vihjaa, että käyttämällä samoja lähestymistapoja 12 tapauksessa, mutta olosuhteiden pienillä muutoksilla, saadaan 12 erilaista tulosta.

Yleiskatsaus

Antaa ja olla äärellisiä joukkoja . Merkitse näiden joukkojen kardinaliteetti (alkioiden lukumäärä). Sanomme, että se on -set ja on -set. $N$ $X$ $n=|N|$ $x=|X|$ $N$ $n$ $X$ $x$

Päätehtävä, jota tarkastelemme, on funktioiden ekvivalenssiluokkien laskeminen . $f:N\to X$

Toiminnot kuuluvat yhden seuraavista kolmesta rajoituksesta:

Ei ole rajoituksia: funktio voi yhdistää minkä tahansa elementin kohteesta mihin tahansa elementtiin , ja jokainen elementti voi esiintyä useita kertoja. $a$ $N$ $f$ $b$ $X$ $b$
$f$ on injektio : jokaisen from arvon on oltava erilainen kuin kaikki muut, jotta jokainen alkio voi esiintyä funktion kuvassa enintään kerran . $fa)$ $a$ $N$ $b$ $X$ $f$
$f$ on surjektio : jokaiselle elementille sieltä tulee olla vähintään yksi elementti sellaisesta , että eli jokainen elementti esiintyy vähintään kerran funktion kuvassa . $b$ $X$ $a$ $N$ $f(a)=b$ $b$ $f$

(Ehto " on bijektio " on mahdollinen vain jos , mutta silloin se vastaa sekä " injektiota" että " on surjektiota".) $f$ ${\näyttötyyli n=x}$ $f$ $f$

On olemassa neljä erilaista ekvivalenssisuhdetta , jotka voidaan määrittää funktioiden joukkoon välillä : $f$ $N$ $X$

tasa-arvo;
tasa-arvo elementtien permutaatioon asti ; $N$
tasa-arvo joukon permutaatioon asti ; $X$
tasa-arvo joukkojen permutaatioon asti ja . $N$ $X$

Mikä tahansa näistä ekvivalenssisuhteista antaa funktiojoukon osion ekvivalenssiluokkiin.

(Ekvivalenssiluokka on funktion kiertorata tarkasteltavana olevan ryhmän vaikutuksesta : f , tai , tai , tai , missä on symmetrinen ryhmä N :llä ja symmetrinen ryhmä X :llä .) $f$ ${\displaystyle f\circ S_{n))$ $S_{x}\circ f$ $S_{x}\circ f\circ S_{n}$ $S_{n}$ $S_{x}$

Kolme funktioiden ehtoa ja neljä ekvivalenssisuhdetta voidaan yhdistää skenaarioiksi. $3\times 4=12$

Laskentafunktioekvivalenssiluokkien kaksitoista tehtävää eivät ole monimutkaisuudeltaan ekvivalentteja, eikä niiden ratkaisemiseen ole olemassa yhtä systemaattista menetelmää. Kaksi tehtävää on triviaaleja (ekvivalenssiluokkien lukumäärä on 0 tai 1), viidellä tehtävällä on vastaus kertovan kaavan muodossa n : ssä ja x :ssä ja lopuilla viidellä tehtävällä on vastaus kombinatoristen funktioiden muodossa ( toisen tyypin ja osiofunktiot tietylle määrälle osia).

Klassiset laskentaongelmat ovat yhdenmukaisia näiden asetusten kanssa seuraavasti.

Joukon X n -permutaatioiden (eli osittaisten permutaatioiden tai sekvenssien ilman toistoja) laskeminen vastaa injektiofunktioiden laskemista . $N\to X$
Joukon X n -yhdistelmän laskeminen vastaa injektiofunktioiden laskemista joukon N permutaatioon asti . $N\to X$
Joukon X permutaatioiden laskeminen vastaa injektiofunktioiden laskemista , missä , sekä surjektiivisten funktioiden laskemista , missä . $N\to X$ ${\näyttötyyli n=x}$ $N\to X$ ${\näyttötyyli n=x}$
Elementtien koon n (tunnetaan myös nimellä n -yhdistelmät toistoineen) laskeminen X : stä vastaa kaikkien funktioiden laskemista joukon N $N\to X$ permutaatioihin asti .
Joukon N osioiden laskeminen x osajoukoksi vastaa kaikkien surjektiivisten funktioiden $N\to X$ laskemista joukon X permutaatioihin asti .
Luvun n laajennuksien laskeminen x osaan vastaa kaikkien surjektiivisten funktioiden laskemista joukon N permutaatioihin asti . $N\to X$

Näkökulmat

Kahdentoista skenaarion eri tehtäviä voidaan tarkastella eri näkökulmista.

Pallot ja laatikot

Perinteisesti monet kahdentoista skenaarion ongelmista on muotoiltu pallojen sijoittamiseksi laatikoihin (tai muihin vastaaviin visualisointeihin) funktioiden määrittämisen sijaan. Sarja N voidaan tunnistaa palloilla ja sarja X laatikoilla. Funktio kuvaa sitten kuinka pallot jaetaan laatikoihin, eli pallo a asetetaan laatikkoon . Sitten ominaisuus, että toiminto määrittää yksilöllisen kuvan jokaiselle toimialueen arvolle, näkyy ominaisuutena, että mikä tahansa pallo voi mennä vain yhteen laatikkoon (yhdessä vaatimuksen kanssa, että palloja ei saa jättää laatikoiden ulkopuolelle), missä mikä tahansa laatikko voi hyväksyä (periaatteessa) mielivaltaisen määrän palloja. Vaatimus ƒ :n olevan injektiivinen tarkoittaa, että mikään laatikko ei voi sisältää useampaa kuin yhtä palloa, kun taas ƒ :n on oltava surjektiivinen tarkoittaa, että jokaisessa laatikossa on oltava vähintään yksi pallo. $f:N\to X$ $f'(a)$

Joukon N ja/tai joukon X permutaatioiden ekvivalenssisuhteiden laskeminen näkyy pallojen ja laatikoiden tunnistamisessa "erottamattomiksi". Tämä tunnistus ei ole tarkka lausunto (käytännössä yksittäiset pallot ja laatikot voidaan erottaa niiden sijainnista ja eri pallot voidaan sijoittaa eri laatikoihin), mutta se osoittaa, että eri kokoonpanoja ei pidetä erillisinä, jos yksi niistä voidaan muuntaa toiseksi vaihtopalloilla tai laatikoilla. Juuri tämä formalisoidaan permutoimalla joukot N ja/tai X . Erottamattomia laatikoita on vaikeampi kuvitella kuin erottumattomia palloja, koska kokoonpano edellyttää väistämättä laatikoiden järjestystä. Laatikoiden uudelleenjärjestely näkyy niiden sisällön vaihdona.

Valinnat

Toinen tapa käsitellä samoja tapauksia on tilastojen otokset . Kuvittele X objektin (tai ihmisten) populaatio, josta valitsemme N . Yleisesti harkitaan kahta mallia, jotka tunnetaan nimellä " näytteenotto takaisinvetämällä" ja "näytteenotto ilman korvaamista" . Ensimmäisessä tapauksessa (valinta palautuksella) kohteen valinnan jälkeen palautamme sen väestölle, jotta se voi osua meihin uudelleen. Kunkin tällaisen otoksen tulos on riippumaton kaikista muista näytteistä, ja näytejoukkoa pidetään teknisesti riippumattomina identtisesti jakautuneina satunnaismuuttujina . Toisessa tapauksessa objektin valinnan jälkeen laitamme sen syrjään, eikä kohde voi ilmestyä toista kertaa. Tämä tarkoittaa, että se, että yksi objekti valitaan, vaikuttaa kaikkiin seuraaviin näytteisiin (tiettyä objektia ei voi lyödä toista kertaa), joten näytteemme tulevat riippuvaisiksi toisistaan.

Jos näytteenotto tapahtuu taaksepäin, sanomme alla "Mikä tahansa f' ", kun taas näytteenottoon ilman paluuta, sanomme "Injektio f' ". Jokainen laatikko ilmaisee, kuinka monta eri joukon valintaa tietyssä skeemassa tehtiin. Rivi sanalla "Erilainen" tarkoittaa, että järjestys otetaan huomioon. Esimerkiksi, jos meillä on objekteja, joista valitsemme kaksi, näyte (4,7) on erilainen kuin (7,4). Toisaalta rivi "S n order" tarkoittaa, että järjestyksellä ei ole väliä; tässä tapauksessa valinnat (4.7) ja (7.4) ovat samat. Todennäköisyysjakauman kannalta reentry-näytteet, joissa järjestys on otettu huomioon, ovat verrattavissa N yksittäisen satunnaismuuttujan yhteisjakauman kuvaamiseen , joista jokaisella on X - kertainen kategorinen jakauma . Tapaus, jossa järjestystä ei oteta huomioon, on verrattavissa yksittäisen N näytteen multinomijakauman kuvaamiseen X - kertaisesta kategoriasta, jossa vain kunkin luokan lukumäärällä on merkitystä. Tapaus, jossa järjestystä ei oteta huomioon ja näytteet tehdään ilman vaihtoa, on verrattavissa erilliseen monimuuttujaiseen hypergeometriseen jakaumaan , eikä neljännen mahdollisuuden vertailu johonkin ole näkyvissä. Huomaa, että kaikissa "injektiivisissä" tapauksissa (eli näytteissä ilman korvaamista) näytesarjojen määrä on nolla, ellei . (Sana "vertailu" tarkoittaa yllä olevissa tapauksissa sitä, että vastaavan jakauman alkeistapahtumaavaruuden jokainen elementti vastaa erillistä näytejoukkoa, ja siksi solussa oleva numero ilmaisee tämän jakauman tapahtumatilan koon.) $N\leqslant X$

Tästä näkökulmasta katsottuna tapaus, jossa on merkintä "Surjektiivinen f' ", näyttää oudolta. Pohjimmiltaan jatkamme valintaa takaisin, kunnes olemme valinneet jokaisen elementin vähintään kerran. Nyt laskemme, kuinka monta kertaa olemme vetäneet pallot, ja jos tämä luku ei ole yhtä suuri kuin N , hylkäämme koko näytteen ja toistamme. Tämä muistuttaa epämääräisesti kuponkien poimintaongelmaa , jossa prosessiin kuuluu X - kuponkien "poimiminen" (haku ja palautus), kunnes meillä on joukko, jossa jokainen kuponki esiintyy vähintään kerran. Huomaa, että kaikissa "surjektiivisissa tapauksissa" näytejoukkojen lukumäärä on nolla, jos ei . $N\geqslant X$

Valinta, merkintä, ryhmittely

Funktiota voidaan tarkastella X :n tai N :n suhteen . Tämä johtaa erilaisiin näkemyksiin: $f:N\to X$

funktio ƒ merkitsee jokaisen joukon N alkion alkiolla X :stä .
funktio ƒ valitsee joukon X alkion jokaiselle joukon N alkiolle, jolloin saadaan yhteensä n näytettä.
funktio ƒ ryhmittelee joukon N elementit yhteen, jos ne kuvataan samaan joukon X alkioon .

Nämä näkemykset eivät päde kaikkiin tapauksiin. "Etiketti" ja "valinta" eivät ole aivan yhteensopivia joukon X elementtien permutaatioiden kanssa , koska ne muuttavat otsikoita ja valintoja. Toisaalta "ryhmittely"-näkökulma ei anna täydellistä tietoa konfiguraatiosta , jos joukon X elementtejä ei voida permutoida. "Näytteistys" ja "valinta"-näkökulmat ovat enemmän tai vähemmän samanarvoisia, kun N ei ole permutoitu, mutta tässä tapauksessa "valinta"-näkökulma on sopivampi. Näytettä voidaan sitten tarkastella järjestämättömänä otoksena - joukosta X valitaan n elementin (moni)joukko .

Merkinnät ja näytteenotto toistoilla tai ilman

Jos ajatellaan , että ƒ merkitsee joukon N alkioita , kirjaimet voidaan ajatella järjestyneinä sekvenssiin ja nimikkeet peräkkäin osoitettuina elementeille. Vaatimus, että funktion ƒ on oltava injektiivinen, tarkoittaa, että mitään etikettiä ei voi käyttää kahdesti. Tuloksena on merkkijono, jossa ei ole toistoja . Tämän vaatimuksen puuttuessa käytetään terminologiaa "sekvenssit, joissa on toistoja", mikä tarkoittaa, että leimoja voidaan käyttää useammin kuin kerran (vaikka myös sekvenssit, joissa ei ole toistoja, ovat sallittuja).

Järjestämättömään näytteeseen sovelletaan samanlaista eroa. Jos ƒ on injektiivinen, valintaan tulee sisältyä n joukon X erillistä alkiota , joten se on joukon X osajoukko, jonka koko on n , ns. n - yhdistelmä . Ilman tätä vaatimusta joukon X sama elementti voi esiintyä otoksessa useita kertoja, jolloin tuloksena on joukon X n elementin monijoukko , jota kutsutaan myös n - monisovitukseksi tai n -sovitukseksi joukon X kanssa. toisto.

Näissä tapauksissa vaatimus, että ƒ on surjektiivinen , tarkoittaa, että mitä tahansa etikettiä on käytettävä vähintään kerran tai että mikä tahansa X :n elementti on sisällytettävä näytteeseen vähintään kerran. Tällainen vaatimus on matemaattisesti vähemmän luonnollinen, ja lisäksi edellinen tapaus on helpompi pitää N :n elementtien ryhmittelynä, johon on lisätty joukon X elementtien ryhmätunnisteet .

Joukkojen ja numeroiden osiot

Jos tarkastellaan ƒ joukon N elementtien ryhmittelynä (mikä tarkoittaa identifiointia joukon X permutaatioiden avulla ), vaatimus, että ƒ on surjektiivinen, tarkoittaa, että ryhmien lukumäärän on oltava täsmälleen yhtä suuri kuin x . Ilman tätä vaatimusta ryhmien määrä ei voi ylittää x . Vaatimus, että ƒ on injektiivinen , tarkoittaa, että jokaisen N :n elementin on oltava itse ryhmä, joka jättää vain yhden pätevän ryhmittelyn, eikä siksi ole mielenkiintoinen laskentaongelma.

Jos lisäksi tunnistus tehdään joukon N permutaatioilla , tämä johtaa ryhmien unohtamiseen, vain niiden koot jäävät jäljelle. Nämä mitat eivät näy missään tietyssä järjestyksessä, ja itse mitat voivat esiintyä useammin kuin kerran. Voit lajitella koot hieman laskevaan numeroluetteloon, jonka summa on n [3] . Tämä antaa kombinatorisen esityksen luvun n jakamisesta täsmälleen x -osiksi (surjektiiville ƒ ) tai enintään x -osille (mielivaltaiselle ƒ ) osille.

Kaavat

Kahdentoista skenaarion eri tapausten kaavat on koottu taulukkoon, jossa jokainen taulukon elementti on linkitetty alla olevaan osioon, joka selittää kaavan.

Kaksitoista kombinatorista objektia ja niiden kaavat.

f -luokka	Mikä tahansa f	Injektio f	Surjektiivinen f
f	n -sekvenssi X :ssä $x^n$	n -joukon X permutaatio $x^{\alleviivaus {n))$	koostumus N x osajoukolla _ $\textstyle x!\{{n \atop x}\}$
${\displaystyle f'\circ S_{n))$	n - X :n moniosajoukko ${\binom {x+n-1}{n))$	joukon X n -osajoukko ${\binom {x}{n))$	kokoonpano n x jäsenellä _ ${\binom {n-1}{nx))$
$S_{x}\circ f$	osioiden N osajoukkoon _ $\leqslant x$ ${\displaystyle \sum _{k=0}^{x}\left\{{n \atop k}\right\))$	N : n jakaminen elementeiksi $\leqslant x$ $[n\leqslant x]$	osioiden N osajoukkoon _ $\leqslant x$ $\left\{{n \atop x}\right\}$
$S_{x}\circ f\circ S_{n}$	jakaa n osiin _ $\leqslant x$ $p_{x}(n+x)$	n jakaminen osiin 1 $\leqslant x$ $[n\leqslant x]$	jakaa n x osaan _ $p_{x}(n)$

Käytetty merkintä:

Pienevä tekijä , $x^{\underline {n}}={\frac {x!}{(xn)!}}=x(x-1)(x-2)\cdots (x-n+1)$
Kasvava tekijä , $x^{\overline {n}}={\frac {(x+n-1)!}{(x-1)!}}=x(x+1)(x+2)\cdots ( x+n-1)$
Factorial $n!=n^{\alleviivaus {n}}=n(n-1)(n-2)\cdots 1$
Toisen tyyppiset Stirling-luvut ilmaisevat kuinka monta tapaa osioida n elementin joukko k osajoukkoon $\textstyle \{{n \atop k}}\}$
Binomiaalinen kerroin $\textstyle {\binom {n}{k}}={\frac {n^{\alleviivaus {k}}}{k!)}}$
Iversonin hakasulkeet koodaavat lausunnon totuuden tai virheellisyyden (1 tai 0)
luvun n osioiden lukumäärä k osaksi _ $p_{k}(n)$

Rivien ja sarakkeiden intuitiivinen merkitys

Tässä on lyhyt yhteenveto kunkin luokan merkityksestä. Luokat on kuvattu yksityiskohtaisesti alla.

Tarkastellaan joukkoa X numeroituja elementtejä (luvut 1 - x ), joista valitaan n , joka antaa järjestetyn luettelon elementeistä. Jos esimerkiksi on elementtejä, joista valitsemme , tuloksena voi olla luettelo (5,2,10). Laskemme nyt, kuinka monta tällaisia erillisiä listoja on, joskus ensin muunnamme luettelot siten, että erilaisten mahdollisuuksien lukumäärä vähenee. $x=10$ $n = 3$

Sitten sarakkeet tarkoittavat:

Mikä tahansa f : Kun olemme valinneet elementin, pinoamme sen takaisin, jotta voimme valita sen uudelleen.
Injektio f : Kun olemme valinneet elementin, asetamme sen sivuun, jotta emme voi valita sitä uudelleen. Siksi päädymme n erilliseen elementtiin. Tietenkin tässä tapauksessa, jos et ole tyytyväinen , emme saa mitään luetteloa. $n\leqslant x$
Surjektiivi f : Kun olemme valinneet elementin, laitamme sen takaisin, jotta voimme vetää sen uudelleen ulos, mutta lopulta jokainen elementti on valittava vähintään kerran. Tietenkin tässä tapauksessa, jos et ole tyytyväinen , emme saa mitään luetteloa. $n\geqslant x$

Viivat tarkoittavat:

Sekalaista: Jätä luettelot sellaisina kuin ne ovat, laske ne suoraan.
S n kiertoradat: Ennen laskemista, lajittele listat valittujen elementtien numeroiden mukaan, jotta järjestyksellä ei ole väliä, esim. (5,2,10), (10,2,5), (2,10,5) jne. kaikki → (2,5,10).
S x kiertoradat: Numeroi elementit ennen laskemista uudelleen siten, että luettelon ensimmäinen alkio on numero 1, toinen (jos ei ole yhtä suuri) numero 2 jne. Numerot voidaan toistaa, jos elementti esiintyy useammin kuin kerran luettelo, esimerkiksi (3,5,3), (5,2,5), (4,9,4) jne. → (1,2,1), while (3,3,5), ( 5,5,3), (2,2,9) jne. → (1,1,2).

$\mathbf {S} _{n}\times \mathbf {S} _{x}$ kiertoradat: Ennen laskemista lista lajitellaan ja numeroidaan uudelleen yllä kuvatulla tavalla. (Huomaa: Uudelleennumerointi ja lajittelu voi joissain tapauksissa tuottaa erilaisia luetteloita, mutta mahdollisten luetteloiden määrä ei muutu.)

Yksityiskohdat eri tapauksista

Alla olevat kotelot on järjestetty siten kuin ne on laskettu, mikä ei ole sama järjestys taulukossa.

Funktiot N :stä X :ään

Tämä tapaus vastaa joukon X n alkion sekvenssien laskentaa ilman rajoituksia: funktio määritellään n elementin kuvalla N :stä , jotka voidaan valita itsenäisesti joukon x hivenelementeistä . Tämä antaa yhteensä x n mahdollisuutta. $f:N\to X$

Esimerkki:

${\displaystyle X=\{a,b,c\},N=\{p,q\))$ , sitten

$\left\vert \{(a,a),(a,b),(a,c),(b,a),(b,b),(b,c),(c,a) ,(c,b),(c,c)\}\right\vert =3^{2}=9$

Injektiofunktiot N :stä X : ään

Tämä tapaus vastaa joukon X n eri elementin sekvenssien laskemista , joita kutsutaan myös joukon X n -permutaatioiksi , tai sekvenssit ilman toistoa . Jälleen sekvenssi muodostuu n elementin kuviosta N :stä . Tämä tapaus eroaa rajoittamattomista sekvensseistä (yllä) siinä, että toisen elementin valinta on yksi vähemmän, toinen kaksi vähemmän ja niin edelleen. Siksi tulos saadaan x :n potenssin sijasta pienenevällä x : n kertoimella, jossa jokainen seuraava tekijä on yhden pienempi kuin edellinen. Kaava yhdistelmien lukumäärälle

x^{\alleviivaus {n}}=x(x-1)\cdots (x-n+1).

Huomaa, että jos , yksi tekijöistä on nolla, joten tässä tapauksessa ei ole injektiofunktioita . Tämä on yksinkertaisesti Dirichlet - periaatteen uusintalause . $n>x$ $N\to X$

Esimerkki:

$X=\{a,b,c,d\},N=\{1,2\}$ , sitten

$\left\vert \{(a,b),(a,c),(a,d),(b,a),(b,c),(b,d),(c,a) ,(c,b),(c,d),(d,a),(d,b),(d,c)\}\right\vert =4^{\alleviivaus {2}}=4\kertaa 3=12$

Injektiofunktiot N :stä X :ään joukon N permutaatioon asti

Tämä tapaus vastaa n: n elementin osajoukkojen laskemista X :stä , joita kutsutaan myös X : n n - yhdistelmiksi - X : n n eri elementin sekvenssien joukossa , ne, jotka eroavat vain elementtien järjestyksestä, tunnistetaan N :n permutaatioilla . Koska kaikissa tapauksissa kaikissa näissä ryhmissä on täsmälleen n ! eri sarjoja, voimme jakaa tällaisten sekvenssien lukumäärän n :llä !, jotta saadaan joukon X n -yhdistelmien lukumäärä. Tämä luku tunnetaan binomikertoimena ja se saadaan kaavasta ${\tbinom {x}{n))$

{\binom {x}{n}}={\frac {x^{\alleviivaus {n}}}{n!)}}={\frac {x(x-1)\cdots (x-n + 2)(x-n+1)}{n(n-1)\cdots 2\cdot 1}}.

Esimerkki:

$X=\{a,b,c,d\},N=\{1,2\}$ , sitten

$\left\vert \{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\ {c,d\}\}\right\vert ={\frac {4^{\underline {2}}}{2!}}={\frac {4\times 3}{2}}=6$

Funktiot N :stä X :ään N :n permutaatioon asti

Tämä tapaus vastaa n-elementin sisältävien multijoukkojen laskemista X : stä ( jota kutsutaan n - moniyhdistelmiksi ). Syynä on se, että jokaiselle joukon X alkiolle yhdistelmä määräytyy sen mukaan, kuinka monta joukon N alkiota on kuvattu kyseiseen elementtiin funktiolla f , kun taas kaksi funktiota, jotka antavat saman määrän "monikertaisuutta" jokaiselle joukon X elementille, voivat muunnetaan aina yhdestä toiseen permutoimalla joukon N alkioita . Kaikki funktiot laskeva kaava on tässä hyödytön, koska N :n permutaatioiden mukaan ryhmiteltyjen elementtien määrä vaihtelee funktiosta toiseen. Pikemminkin, kuten on selitetty kohdassa Yhdistelmät toistoilla , x - elementin joukon n -moniyhdistelmien lukumäärä voidaan ajatella n -yhdistelmien lukumääränä joukosta, jossa on x + n − 1 alkiota. Tämä vähentää ongelman toiseen tapaukseen "kaksidesimaalisella tavalla" ja antaa tuloksen $N\to X$

{\binom {x+n-1}{n}}={\frac {(x+n-1)(x+n-2)\cdots (x+1)x}{n(n- 1)\cdots 2\cdot 1}}={\frac {x^{\overline {n}}}{n!}}.

Esimerkki:

${\displaystyle X=\{a,b,c\},N=\{p,q\))$ , sitten

$\left\vert \{\{a,a\},\{a,b\},\{a,c\},\{b,b\},\{b,c\},\ {c,c\}\}\right\vert ={\frac {3^{\overline {2}}}{2!}}={\frac {4\times 3}{2}}=6$

Surjektiiviset funktiot N :stä X :ään N :n permutaatioon asti

Tämä tapaus vastaa n:n elementin monijoukkojen laskemista X : stä , joissa jokainen X :n elementti esiintyy vähintään kerran. Tämä vastaa luvun n laajennusten laskemista x (nollasta poikkeavaksi) elementiksi , ja x -elementtien moninkertaisuus luetellaan nousevassa järjestyksessä. Vastaavuus funktioiden ja multijoukkojen välillä on sama kuin edellisessä tapauksessa, ja surjektiivisuusvaatimus tarkoittaa, että kaikki kertoimet ovat vähintään yksi. Kun kaikki kertoimet pienennetään yhdellä, ongelma pienenee edelliseen tapaukseen. Koska tällainen muutos pienentää n:n arvoa x : llä , tulos on

{\binom {n-1}{nx)).

Huomaa, että tapauksessa ei ole lainkaan surjektiivisia funktioita . Tämä otetaan huomioon kaavassa, jos binomikertoimien katsotaan aina olevan 0, jos alaindeksi on negatiivinen. Saman arvon antaa myös lauseke $n<x$ $N\to X$

{\binom {n-1}{x-1)),

Paitsi ääritapauksessa , jossa edellinen kaava antaa oikean arvon , mutta viimeinen kaava antaa . $n=x=0$ ${\tbinom {-1}{0}}=1$ ${\tbinom {-1}{-1}}=0$

Tämä tuloskaava ehdottaa surjektiivisten funktioiden assosioinnin etsimistä suoraan n − x elementin osajoukon kanssa , joka on valittu n − 1 elementistä, mikä voidaan tehdä seuraavasti. Valitsemme ensin joukot N ja X täydellisen järjestyksen ja huomaamme, että käyttämällä sopivaa joukon N permutaatiota mikä tahansa surjektiivinen funktio voidaan muuntaa yhdeksi hitaasti kasvavaksi [4] (ja tietysti edelleen surjektiiviseksi) funktioksi. Jos yhdistämme joukon N alkiot (järjestyksen mukaan) n − 1 kaarella viivakaavioksi , niin minkä tahansa n − x kaaren osajoukon valitseminen ja loput poistaminen antaa graafin, jossa on x yhdistetty komponenttia ja ne kartoitetaan. joukon X peräkkäisiksi elementeiksi antaa hitaasti kasvavan surjektiivisen funktion . Myös yhdistettyjen komponenttien mitat antavat koostumuksen n x osassa . Tämä argumentti on olennaisesti sama kuin tähtien ja väliviivojen kohdalla , paitsi että valitaan x − 1 "erotin" $N\to X$ $N\to X$ $N\to X$

Esimerkki:

$X=\{a,b\},N=\{p,q,r\}$ , sitten

$\left\vert \{\{a,a,b\},\{a,b,b\}\}\right\vert ={\binom {3-1}{3-2}}= {\binom {2}{1}}={\frac {2!}{1!\times (2-1)!}}=2$

Injektiofunktiot N :stä X :ään aina X :n permutaatioihin

Tässä tapauksessa tarkastellaan n: n eri elementin sarjaa X :stä , mutta tunnistetaan toisistaan saadut funktiot permutoimalla joukon X alkioita . On helppo nähdä, että kaksi erilaista tällaista sekvenssiä voidaan aina tunnistaa - permutaatiossa tulee kuvata ensimmäisen sekvenssin termi i toisen sekvenssin termiin i , ja koska arvo esiintyy kahdesti molemmissa sarjoissa, nämä vaatimukset eivät ole ristiriidassa keskenään. . Mappaus jää kartoittaakseen elementin, jota ei löydy ensimmäisessä sekvenssissä, elementtiin, jota ei löydy toisesta sekvenssistä. Ainoa asia, joka tekee tuloksen riippuvaiseksi n :stä ja x :stä , on tällaisten sekvenssien olemassaolo, mikä ilmaistaan vaatimuksena Dirichlet'n periaatteen mukaan. Permutaatioiden määrä ilmaistaan siten kuin käytettäessä Iverson-sulkua . $n\leqslant x$ $[n\leqslant x]$

Injektiofunktiot N :stä X :ään joukkojen N ja X permutaatioihin asti

Tämä tapaus supistuu edelliseen - koska kaikki n: n eri elementin sekvenssit X :stä voidaan muuntaa toisikseen käyttämällä joukon X permutaatioita , mikä mahdollistaa elementtien järjestyksen uudelleen luomatta uusia kokonaisuuksia, numero pysyy . $[n\leqslant x]$

Surjektiiviset funktiot N :stä X :ään joukon X permutaatioon asti

Tämä tapaus vastaa N :n osioiden laskemista x (ei-tyhjiin) osajoukkoon tai N : n ekvivalenssisuhteiden laskemista täsmälleen x luokan kanssa. Lisäksi mille tahansa surjektiiviselle funktiolle suhde saman kuvan saamiseen funktiolla f kartoitettuna on tällainen ekvivalenssisuhde, eikä tämä suhde muutu, kun joukon X permutaatioita sovelletaan peräkkäin . Toisaalta tällainen ekvivalenssirelaatio voidaan muuttaa surjektiiviseksi funktioksi osoittamalla tiettyjä ekvivalenssiluokkia joukon X elementeille x . Tällaisten osioiden tai ekvivalenssisuhteiden lukumäärä on määritelmän mukaan toisen tyypin Stirling-luku S ( n , x ), joka kirjoitetaan myös muodossa . Arvoja voidaan kuvata toistuvuusrelaatiolla tai generoivilla funktioilla , mutta toisin kuin binomikertoimilla, näille luvuille ei ole suljetun muotoista lauseketta , jossa ei käytetä summaamista . $N\to X$ $\textstyle \{{n \atop x}}\}$

Surjektiiviset funktiot N :stä X :ään

Jokaiselle surjektiiviselle funktiolle sen kiertoradalla joukon X permutaatioiden yli on x ! elementtejä, koska kokoonpano (vasemmalla) joukon X kahdella eri permutaatiolla ei koskaan anna samaa funktiota joukossa N (permutaatioiden täytyy erota jossain joukon X elementissä , joka voidaan aina kirjoittaa f ( i ) joillekin , ja koostumukset eroavat sitten elementin i ) suhteen. Tästä seuraa, että tämän tapauksen numero x :ssä ! kertaa edellisen tapauksen luku, eli $N\to X$ $i\in N$ $\textstyle x!\{{n \atop x}\}.$

Esimerkki:

$X=\{a,b\},N=\{p,q,r\}$ , sitten

$\left\vert \{(a,a,b),(a,b,a),(a,b,b),\ (b,b,a),(b,a,b), (b,a,a)\}\right\vert =\textstyle 2!\{{3 \atop 2}\}=2\times 3=6$

Toimii N :stä X :ään joukon X tarkalla permutaatiolla

Tämä tapaus on samanlainen kuin vastaava tapaus surjektiivisille funktioille, mutta jotkin x :n elementit eivät välttämättä vastaa yhtään ekvivalenssiluokkaa (koska funktioita tarkastellaan joukon X permutaatioon asti , ei ole väliä mitä elementtejä otetaan huomioon, se sillä on väliä vain kuinka monta ). Tämän seurauksena lasketaan N :n ekvivalenssisuhteet, joissa on enintään x luokkaa, ja tulos saadaan mainitusta tapauksesta summaamalla x -arvot , mikä antaa . Tapauksessa x :n koko ei aseta rajoituksia ollenkaan ja kaikki n elementin joukon ekvivalenssisuhteet lasketaan (vastaavasti kaikki tällaisen joukon osiot). Siksi se antaa lausekkeen kellon numerolle B n . $\textstyle \sum _{k=0}^{x}\{{n \atop k}}\}$ $x\geqslant n$ $\textstyle \sum _{k=0}^{n}\{{n \atop k}}\}$

Surjektiiviset funktiot N :stä X :ään N :n ja X :n permutaatioihin asti

Tämä tapaus vastaa luvun n osioiden laskemista x nollasta poikkeavaan osaan . Tapaus on verrattavissa tapaukseen, jossa lasketaan surjektiivisia funktioita joukon X permutaatioihin asti (vain X , ), vain niiden ekvivalenssiluokkien koot, joihin joukko N tulee ottaa huomioon funktioosioissa (mukaan lukien joukon N moninkertaisuus). jokainen koko), koska kaksi ekvivalenssirelaatiota voidaan muuntaa toiseksi joukon N permutaatioksi silloin ja vain, jos luokkien koot ovat samat. Juuri tämä erottaa n: n osion käsitteen N :n osion käsitteestä , joten tulos saadaan määrittämällä n:n osioiden lukumäärä p x ( n ) x nollasta poikkeavaan osaan. $\textstyle \{{n \atop x}}\}$

Funktiot N :stä X :ään joukkojen N ja X permutaatioon asti

Tämä tapaus vastaa luvun n osioiden laskemista enintään x osaan . Assosiaatio on sama kuin edellisessä tapauksessa, mukaan lukien 0-osan jakaminen jokaiselle X :n elementille, joka ei sisälly funktion kuvaan. Jokainen luvun n osio enintään x nollasta poikkeavaan osaan voidaan laajentaa tällaiseen osioon lisäämällä tarvittava määrä nollia, ja tämä laskee kaikki mahdollisuudet täsmälleen kerran, jolloin tulos saadaan kaavalla . Lisäämällä yksi kuhunkin x osaan, saadaan osio n + x x ei- nollaosaan , ja tämä vastaavuus on bijektiivinen. Siksi lauseke voidaan yksinkertaistaa merkinnällä (vaikka tämä muutos ei helpota laskemista). $\textstyle \sum _{k=0}^{x}p_{k}(n)$ $p_{x}(n+x)$

Äärimmäiset tapaukset

Yllä olevat kaavat antavat vastaavat arvot kaikille äärellisille joukoille N ja X. Joissakin tapauksissa on olemassa vaihtoehtoisia kaavoja, jotka ovat lähes samanarvoisia, mutta jotka eivät anna oikeaa tulosta joissakin ääritapauksissa, kuten tyhjä N tai X . Näissä tapauksissa on otettava huomioon seuraava.

Jokaiselle joukolle X on täsmälleen yksi funktio X :n tyhjästä joukosta ( tälle funktiolle ei ole arvoja), joka on aina injektiivinen, mutta ei koskaan surjektiivinen, paitsi kun X on (myös) tyhjä.
Ei-tyhjälle joukolle N ei ole funktiota N :stä tyhjään joukkoon (on välttämätöntä, että funktiolla on vähintään yksi arvo, mutta ei ole yhtään).
Kun , ei ole injektiofunktiota , ja if , ei ole surjektiivisia funktioita . $n>x$ $N\to X$ $n<x$ $N\to X$
Kaavoissa käytetyillä lausekkeilla on tietyt arvot

0^{0}=0^{\underline {0}}=0!={\binom {0}{0}}={\binom {-1}{0}}=\left\{{ 0 \atop 0}\right\}=p_{0}(0)=1

(kolme ensimmäistä edustavat tyhjää tuloa , ja merkitys määräytyy yleisesti hyväksyttyjen binomikertoimien laajennuksella yläindeksin mielivaltaisiin arvoihin), kun taas

\scriptstyle {\tbinom {-1}{0}}={\frac {(-1)^{\alleviivaus {0}}}{0!)}}=1

\left\{{n \atop x}\right\}=p_{x}(n)=0

koskaan , joko

n>0=x

0\leqslant n<x.

Erityisesti siinä tapauksessa, että lasketaan multijoukkoja , joissa on n elementtiä valittuna X :stä , yllä oleva lauseke vastaa useimmissa tapauksissa lauseketta, mutta jälkimmäinen lauseke tuottaa 0:n tapauksessa (tavallisen käytännön mukaisesti, että binomiaaliset kertoimet negatiivisella alaindeksillä ovat aina 0 ). Samoin tapauksessa, jossa lasketaan luvun n koostumuksia , joissa on x nollasta poikkeavaa osaa, yllä oleva lauseke on melkein sama kuin tähti- ja viiva -argumenttilähestymistavan antama lauseke , mutta jälkimmäisessä tapauksessa saamme väärän tuloksen ja kaikki x :n arvot . Tapauksissa, joissa tulokseen liittyy summaus, eli laskettaessa N :n osioita enintään x ei-tyhjällä osajoukolla tai n: n osioita enintään x nollasta poikkeavalla osalla, summausindeksi alkaa nollasta, vaikka vastaava termi on nolla kaikille ja siitä tulee nollasta poikkeava, kun . Siinä tapauksessa, että tuloksesta tulee virheellinen, jos aloitat summauksen luvusta 1. ${\tbinom {n+x-1}{n))$ ${\näyttötyyli {\tbinom {n+x-1}{x-1))}$ $n=x=0$ ${\tbinom {n-1}{nx))$ ${\tbinom {n-1}{x-1))$ $n = 0$ $n>0$ $n = 0$ $n = 0$

Yleistykset

Voimme yleistää edelleen antamalla muiden permutaatioryhmien vaikuttaa N : ään ja X :ään. Jos G on joukon N permutaatioryhmä ja H on joukon X permutaatioryhmä , lasketaan funktioiden ekvivalenssiluokat . Kaksi funktiota ja niitä pidetään vastaavina, jos ja vain jos niitä on olemassa siten, että . Tämä laajennus johtaa käsitteisiin, kuten syklisiin ja dihedrisiin permutaatioihin sekä lukujen ja joukkojen syklisiin ja kaksitahoisiin osioihin. $f\colon N\to X$ $f$ $F$ $g\in G,h\in H$ $F=h\circ f\circ g$

Desimaalitapa

Toisen yleistyksen, nimeltään 20 way , kehitti Kenneth P. Bogart kirjassaan Combinatorics Through Guided Discovery . Objektien jakamisen laatikoihin ongelmassa esineitä ja laatikoita voidaan pitää erottumattomina tai erilaisina. Bogart erotti 20 tapausta [5] .

2 desimaalin tarkkuudella

n esineitä ja ehtoja, miten ne saadaan	x vastaanottajat ja jakelun matemaattinen malli
n esineitä ja ehtoja, miten ne saadaan	Eri	Sama
1. Erilaiset Ei ehtoja	n -sekvenssit X :ssä $x^n$	osioiden N osajoukkoon _ $\leqslant x$ ${\displaystyle \sum _{i=0}^{n}\left\{{x \atop i}\right\))$
2. Erilaisia Jokainen valitaan enintään kerran	joukon X n -permutaatioita $x^{\alleviivaus {n))$	${\begin{cases}1&n\leqslant x;\\0&n>x\end{cases))$
3. Erilaisia Jokainen valitaan vähintään kerran	sävellykset N , joissa on x osajoukkoa $x!\left\{{n \atop x}\right\}$	jakaa N x osajoukkoon _ $\left\{{n \atop x}\right\}$
4. Erilainen Jokainen valitaan tasan kerran	$n!=x!$ permutaatioita	$1{\begin{cases}1&n=x\\0&n\neq x\end{cases))$
5. Erilaisia, järjestystä kunnioitetaan	${\näyttötyyli (n+x-1)^{\alleviivaus {n))}$ tilatut toiminnot	$\sum _{i=1}^{x}L(n,i)$ rikki permutaatiot ( osissa) $\leqslant x$ Missä on Lachin numero? $L(n,i)$
6. Erilaisia, tilaukset lasketaan Jokainen valitaan vähintään kerran	$(n)^{\alleviivaus {x}}(n-1)^{\alleviivaus {nx}}$ tilattu funktioissa	$L(n,x)=\left({n \atop x}\right)(n-1)^{\alleviivaus {nx))$ rikki permutaatiot ( x osaan) missä on Lachin numero $L(n,x)$
7. Sama ilman ehtoja	joukon X n -multisarjaa $\left({x+n-1 \atop n}\right)$	$\sum _{i=1}^{x}p_{i}(n)$ osioiden lukumäärä ( osissa) $\leqslant x$
8. Identtinen Jokainen valitaan enintään kerran	joukon X n -osajoukkoa $\left({x \atop n}\right)$	${\begin{cases}1&n\leqslant x;\\0&n>x\end{cases))$
9. Sama Jokainen valitaan vähintään kerran	$\left({n-1 \atop x-1}\right)$ sävellykset ( x osaa)	jakaa n x osaan _ $p_{x}(n)$
10. Sama Jokainen valitaan tasan kerran	${\begin{cases}1&n=x\\0&n\neq x\end{cases))$	${\begin{cases}1&n=x;\\0&n\neq x\end{cases))$

Muistiinpanot

↑ Stanley, 1997 , s. 41.
↑ Richard Stanley. Enumeratiivinen kombinatoriikka. - Mir, 1990. - T. 1. - S. 55.
↑ Heikosti laskeva lista on laskeva lista, jossa on mahdollisuus toistoon.
↑ Funktion sanotaan kasvavan hitaasti, jos se on monotoninen, mutta arvojen toistaminen on mahdollista.
↑ Bogart, 2004 , s. 57.

Kirjallisuus

Richard P Stanley. Enumeratiivinen kombinatoriikka, osa I. - Cambridge University Press, 1997. - ISBN 0-521-66351-2 .
Kenneth P. Bogart. Kombinatoriikka ohjatun löydön kautta . - Dartmouth College, 2004.