Möbiusova funkcija. Möbiusova inverzijska formula. Mobiusov trak - neverjetno odkritje "Magija" Mobiusovega traku

Srednja občinska proračunska izobraževalna ustanova splošna šola s poglobljenim študijem posameznika

predmeti z. Terbuny

Mobiusov trak

Izpolnila: Chepurina Anna Vitalievna,

Učenka 10. razreda

Vodja: Kirikova M.A.

prva učiteljica matematike

kvalifikacijska kategorija

Terbuny vas

2015

Uvod……………………………………………………..3

Zgodovinsko ozadje………………………………………………………4

Möbiusov trak – začetek nove znanosti o topologiji..................................5

Izdelava Mobiusovega traku…………………………………………………………………………

Poskusi z Mobiusovim trakom ............................................. ...... .................9

Topološke lastnosti Möbiusovega traku……………………..11

Izreki o Möbiusovem traku…………………………………….12

Triki z Mobiusovim trakom…………………………………………………………15

Uporaba Möbiusovega traku……………………………………..16

Zaključek..................................................... ............................................23

Seznam uporabljene literature.................................................. .......... .25

Aplikacija

Uvod

Dandanes je pomembno preučiti različne lastnosti in nestandardne uporabe nenavadnih figur.

Ste že slišali za Möbiusov trak? Kako ga je mogoče izdelati, kako je povezan z matematiko in kje se uporablja v življenju.

Pri tem delu sem prišel do zaključka, da čeprav je bil Möbiusov trak odkrit že v 19. stoletju, je bil pomemben tako v 20. kot v 20. stoletju. Osupljive lastnosti Möbiusovega traku so bile in se uporabljajo v kulinariki, tehnologiji, fiziki, slikarstvu, arhitekturi ter pri oblikovanju nakita in bižuterije. Navdihnil je ustvarjalnost številnih pisateljev in umetnikov.

Zanimanje za Möbiusov trak še danes ni pojenjalo. V Moskvi je septembra 2006 potekal Festival umetniške matematike. Govor profesorja iz Tokia je bil sprejet z velikim uspehom.

Ta tema me je zelo zanimala in navdušila. Študiral sem literaturo, nato sam izdelal Mobiusov trak in nato izvajal raziskave, izvajal poskuse, proučeval njegove magične, izjemne lastnosti.

Möbiusov trak je trak papirja, ki ima en konec obrnjen za pol obrata (to je 180 stopinj) in prilepljen na drugi konec. Milijoni ljudi na vseh koncih sveta se niti ne zavedajo, da vsak dan uporabljajo Möbiusov trak.

Tarča : povejte in pokažite sošolcem, da je na videz preprost trak, obrnjen

pol obrata z zlepljenimi konci, lahko vsebuje veliko

presenečenja.

Predmet študija: Möbiusov trak.

Naloge: prepoznati vire in literaturo na to temo ter jih analizirati;

se seznanijo z zgodovino Mobiusovega traku;

nauči se izdelati Mobiusov trak;

preučevanje različnih lastnosti Möbiusovega traku;

Med delom na temi sem uporabil naslednje metode: analiza, sinteza,

opazovanje, eksperiment, primerjava in sociološka raziskava.

ODSEK jaz

"Möbiusov trak - začetek nove znanosti"

1. 1. Zgodovinsko ozadje

Skrivnostni in slavni Möbiusov trak je leta 1858 izumil nemški geometerAvgust Ferdinand Mobius . Pravijo, da je Mobiusu svoj »list« pomagala odpreti služkinja, ki je narobe zašila konca dolgega traku. Sedem let je čakal na recenzijo svojega dela in brez čakanja objavil rezultate.

V istem času kot Möbius je drug učenec K. F. Gaussa izumil ta list -Johann Benedict Listing, Profesor na Univerzi v Göttingenu. Svoje delo je objavil tri leta prej kot Mobius, leta 1862. A. F. Mobius se je rodil v mestu Schulpforte. Nekaj ​​časa je pod vodstvom K. Gaussa študiral astronomijo. Leta 1818 je začel izvajati neodvisna astronomska opazovanja na observatoriju v Pleisenburgu. postal njegov direktor. Matematika v tistih časih ni bila podprta, astronomija pa je dala dovolj denarja, da o njih ne bi razmišljali, in puščala čas za lastne misli. Ko je leta 1816 postal profesor na univerzi v Leipzigu, je Möbius prvi uvedel projektivno geometrijo, koordinatni sistem in analitične metode raziskovanja; ugotovil obstoj enostranskih ploskev (Möbiusovih trakov), poliedrov, za katere ne velja “zakon robov” in nimajo volumna. Möbius je eden od utemeljiteljev teorije geometrijskih transformacij, pa tudi topologije. Dosegel je pomembne rezultate v teoriji števil (Möbiusova funkcija) in postal eden vodilnih geometrov svojega časa.

1.2. Möbiusov trak - začetek nove topološke znanosti

Od trenutka, ko je nemški matematik A. F. Möbius odkril obstoj neverjetnega enostranskega lista papirja, se je začela razvijati popolnoma nova veja matematike, imenovana topologija. Izraz "topologija" lahko pripišemo dvema vejama matematike. Ena topologija, katere ustanovitelj je bil Poincaré, se je dolgo imenovala kombinatorna. Druga, katere izvor je bil nemški znanstvenik Georg Cantor, je dobila ime splošna ali množično-teoretična.

Kombinatorna topologija je veja geometrije. "Geometrija" je grška beseda, ki prevedena v ruščino pomeni "merjenje zemlje" ("geo" v grščini pomeni zemlja, "metreo" pa pomeni meriti), proučuje lastnosti figur. Kot vsaka znanost je tudi geometrija razdeljena na dele.

1. Planimetrija (latinska beseda, "planum" - površina + geometrija), del geometrije, ki preučuje lastnosti likov na ravnini (trikotnik, kvadrat, krog, krog itd.)

2. Stereometrija (grško, "stereos" - prostor + geometrija) - del geometrije, ki preučuje lastnosti figur v prostoru (krogla, kocka, paralelopiped itd.)

H. Topologija (grško "topos" - kraj, teren + logika) je eden od "najmlajših" oddelkov sodobne geometrije, ki preučuje lastnosti takih figur, ki se ne spremenijo, če so upognjene, raztegnjene, stisnjene, vendar ne zlepljene in se ne trgajo, tj. ne spreminjajo se ob deformaciji. Primeri topoloških objektov so: črki I in H, tanki dolgi baloni.

Kombinatorna topologija proučuje lastnosti geometrijske oblike, ki ostanejo nespremenjeni pri preslikavah ena proti ena in zveznih preslikavah. Dolgo časa je bila topologija dojeta kot znanost, daleč od življenja, namenjena le »poveličevanju človeškega uma«. Toda v našem času je postalo jasno, da je neposredno povezana z razlago strukture vesolja.

Splošna topologija je sosednja teoriji množic in je temelj matematike. To je aksiomatska teorija, zasnovana za raziskovanje konceptov, kot so »meja«, »konvergenca«, »kontinuiteta« itd. Temelje aksiomatike topološkega prostora je postavil in dokončal Felix Hausdorff Ruski matematik Pavel Sergejevič Aleksandrov.

1.3. Kako narediti Möbiusov trak

● Möbiusov trak je eno izmed (matematičnih presenečenj, vzemite pravokotni trak AB).CD, ga zavrtite za 180 stopinj in zlepite nasprotni strani AB inCD, tj. torej bosta točki A in sovpadaliC in pike D in V.

Glej adj. enajst.

● Oblike in velikosti papirnatih trakov za Möbiusov trak.

Trak naj bo ozek in dolg, s čim večjim razmerjem med dolžino in širino. Iz kvadratnega lista papirja ne morete narediti Möbiusovega traku. To je res, vendar ne gre podcenjevati, da so omejitve velikosti pomembne, ko se papir ne sme zmečkati. Če mečkanje papirja ni prepovedano, potem lahko Möbiusov trak zlepimo ne samo iz kvadrata, temveč iz pravokotnika poljubne velikosti - zlepljene stranice so lahko celo poljubno krat daljše od nezlepljenih.

● Razvojna površina.

Ker je zahteva, da se papir ne zmečka, pomembna, poglejmo, kakšen je njen matematični pomen.

Lahko razumeti, da prepoved mečkanja papirja bistveno omejuje

sposobnost ravnanja z listom papirja. List papirja lahko na primer zvijemo v cev ali prepognemo na pol, ne da bi ga zmečkali, ne moremo pa ga zložiti na štiri. Iz lista papirja lahko naredite stožec, ne da bi ga zmečkali, ne morete pa narediti krogle ali celo njenega kosa: pritisnite list papirja ob globus in zagotovo se bodo pojavile gube. Kot lahko vidite, listu papirja ni mogoče dati nobene oblike. Glej adj. 2.

Površine, ki jih lahko izdelamo iz lista papirja tako, da ga upognemo, ne da bi ga zmečkali, matematiki imenujemo razvite površine. V matematiki so razvite površine definirane drugače: v metamatematičnem jeziku ni besed »papir«, »mečkati«, »narediti«. Obstaja cela teorija razvitih površin, med dosežki katere je tudi zadovoljiv odgovor na vprašanje, kaj so lahko; matematiki to imenujejo "razvrstitev" (odgovor pripada Leonardu Eulerju). Predstavimo le nekatere lastnosti razvitih površin kot eksperimentalna dejstva.

Glej adj. 3

1. Skozi vsako točko A razvite ploskve, ki ne leži na njeni meji, poteka segment, ki leži na ploskvi, ki se ne konča na A. Z drugimi besedami, do vsake točke na razviti ploskvi (ukrivljeni, a ne zmečkani list papirja) lahko pritrdite pletilno iglo tako, da do neke mere meji na površino na obeh straneh posnete točke. Tak segment se imenuje generatrisa površine (strinjamo se, da to ime velja samo za segmente največje dolžine, ki v celoti ležijo na površini, torej za segmente, ki niso vsebovani v velikih segmentih s to lastnostjo).

2. Če potekata dve različni generatorji skozi točko A, ki ne leži na meji ploskve in A ni konec nobene od njiju, potem je dovolj majhen kos ploskve, ki obkroža A, raven. V tem primeru bomo točko A imenovali ravno.

3. Če je točka A, ki ne leži na meji površja, konec nekega generatorja, recimo,A , potem je okolica točke A strukturirana takole: skozi točko A poteka edina generatrisa, ki se tam ne konča, recimob . Ta generatrisa deli površino na dva dela. Na drugi strani generatriseb , s katerim se nahaja generatrixa , na generator b ploščat kos je sosednji, na drugi stranib , poljubno iz točke A, obstajajo neravne točke. V tej situaciji bomo točko A imenovali polravna.

Poudarjamo, da če točka na ploskvi ni niti mejna niti ravnina, teče skozi njo ena sama generatrisa, ki se na njej ne konča, konci te generatrise pa ležijo na meji ploskve.

●Primeri: List papirja, zvit v valj ali stožec, nima ravnih (ali polploskih) konic. Za jeklenko generatorji sestavljajo družino vzporedni segmenti, ima stožec družino segmentov, ki se pahljačasto širijo iz ene točke. Možne so bolj zapletene razporeditve generatric.

Glej adj. 4.

Na sliki so na primer prikazani generatorji in ravne točke razvijajoče se ploskve (v kateri je površina razgrnjena v raven list papirja): tanke črte so generatorji, osenčena območja pa so sestavljena iz ravnih točk.

Točke, ki ležijo na meji območja ravnih točk, so mejne točke za celotno površino ali polravne. Če je površina sestavljena iz papirnatega mnogokotnika (recimo pravokotnika), potem ravninske točke sestavljajo enega ali več ravninskih mnogokotnikov, pri čemer ima vsak od teh mnogokotnikov oglišča, ki ležijo na meji površine, stranice pa bodisi ležijo na meji bodisi so sestavljene iz polravninskih točk.

POGLAVJE 2

2.1. Poskusi z Mobiusovim trakom

Vsak od nas ima intuitivno predstavo o tem, kaj je "površina". Površino lista papirja, površino sten učilnice, površino globusa poznajo vsi. Ali je lahko kaj skrivnostnega v tako navadnem konceptu? Da, morda je primer Möbiusov trak. Za preučevanje njegovih lastnosti sem sam izvedel več poskusov (razdelil sem jih v dve skupini).

jaz skupina poskusov

Izkušnja št. 1. Navajeni smo, da na kateri koli površini, s katere

imamo opravka (list papirja, cev za kolo ali odbojko) –

dve strani.

Mobiusov trak sem začel slikati, ne da bi ga obračal.

Rezultat . Möbiusov trak je bil v celoti prebarvan.

»Če se kdo odloči barvati samo eno stran

površino Möbiusovega traku, naj vse takoj potopi v vedro barve,« - pišeta Richard Courant in Herbert Robins v odlični

knjiga "Kaj je matematika?"

Izkušnja št. 2. Iz papirja sem naredila pajka in muho ter ju poslala “na sprehod” naokoli

navaden prstan, a jim prepovedali prehajanje meja.

Rezultat. Pajek ni mogel priti do muhe.

Poskus št. 3. Tega pajka sem poslal in leti le po Mobiusovem traku. IN

jim prepovedal plazenje čez mejo.

Rezultat.Uboga muha bo pojedena, če seveda pajek teče

hitreje!

Izkušnja št. 4. Iz papirja je naredila možička in ga poslala potovati po Mobiusovem traku.

Rezultat. Človek se bo vrnil na izhodiščno točko, kjer bo srečal svojo zrcalno podobo.

II skupina poskusov

povezanih z rezanjem Möbiusovega traku, so rezultati navedeni v tabeli

izkušnje

Opis doživetja

Rezultat

Preprost obroček sem po dolgem prerezal po sredini.

Dobila sem dva enostavna obročka, enako dolga, dvakrat širša, z dvema obrobama.

Möbiusov trak je bil vzdolžno prerezan po sredini.

Prejel sem 1 obroček, katerega dolžina je dvakrat daljša, širina dvakrat ožja, zavit za 1 polni obrat, z eno obrobo.

Širina Möbiusovega traku

5cm prerežemo po dolžini na razdalji 1cm od roba.

Prejel sem dva medsebojno povezana prstana: 1) Mobiusov trak - dolžina = dolžina originalnega, širina 3 cm; 2) širina 1 cm, dolžina dvakrat večja od originalne, zavita dva polna obrata, z dvema robovoma.

Širina Möbiusovega traku

5 cm prerežemo po dolžini na razdalji 2 cm od roba.

Prejel sem dva medsebojno povezana prstana: 1) prstan je Möbiusov trak širine 1 cm, dolžina = dolžini originalnega; 2) obroč - širok 2 cm, dvakrat daljši od prvotnega, zasukan z dvema polnima obratoma, z dvema obrobama.

Möbiusov trak širine 5 cm, prerezan po dolžini na razdalji 3 cm od roba.

Dobil sem dva obroča, povezana drug z drugim: 1) obroč je Möbiusov trak s širino

1 cm enake dolžine; 2) prstan – širok 2 cm, njegova dolžina je dvakrat večja od prvotne, zvit za dva polna obrata.

Rezultati sociološke ankete z učenci 10. razreda.

Vprašanja

ja

št

Ste slišali

1. Ali veste, kaj je topologija?

2. Ali veste, kaj je Mobiusov trak?

3.Ali ste vedeli lastnosti Mobiusovega traku?

Le 5 % učencev 10. razreda ve, kaj je topologija. 30 % učencev ve, kaj je Mobiusov trak. 50% nima pojma o Mobiusovem traku. 25 % učencev pozna lastnosti traku, 10 % jih je že slišalo zanje, 65 % jih ne ve nič o lastnostih Möbiusovega traku.

2.2.Topološke lastnosti Möbiusovega traku

Na podlagi rezultatov poskusov lahko formuliramo naslednje topološke lastnosti Möbiusovega traku, povezane z matematičnimi presenečenji.

Enostranskost je topološka lastnost Möbiusovega traku, značilna samo zanj.

Zveznost - na Möbiusovem traku je mogoče povezati katerokoli točko

s katero koli drugo točko. Ni prekinitev – popolna kontinuiteta.

S topološkega vidika se krog ne razlikuje od kvadrata,

ker jih je enostavno spremeniti enega v drugega, ne da bi se zlomili

kontinuiteta.

Povezljivost – za prepolovitev prstana bosta potrebna dva reza. Pri Möbiusovem traku se število povezav zamenja glede na spremembo števila ovojev traku: če je en zavoj dvojno povezan, če sta dva zavoja preprosto povezana, če so trije zavoji dvojno povezani itd. kvadrat razdelimo na dva dela, potrebujemo le en rez. Povezljivost se običajno ocenjuje z Bettijevim številom ali pa se včasih uporablja Eulerjeva karakteristika.

4. Orientacija je lastnost, ki je v Möbiusovem traku ni. Torej, če bi človek lahko potoval po vseh ovinkih Mobiusovega traku, bi se vrnil Izhodišče, ampak bi se spremenil v njegovo zrcalno podobo.

5. »Kromatsko število« je največje število območij, ki jih je mogoče narisati na površino, tako da ima vsako od njih skupno mejo z vsemi drugimi. Kromatsko število Möbiusovega traku je šest.

6. Izreki o Möbiusovem traku

Izrek 1: λ ≥ π/2

Zaradi zahtevnosti dokaza ga pri svojem delu ne upoštevam.

Izrek 2: λ ≤ √3

Ta izrek je preprostejši od prejšnjega: za dokaz je dovolj, da razložimo, kako zlepimo Möbiusov trak iz traku, katerega dolžina je večja od √3. Najprej predpostavimo, da je njegova dolžina natanko √3. Nato lahko na ta trak postavite dva pravilna trikotnika. Zložimo trak vzdolž stranic teh trikotnikov v izmenični smeri pregibanja. Robova AB in CD traku se bosta poravnala, točka A se bo poravnala s točko D in točka B s točko C. Rezultat bo Möbiusov trak, katerega robovi so postavljeni od konca do konca (glejte Dodatek 1.2 )

Pri tej konstrukciji je bilo kršeno glavno pravilo - ne gubajte papirja. Vendar je enostavno razumeti, da če je dolžina traku vsaj malo večja od √3, potem lahko prelom vzdolž generatrike nadomestimo z upogibom v ozkem delu. Skratka, ne bojimo se pregiba vzdolž ravnega segmenta: lahko ga nadomestimo z ovinkom blizu njega. (Nepopravljivo zmečkanje papirja nastane, ko se dve pregibni črti sekata, tj. ko je list prepognjen kot robec – vse to nam je znano iz vsakdanjih izkušenj.) Njegovo strukturo si lahko predstavljamo takole: trije enaki pravilni trikotniki ABC, A"B"C", A"B"C" ležijo vzporedno drug z drugim, ustrezna oglišča so nad ustreznimi oglišči; stranice AB in A"B", B"C" in B"C", C"A" in CA so povezane z mostički. Linija lepljenja poteka vzdolž mediane enega od trikotnikov.

Zakaj λ ne moremo najti natančneje?

Dokler problem ni rešen, je težko reči, zakaj ni rešen. Kljub temu je včasih v različnih nerešenih problemih mogoče izslediti skupne težave, označiti tako rekoč težka mesta na matematičnem zemljevidu, kar včasih omogoča napovedovanje uspeha ali neuspeha pri reševanju določenega problema.

Izrek 3. Möbiusov trak s samopresečišči je mogoče zlepiti iz traku poljubne dolžine, večje od π/2.

To se naredi takole. Vzemimo dovolj veliko liho n in sestavimo pravilni n-kotnik, včrtan v krog s premerom 1. Razmislimo še o n trikotnikih s središčem kroga, od katerih je vsak omejen s stranico in dvema diagonalama n- gon (n=7). Ti trikotniki pokrivajo naš n-kotnik, nekaj njegovih mest večkrat. Prilepimo zdaj teh n trikotnikov drug na drugega, nato pa odrežemo polovico skrajnega levega trikotnika vzdolž dolge mediane in jo prilepimo na skrajni desni trikotnik. Rezultat je pravokoten trak z razmerjem med dolžino in širino, ki je večje od π/2 in teži k π/2 kot n, ki teži k ∞ (širina traku teži k 1, dolžina pa k π/2). Ta trak dosledno zložite vzdolž vseh črt, ki so na njem narisane, in menjajte smeri zgibanja. Segmenta AB in CD bosta skoraj sovpadala - med njima bo le nekaj plasti prepognjenega papirja. Pri tej "skoraj poravnavi" se bo točka A poravnala z D, točka B pa s C, tako da če bi lahko "prenesli trak skozi" in prilepili |AB| z |CD|, bi bil rezultat Möbiusov trak. Če trak vzamete malo dlje, se lahko izognete pregibom, tako kot smo to storili pri dokazu izreka 2. Dobili smo Möbiusov trak, katerega robovi so ločeni z več plastmi papirja, glej prilogo 1.3. A vrnimo se k Möbiusovemu traku. Izrek 1, kot smo videli, dejansko velja za pasove, ki se sekajo sami s seboj. Ni verjetno, da bi pogoj brez samopreseka ne vplival na λ; vendar pa tega učinka ni mogoče upoštevati, saj matematika nima dovolj tehničnih sredstev za preučevanje samopresečišč v tridimenzionalnem prostoru. Nasprotno, zelo verjetno je, da izreka 2 ni mogoče izboljšati. Navsezadnje njegovo izboljšanje pomeni oblikovanje novega traku. Izkušnje kažejo, da so optimalne konstrukcije enostavne in harmonične, kar je konstrukcija iz dokaza izreka 2. Naravno je domnevati, da če bi obstajala najboljša konstrukcija, bi bila najdena – po toliko letih!

Zato lahko pričakujemo λ = √3.

Triki z Moebiusovim trakom

Težava pri vezanju vozlov

Kako zavezati vozel na šalu, ne da bi izpustili njegove konce? Lahko se naredi tako. Položite šal na mizo. Prekrižajte roke na prsih. Še naprej jih držite v tem položaju, se sklonite nad mizo in z vsako roko primite en konec šala. Ko so roke razmaknjene, se na sredini šala samodejno oblikuje vozel. Če uporabimo topološko terminologijo, lahko rečemo, da gledalčeve roke, njegovo telo in šal tvorijo sklenjeno krivuljo v obliki »trilistnega« vozla. Pri razmiku rok se vozel premakne samo z rok na šal.

Zavežite šal z eno roko, ne da bi izpustili konec šala iz roke. Odgovor na to uganko je mogoče najti v knjigi "Matematični čudes in skrivnosti" M. Gardnerja.

S topološkega vidika lahko telovnik obravnavamo kot dvostransko ploskev s tremi neprepletenimi robovi, od katerih je vsak navadna zaprta krivulja. Brezrokavnik z gumbi je dvostranska površina s štirimi robovi.

Skrivnostna zanka.

Gledalec, ki nosi jopič, ima na roki nameščeno zanko, nato pa mora palec položiti v spodnji žep jopiča. Zdaj lahko povabite prisotne, da vam odstranijo zanko iz roke, ne da bi odstranili prst iz žepa telovnika. Rešitev je naslednja: zanko je treba potegniti v odprtino telovnika za rokav, jo vreči čez glavo gledalca, izvleči skozi drugo luknjo za rokav in jo prenesti pod drugo roko. Zaradi teh dejanj bo zanka pod telovnikom, ki obdaja prsni koš. Spuščajte ga, dokler se ne prikaže izpod jopiča, nato pa pustite, da pade na tla.

Obrnite telovnik navzven, ne da bi ga odstranili z osebe.

Lastnik telovnika mora stisniti prste za hrbtom. Tisti okoli vas bi morali telovnik obrniti navzven, ne da bi ločili lastnikove roke. Za prikaz te izkušnje je potrebno telovnik odpeti in ga potegniti čez roke za hrbtom uporabnika. Telovnik bo visel v zraku, vendar se seveda ne bo snel, ker so roke sklenjene. Zdaj morate vzeti levi rob telovnika in ga poskušati ne zmečkati, potisnite čim dlje v desno roko. Nato vzemite desno luknjo za roko in jo vstavite v isto luknjo za roko in v isti smeri. Ostaja le še poravnati telovnik in ga potegniti na lastnika. Telovnik bo obrnjen navzven. Ta trik smo izvedli in posneli s sošolci. Vsebovan je v predstavitvi "Mobiusov trak".

2.3. Uporaba Möbiusovega traku

∞ Na vhodu v Muzej zgodovine in tehnologije v Washingtonu se jekleni trak, zavit za pol obrata, počasi vrti na podstavku. Leta 1967, ko je v Braziliji potekal mednarodni matematični kongres, so njegovi organizatorji izdali priložnostno znamko v apoenih po pet centavosov. Upodabljal je Möbiusov trak. Tako več kot dva metra visok spomenik kot droben žig sta edinstvena spomenika nemškemu matematiku in astronomu Augustu Ferdinandu Möbiusu.

Glej dodatek 5.

Patentna služba je registrirala veliko izumov, ki temeljijo na isti enostranski površini.

∞ Möbiusov trak se uporablja v številnih izumih, ki jih je navdihnila skrbna študija lastnosti enostranske površine. Trak tekočega traku, izdelan v obliki Möbiusovega traku, omogoča dvakrat daljše delovanje, saj se celotna površina pločevine enakomerno obrablja. Leta 1923 je bil patent izdan izumitelju Leeju de Forceu, ki je predlagal snemanje zvoka na film brez zamenjave kolutov na obeh straneh hkrati. Izumljene so bile kasete za magnetofone, kjer je trak zvit in zlepljen v obroč, kar omogoča snemanje oziroma branje informacij z obeh strani hkrati, kar podvoji kapaciteto kasete in s tem čas predvajanja. Pri matričnih tiskalnikih je bil črnilni trak oblikovan kot Möbiusov trak, da bi podaljšali rok trajanja. To zagotavlja znatne prihranke. Möbiusov trak se uporablja v kolesarskih in odbojkarskih zvočnikih.

∞ Nedavno so mu našli drugo uporabo - začel je igrati vlogo vzmeti, le posebne vzmeti. Kot veste, nabita vzmet sproži v nasprotni smeri. Mobiusov trak v nasprotju z vsemi zakoni ne spreminja smeri delovanja, kot mehanizmi z dvema stabilnima položajema. Takšna vzmet bi lahko postala neprecenljiva v igračah na navijanje – ni je mogoče zviti kot navadna – nekakšen večni gibalnik.

Glej adj. 6.

∞ Leta 1971 je izumitelj iz Urala P.N. Chesnokov. uporabil filter v obliki Mobiusovega traku.

∞ Mobiusov list se uporablja pri kuhanju za ustvarjanje zanimivega in okusnega videza žemljic, krekerjev in grmičevja. In tudi pri izdelavi orodij za pripravo in dekoracijo različnih jedi, močnostnih konstrukcij (mešalo).

Glej adj. 7.

∞ S pomočjo Möbiusovega traku nastanejo cele mojstrovine.

Möbiusov trak je služil kot navdih za kiparstvo in grafiko. Escher je bil eden od umetnikov, ki ga je še posebej ljubil in je temu matematičnemu predmetu posvetil več svojih litografij. Ena znana prikazuje mravlje, ki se plazijo po površini Möbiusovega traku.

Glej dodatek 9.

∞ Möbiusov trak se redno pojavlja tudi v znanstveni fantastiki, na primer v zgodbi Arthurja C. Clarka "The Wall of Darkness". Včasih znanstvenofantastične zgodbe nakazujejo, da je naše vesolje nekakšen posplošen Möbiusov trak. V zgodbi avtorja A.J. Deitch, bostonska podzemna železnica gradi novo progo, katere pot postane tako zmedena, da se spremeni v Mobiusov trak, po katerem začnejo vlaki na tej progi izginjati.

∞ Obstaja hipoteza, da je sama vijačnica DNK prav tako delček Mobiusovega traku in le zato je genetsko kodo tako težko razvozlati in zaznati. Poleg tega takšna struktura povsem logično pojasnjuje razlog za nastanek biološke smrti: spirala se zapre in pride do samouničenja.

Dodatek 10.

∞ Möbiusov trak ni bil všeč samo matematikom, ampak tudi čarovnikom

Že več kot 100 let se Möbiusov trak uporablja za izvajanje različnih čarovniških trikov in zabave. Neverjetne lastnosti lista so bile prikazane celo v cirkusu, kjer so viseli svetli trakovi, zlepljeni v obliki Möbiusovih trakov. Čarovnik je prižgal cigareto in se z gorečim koncem dotaknil srednje črte vsakega traku, ki je bil narejen iz kalijevega nitrata. Ognjena pot je prvi trak spremenila v daljšega, drugega pa v dva trakova, vpeta enega v drugega. (V tem primeru je čarovnik prerezal Mobiusov trak ne na sredini, ampak na razdalji ene tretjine širine).

∞ Fiziki trdijo, da vsi optični zakoni temeljijo na lastnostih Mobiusovega traku, predvsem pa je odsev v zrcalu nekakšen prenos v času, kratkotrajen, ki traja stotinke sekunde, saj vidimo pred sabo.. .tako je, naše ogledalo dvojno.

∞Obstaja hipoteza, da je naše vesolje zelo verjetno zaprto v istem Mobiusovem traku, glede na teorijo relativnosti, večja kot je masa, večja je ukrivljenost prostora. Ta teorija v celoti potrjuje domnevo, da vesoljska ladja, ki ves čas leti naravnost, se lahko vrne na izhodišče, kar potrjuje neomejenost in končnost vesolja.

Glej adj. enajst.

∞ Zanimanje za Möbiusov trak še danes ni pojenjalo. Septembra 2006 je v Moskvi potekal Festival umetniške matematike. Govor profesorja iz Tokia Jin Akiyame je bil sprejet z velikim uspehom. Njegov nastop je spominjal na iluzionistično predstavo, kjer je bilo mesto za Möbiusov trak (delo s papirjem »Möbiusov trak in njegove modifikacije«).

ŠPORT

Ročni ekspander "Robur"

Glej adj. 12.

Eden odnajljubše stvari vseh šolskih učiteljev športne vzgoje, ki po njihovempo lastnih besedah ​​»ne trenirasamo mišice roke, ampakin možgansko mišico."Karpalni ekspander izStudio Artemija Lebedeva ponavlja obliko Möbiusovega traku. Odlično zdravilo za lajšanje stresa, razmišljanje oneskončnost insamo koristen način, da zaposlite svoje roke.

PARFUMI

Parfum Bugatti

Glej adj. 13

PodjetjeBugattizačel proizvajati ne le ultra drage avtomobile (modelVeyronstane 1,3 milijona evrov), ampak tudi ... parfum. Vsaka steklenička, izdelana iz kristala in prekrita s pravim zlatom, je oblikovana v obliki nenavadnega Möbiusovega traku, ki ima samo eno stran. Cena parfumaBugattije 3500 evrov.

Parfum Loewe Quzas, Quizas, Quizas

Glej adj. 14.

Jeseni 2011 je izšla škrlatna različica dišave, katere steklenička je ovita v Mobiusov trak - simbol cikla strasti v naravi. Bogastvo kompozicije sestavljajo svežina azijskih pomaranč, bergamotke, rdečega jagodičevja, nadaljuje se s cvetličnim srcem magnolije, frezije in pomarančnih cvetnih listov ter se zaključi s čutno sledjo kašmirjevega lesa, zlatega jantarja in vetiverja.

Parfum UFO Limited Edition, Kenzo

Glej adj. 15.

Predstavitev dišavKenzoleta 2009 na retrospektivni razstavi del Rona Arada (RonArad) v centru Pompidou v Parizu. Prav ta umetnik in arhitekt se je domislil kozmične zasnove steklenice v obliki Mobiusovega traku. Zasnovan je tako, da se natančno prilega vaši dlani.NeidentificiranoDišavaObjekt, ali "Neidentificirani aromatični predmet," je omejen na samo 180 kosov in se prodaja za 188 $.

POHIŠTVO

Mobiusova tabela

Glej adj. 16

Miza z eno površino, za katero lahko udobno stojite, sedite in ležite.

Knjižna polica Infinity

Glej adj. 17.

Oblikovalec Job Kelevius je zlomil kalup, ko je oblikoval svojo knjižno omaro Infinity. Z uporabo matematičnega koncepta Lemniscate in nečesa podobnega Möbiusovemu traku je oblikovalec v Infinity Shelf utelesil fizični koncept neskončnosti. To pomeni, da če ste prebrali vse knjige na tej polici, menite, da ste dojeli vso neskončnost literature.

Kavč Mobius

Glej adj. 18.

Rojen pod motom "Dvojni stol - dvojni užitek", je sedežna garnituraMoebiusDvojnoFoteljustvaril oblikovalecGaeporjavelostkombideWyeriz Belgije in prinaša svežo vizijo pohištva za ljubitelje.

LOGOTIPI

Logotip podjetja Woolmark

Glej adj. 19.

Logotip je nastal leta 1964 kot rezultat oblikovalskega natečaja. Član žirijeFrancoGrignanini mogel upreti in ponudil svojo različico, ki se je skrivala pod psevdonimomFrancescoSeraglio. Ta logotip spominja na Mobiusov trak in je simbol večnosti in prilagodljivosti podjetja.

Simbol recikliranja

Glej adj. 20.

Mednarodni simbol za recikliranje je Möbiusov trak. Recikliranje (drugi izrazi: recikliranje, recikliranje odpadkov, recikliranje in recikliranje)- ponovno uporabo ali vrnitev v promet industrijskih odpadkov ali smeti. Najpogostejši so sekundarni, terciarni in T. e. recikliranje v takšnem ali drugačnem obsegu materialov, kot so steklo, papir, aluminij, asfalt, železo, tkanine in različne vrste plastike. Že od antičnih časov se uporablja tudi v kmetijstvo organski kmetijski in gospodinjski odpadki.

Matematični simbol

Glej adj. 21.

Möbiusov trak velja za simbol sodobne matematike, saj je prav on dal zagon novim matematičnim raziskavam.

OBLAČILA IN OBUTEV

Čevlji

Glej adj. 22.

Leta 2003 sta ga ustanovila arhitekt Ram Di Koolhaase in čevljar Galahad ClarkZdruženogolaje specializirano za proizvodnjo inovativnih dizajnerskih čevljev. Eden najuspešnejših razvojev podjetja so čevljiMobius , poimenovan po geometru Augustu Möbiusu in njegovi zamisli o enostranski ploskvi. Ideja čevljev je naslednja: usnjeni zgornji del čevljev in podplat sta en sam trak, zavit na določen način.

Mobiusov šal

Glej adj. 23.

Zanimiv je Möbiusov šal, ki se pojavlja v omarah 21. stoletja. Möbiusov šal lahko izdelate sami, tako da konce šala zavežete in zasukate za en obrat.

SLIKA

Grafiti

Glej adj. 24.

Sodoben Möbiusov trak je naslikan na steni v Pragi na Češkem.

 Po traku se premikata dve vrsti vozil: cisterne in oprema za gradnjo cest moderna civilizacija: uniči-zgradi-uniči-zgradi..

ARHITEKTURA

Stavba knjižnice

Glej adj. 25.

Trenutno se obravnava projekt izgradnje knjižnice v obliki Mobiusovega traku v Kazahstanu.

Krivulje stavbe tvorijo Möbiusov trak, s čimer se notranji prostor preliva v zunanjega in obratno; na podoben način se stene spremenijo v streho, streha pa spet v stene. Naravna svetloba vstopa v notranje hodnike skozi geometrijske odprtine v zunanji lupini, kar ustvarja čudovito osvetljene prostore, idealne za branje.

Zanimivosti

Glej adj. 26.

Vožnja s toboganom spominja na obliko Mobiusovega traku. V Moskvi je največji obrnjeni tobogan na svetu, kjer človek sedi na visečem stolu in ima noge v zraku. Hitrost - 81 km / h, višina 30 m, v primerjavi s tujimi analogi je majhna, vendar se več kot izplača z obilico spiral, obročev in zank.

Filmski kolut

Glej adj. 27.

Leta 1923 je bil izdan patent izumitelju Leeju de Forceu, ki je predlagal snemanje zvoka na film brez menjave kolutov, z obeh strani hkrati.

Kaseta

Glej adj. 28.

Za magnetofone so izumili kasete, kjer je trak zvit in zlepljen v obroč, kar omogoča snemanje oziroma branje informacij z obeh strani hkrati, kar poveča kapaciteto kasete in s tem čas predvajanja.

Avto Toyota MOB

Glej adj. 29.

Möbiusov trak je oblikoval španski oblikovalec Jorge Marti Vidal in združuje lepoto in skrivnostnost Möbiusovega traku. Edinstvena oblika karoserije zagotavlja dirkalniku dobro aerodinamiko

Matrični tiskalnik

Glej adj. trideset.

V mnogih matričnih tiskalnikih ima črnilni trak tudi obliko Mobiusovega traku, da poveča svojo življenjsko dobo.

Möbiusov upor

Glej adj. 31.

To je na novo izumljen elektronski element, ki nima lastne induktivnosti.

Brusni trak

Glej adj. 32.

Leta 1969 je sovjetski izumitelj Gubaidullin predlagal neskončni brusni trak v obliki Möbiusovega traku.

Zaključek

Möbiusov trak je prva enostranska površina, ki jo je odkril znanstvenik. Kasneje so matematiki odkrili celo vrsto enostranskih ploskev. Ampak

ta je prvi, ki je postavil temelje celotni smeri v geometriji in še naprej pritegne pozornost znanstvenikov, izumiteljev, umetnikov in naših študentov. Zelo so me zanimale odkrite lastnosti Möbiusovega traku:

Möbiusov trak ima en rob, eno stran

Möbiusov trak je topološki objekt. Kot vsaka topološka figura ne spremeni svojih lastnosti, dokler je ne razrežemo, raztrgamo ali njenih posameznih kosov zlepimo skupaj.

En rob in ena stran Mobiusovega traku nista povezana z njegovim položajem v prostoru in nista povezana s pojmi razdalje.

Möbiusov trak najde številne aplikacije v kulinariki, tehnologiji, fiziki, slikarstvu, arhitekturi, oblikovanju nakita in preučevanju lastnosti vesolja. Navdihnil je ustvarjalnost številnih pisateljev in umetnikov.

μ( n) je definiran za vsa naravna števila n in ima vrednosti glede na naravo razširitve števila n na preproste dejavnike:

• μ( n) = 1 če n brez kvadratov (tj. nobeno praštevilo ni deljivo s kvadratom) in razčlenitev n sodo število faktorjev;
• μ( n) = − 1 če n brez kvadratov in razkroja n v prafaktorje je sestavljen iz lihega števila faktorjev;
• μ( n) = 0 če n ni brez kvadratov.

Po definiciji predpostavljamo tudi μ(1) = 1.

Lastnosti in aplikacije

Möbiusova funkcija je multiplikativna: za poljubna soprosta števila a in b enakost velja μ( ab) = μ( a)μ( b) .

Vsota vrednosti Möbiusove funkcije nad vsemi delitelji celega števila n, ni enako ena, je enako nič

Style="max-width: 98%; height: auto; width: auto;" src="/pictures/wiki/files/49/1bee8d0f6bd91176912a8cedc63e174b.png" border="0">

Iz tega zlasti sledi, da je za vsako neprazno končno množico število različnih podmnožic, ki jih sestavljajo liho število elementov je enako številu različnih podmnožic, sestavljenih iz sodega števila elementov - dejstvo, uporabljeno v dokazu.

Möbiusova funkcija je povezana z Mertensovo funkcijo z razmerjem

Mertensova funkcija pa je tesno povezana s problemom ničel Riemannove funkcije zeta, glej članek Mertensova hipoteza.

Mobiusova inverzija

Prva Möbiusova inverzijska formula

Za aritmetične funkcije f in g ,

g(n) =	∑	f(d)
	d | n

takrat in samo takrat

.

Druga Möbiusova inverzijska formula

Za funkcije z realnimi vrednostmi f(x) In g(x) določeno pri ,

takrat in samo takrat

.

Tu se znesek razlaga kot .

Fundacija Wikimedia. 2010.

Oglejte si, kaj je "Mobiusova funkcija" v drugih slovarjih:

Möbiusova funkcija μ(n) je multiplikativna aritmetična funkcija, ki se uporablja v teoriji števil in kombinatoriki, poimenovana po nemškem matematiku Möbiusu, ki jo je prvi obravnaval leta 1831. Vsebina 1 Definicija 2 Lastnosti in aplikacije ... Wikipedia

Möbiusova funkcija μ(n) je multiplikativna aritmetična funkcija, ki se uporablja v teoriji števil in kombinatoriki, poimenovana po nemškem matematiku Möbiusu, ki jo je prvi obravnaval leta 1831. Vsebina 1 Definicija 2 Lastnosti in aplikacije ... Wikipedia

Vrsta transformacij na kompleksni ravnini (siva) in Riemannovi krogli (črna) Vsebina 1 Definicija 2 Algebraične lastnosti... Wikipedia

Delno linearna funkcija funkcija oblike, kjer so z = (z1,...,zn) kompleksne ali realne spremenljivke, ai,b,ci,d kompleksni ali realni koeficienti. Pogosto se izraz "frakcijska linearna funkcija" uporablja za poseben primer transformacije... ... Wikipedia

Möbiusova vrsta je funkcionalna vrsta oblike To vrsto je proučeval Möbius, ki je našel inverzijsko formulo za to vrsto: kjer je μ(s) Möbiusova funkcija ... Wikipedia

METODE MEDICINSKEGA RAZISKOVANJA- JAZ. Splošna načela medicinskih raziskav. Rast in poglabljanje znanja, vse večja tehnična opremljenost klinike, ki temelji na uporabi najnovejših dosežkov fizike, kemije in tehnologije, s tem povezano zapletanje metod... ... Velika medicinska enciklopedija

Patološko stanje, ki se je razvilo med porodom in za katerega je značilna poškodba tkiv in organov otroka, ki jo praviloma spremlja motnja njihovih funkcij. Dejavniki, ki povzročajo nagnjenost k razvoju tako imenovane R., so netočni... ... Medicinska enciklopedija

Lema.

Dokaz. Kajti izjava je očitna. Naj in je kanonična razširitev števila . Potem, ob upoštevanju, da imajo delitelji obliko , kjer je , ,…, ; , dobimo

zaradi

Izrek. (Aditivna Möbiusova inverzijska formula.) Naj in sta funkciji naravnega argumenta . Potem, če

Dokaz. Imamo

Pustiti . Nato fiksni teče skozi vse vrednosti deliteljev števila. To pomeni, da se seštevalni predznaki v zadnji dvojni vsoti lahko obrnejo, tj.

Zdaj, glede na to

dobimo

Obstaja še ena oblika dokazanega izreka:

Izrek. (Formula multiplikativne Möbiusove inverzije.) Pustiti

kjer simbol označuje zmnožek, razširjen na vse delitelje števila.

Dokaz:

Primeri uporabe formule Möbiusove inverzije:

Problem s številom zaporedij zvonjenja. Glej: Hall M. Kombinatorika. M.: Mir, , § .

Število nereducibilnih polinomov dane stopnje nad končnim poljem elementov. Glej: Berlekamp E. Algebraic coding theory. − M.: Mir, 1970, pogl. 3.

Glukhov M. M., Elizarov V. P., Nechaev A. A. Algebra. V t. M.: Helios, . T., §.

Za samostojno učenje :

Möbiusova inverzija na delno urejenih množicah. Načelo vključitve-izključitve poseben primer Möbiusove inverzijske formule. Glej: Hall M. Kombinatorika. M.: Mir, , § ; Bender E., Goldman J. O aplikacijah Möbiusove inverzije v kombinatorični analizi. V knjigi: Enumerativni problemi kombinatorične analize. M.: Mir, 1971. S. - .

Primerjave številskih kombinacij

Naj bo praštevilo.

Lema.

Dokaz. Ko je števec v formuli

Posledica.

Dokaz.

Lema. Naj , , , so nenegativna cela števila, in naj , . Potem

Dokaz. Imamo

Na drugi strani,

Če primerjamo koeficiente pri enakih stopinjah, dobimo zahtevani rezultat. ∎

− predstavitve nenegativnih celih števil in korena. (Tukaj je katero koli celo število, za katerega , ). Na množici nenegativnih celih števil definiramo relacijo delnega reda (relacijo prednost), ob predpostavki, če in samo če

Lucasov izrek ( ).

Dokaz. Glede na prejšnjo lemo,

Kje , . Z večkratno uporabo leme ustrezno število krat dobimo zahtevani rezultat. ∎

Komentiraj. Izrek ne velja za nepraštevilne. Na primer (glej Berlekamp, ​​​​str.),

Posledica.

II . Algebraične strukture

II. 1. Množice z binarnimi operacijami. Grupoidi, polgrupe, monoidi

Binarna algebraična operacija(oz zakon sestave) na neprazni množici S imenovano kartiranje : , povezovanje para elementov z enolično definiranim elementom. Na nizu je mogoče določiti veliko operacij. (Če je npr. seveda, potem je število načinov enako , kjer je število elementov v .) Če želite na primer izpostaviti enega od njih, napišite , . Tak predmet se imenuje binarna algebra, oz groupoid. Namesto , pogosto pišejo , samo operacijo pa označujejo s kakšnim simbolom ( , , itd.).

Komentiraj. Poleg binarnih operacij se upoštevajo bolj splošne -arne operacije (unarni at, ternarni at itd.). Z njimi povezane algebraične strukture (sistemi) predstavljajo predmet raziskovanja ti. univerzalne algebre.

Pokliče se binarna operacija na množici asociativno, Če

, za katero koli , , .

Grupoid z asociativno operacijo imenujemo polskupina.

Primer neasociativnega groupoida. Na nizu definiramo operacijo kot . Operacija ni asociativna: , ampak .

Izrek.Če je binarna operacija na nizu asociativna, potem vrednost izraza ni odvisna od postavitve oklepajev v njej.

Dokaz. Z ali je izjava očitna. Kajti zadostuje, da z uporabo indukcije pokažemo, da

za katero koli,. Po indukcijski hipotezi je postavitev oklepajev v

Ni pomembno; še posebej, .

Če, potem.

Če, potem

Na isto obliko je reducirana tudi desna stran enakosti, ki jo dokazujemo (1). ∎

Element se imenuje nevtralen glede operacije, če

za kogarkoli.

Polskupina z elementom se imenuje monoid(oz polskupina z identiteto) in označujejo , , .

Polskupina (groupoid) ima lahko največ en nevtralni element: if

, so torej nevtralni elementi

Grupoid (polskupina) se imenuje subgroupoid (podpolskupina) skupinoid (polskupina), , če

In za katero koli,.

V tem primeru pravijo, da podmnožica zaprto v obratovanju. Monoid se imenuje submonoid monoid , , , če in .

Element monoida, , se imenuje reverzibilen, če obstaja tak element, da (očitno, potem ga bomo obrnili). Če ima element enako lastnost, tj. , potem iz enakosti sledi, da je element dejansko edinstven (glede na ). To nam omogoča, da govorimo o vzvratno element , v (obrnljiv) element , z lastnostmi: , .

Če so , invertibilni elementi monoida , , , potem je njihov produkt tudi invertibilen element, saj , . Očitno gre za obrnljiv element. Zato obstaja

Izrek. Množica vseh invertibilnih elementov monoida , , je zaprta glede na operacijo ∗ in tvori submonoid v , , .

Skupine

Opredelitev skupine. Imenuje se monoid , , , katerega vsi elementi so invertibilni skupina.

Z drugimi besedami, skupina je množica z binarno operacijo, za katero veljajo naslednji aksiomi:

. (Zaprto delovanje.) , .

. (Asociativnost delovanja.) ,

. (Obstoj nevtralnega elementa.) ∃ .

. (Obstoj inverznega elementa.) .

Komentiraj.Če se vrnemo k zgoraj predstavljenim algebraičnim strukturam, opazimo med njimi naslednjo hierarhijo: par , je groupoid, če je aksiom izpolnjen; polskupina, če aksiomi in ; monoid, če aksiomi , in ; skupina, če so aksiomi , , in .

Stopnje elementov z očitnimi lastnostmi se določijo na naraven način:

(enkrat),

; , ( , , .

Na splošno je elementov v izrazu nemogoče preurediti (tj. ). če , nato se pokličejo elementi premenljiv, oz prevoz na delo. Če se katera koli dva elementa skupine vozita na delo, se skupina pokliče komutativni, oz abelski(v čast norveškemu matematiku Riehlu Henriku Abelu ( - )).

Operacija v skupini je največkrat označena s simbolom (seštevanje) ali simbolom (množenje). V tem primeru se skupina ustrezno pokliče aditiv oz multiplikativen, njegov nevtralni element je oz nič() oz enota(). V aditivni skupini se imenuje element, inverz elementa nasprotje in je označen , ampak namesto tega pišejo . V množilni skupini običajno pišejo namesto, pri čemer izpustijo simbol operacije.

Primeri aditivnih skupin. 1) , , , , , , , so aditivne skupine obroča in polj , , . Pišejo preprosto , , , . 2) Vsak obroč z dodatkom je Abelova skupina. Zlasti obroč polinomov ,…, ] in obroč matrik reda nad poljem sta Abelovi skupini. 3) Kateri koli vektorski prostor nad poljem glede na seštevanje je Abelova skupina. 4) , 1,…, – popoln sistem najmanjših nenegativnih modulo ostankov z operacijo modulo seštevanja.

Primeri multiplikativnih skupin. 1) , , so multiplikativne skupine polj , , . 2) je množica invertibilnih elementov katerega koli obroča z enoto pri množenju. Zlasti = ; , je množica invertibilnih matrik iz . 3) − vse (prave in kompleksne) korenine

, , 1,…, , − namišljena enota,

enačba je multiplikativna Abelova skupina. 4) - množica vrtenja pravilnega -kotnika v ravnini in v prostoru - nekomutativna skupina (za ).

Nadalje se pogosteje uporablja multiplikativna oblika zapisa operacije. Skupina je običajno označena z eno samo črko brez navedbe operacije. Množica vseh elementov skupine se imenuje glavni sklop skupine in je označen z isto črko. Če je osnovna množica končna, se imenuje skupina končni; drugače se imenuje neskončno. Število elementov končne skupine se imenuje njeno v redu. Pokliče se skupina reda 1 samski, ali T rivial. Rečeno je, da ima neskončna skupina neskončni red . Za označevanje vrstnega reda skupine (kardinalnost glavnega niza) se uporabljata enaka simbola Kartica (kardinalno število) in ().

Če so podmnožice (glavne množice) skupine, potem postavimo

, , .

Podskupina skupine je podmnožica, v kateri je sama skupina glede na isto operacijo kot v . Z drugimi besedami, podmnožica je podskupina, če in samo če ( ena v ) in je zaprta za množenje in recipročnost, tj. , (pravzaprav so tu celo enakosti). Če je podskupina v , potem napišite ; če hkrati, potem se imenuje lasten podskupina in to je označeno kot .

Möbiusova funkcija  (n), Kje n– naravno število, ima naslednje vrednosti:

Möbiusova funkcija vam omogoča, da zapišete Eulerjevo funkcijo kot vsoto:

Seštevek velja za vse delitelje števila n (in ne samo za pradelilnike).

Primer. Izračunajmo φ (100) z uporabo Möbiusove funkcije.

Vsi delitelji števila 100 so (1, 2, 4, 5, 10, 20, 25, 50, 100).

(2) = (-1) 1 = -1 (dva ima en pradelilnik – 2)

(4) = 0 (4 je deljeno s kvadratom dva)

(5) = (-1) 1 = -1 (5 ima en pradelilnik – 5)

(10) = (-1) 2 = 1 (10 ima dva pradelilnik– 2 in 5)

(20) = 0 (20 deljeno s kvadratom dva)

(25) = 0 (25 deljeno s kvadratom pet)

(50) = 0 (50 je deljivo z 2 2 in 5 5)

(100) = 0 (100 je deljivo z 2 2 in 5 5)

torej

Lastnost Möbiusove funkcije:.

npr. n=100, {1, 2, 4, 5, 10, 20, 25, 50, 100}.

16 Izrek o številu načinov za izbiro k-elementov, med katerimi ni dveh sosednjih, iz n elementov, postavljenih v vrsto. Dokaži tako, da dobiš formulo ponovitve.

17 Število kombinacij s ponovitvami

številka r-kombinacije s ponovitvami iz n- nizi so enaki

.

– dokaz z uporabo recidivne formule.

Metoda temelji na pridobivanju formule, ki vam omogoča, da korak za korakom izračunate vrednosti želene količine na podlagi znanih začetnih vrednosti in vrednosti, izračunanih v prejšnjih korakih.

Formula ponovitver -th red– formula obrazca

a n = f(n, a n- 1 , a n- 2 , … , a n-r).

Formula izraža pri n>r vsak član zaporedja ( a jaz) prek prejšnjega rčlani. Konstrukcija ponavljajoče se formule je sestavljena iz naslednjih korakov.

1. Proizvodnja začetni pogoji na podlagi kakršnih koli očitnih odnosov.

Označimo z f(n,r). To je očitno

2. Logično sklepanje. Popravimo kakšen element v nizu S. Potem glede na katerokoli r- kombinacije s ponovitvami iz n-kompletov S lahko ugotovimo, ali vsebuje določen fiksni element ali ne.

če vsebuje, potem ostalo ( r-1) element lahko izberete f(n,r-1) načine.

če ne vsebuje(tega elementa ni v izboru), torej r- kombinacija sestavljena iz elementov ( n-1)-množice (niz S razen tega fiksnega elementa). Število takih kombinacij f(n-1,r).

Ker ti primeri se med seboj izključujejo, potem po pravilu vsote

3. Preverjanje formule na nekaterih vrednostih in sklepanje splošnega vzorca.

1) Izračunajmo f (n ,0) . Iz (2) sledi

Potem f(n,0)=f(n,1)-f(n-1,1). Od (1) f(n,1)=n, f(n-1,1)=n-1.

torej f(n,0)=n-(n-1)=1=.

2) f (n ,1) =f(n,0)+f(n-1,1) = 1+n- 1 =n==.

3) f (n ,2) =f(n,1)+f(n-1,2) =n+f(n-1,1)+f(n-2,2) =n+(n-1)+f(n-2,1)+f(n-3,2) = … =

= n+(n-1)+…+2+1 =.

(vsota aritmetične progresije)

4) f (n ,3) =f(n,2)+f(n-1,3) =+f(n-1,2)+f(n-2,3) =++f(n-2,2)+f(n-3,3) = … =

(vsota geometrijske progresije)

5) f (n ,4) =

Na podlagi posameznih primerov je mogoče sklepati, da

4. Preverjanje začetnih pogojev z dobljeno formulo.

,

kar je skladno z (1) #

19, 20) Število binarnih dreves z n vozlišči je enako C(n), kjer je C(n) n-to katalonsko število.

Število binarnih dreves z n vozlišči se imenuje katalonsko število, ki ima veliko zanimivih lastnosti. N-to katalonsko število se izračuna po formuli (2n)! / (n+1)!n!, ki eksponentno raste. (Wikipedia ponuja več dokazov, da je to oblika katalonskega števila.) Število binarnih dreves dane velikosti 0 1 1 1 2 2 4 14 8 1430 12 208012 16 35357670

Zamenjava

Pojdi do: navigacijo, Iskanje

To je članek o zamenjavi kot sintaktični operaciji naterme . Morda bi vas zanimalopreureditev .

IN matematika in Računalništvo zamenjava- to je operacija sintaktični zamenjava podpojmov danega terma drugih pogojih, po določenih pravilih. Običajno govorimo o zamenjavi izraza namesto spremenljivka.

Definicije in oznake

Ni univerzalne, dogovorjene oznake za zamenjavo, niti standardne definicije. Koncept zamenjave se razlikuje ne le znotraj rubrik, temveč tudi na ravni posameznih publikacij. Na splošno lahko izpostavimo zamenjava konteksta in zamenjava "namesto". V prvem primeru je navedeno mesto v izrazu, kjer pride do zamenjave kontekstu, torej del terme, ki »obdaja« ta kraj. Zlasti se ta koncept zamenjave uporablja v prepisovanje. Druga možnost je pogostejša. V tem primeru je substitucija običajno določena z neko funkcijo iz niza spremenljivk v niz izrazov. Navesti nadomestna dejanja, praviloma uporabljajo postfiksni zapis. Pomeni na primer rezultat zamenjave izraza.

V veliki večini primerov se zahteva, da ima substitucija končen nosilec, to je, da množica je bil končen. V tem primeru ga je mogoče določiti tako, da preprosto navedete pare "vrednost-spremenljivka". Ker je vsako takšno zamenjavo mogoče reducirati na zaporedje zamenjav, ki nadomestijo samo eno spremenljivko, lahko brez izgube splošnosti domnevamo, da je zamenjava podana z enim parom "vrednost-spremenljivka", kar se običajno naredi.

Zadnja definicija substitucije je verjetno najbolj značilna in pogosto uporabljena. Vendar tudi zanj ni enotnega splošno sprejetega zapisa. Najpogosteje se uporablja za označevanje zamenjave a namesto x V t uporablja se snemanje t[a/x], t[x:=a] oz t[x←a].

Zamenjava spremenljivke vλ-račun

V λ-računu je substitucija določena s strukturno indukcijo. Za poljubne objekte in poljubno spremenljivko se izračuna rezultat zamenjave poljubne proste pojavitve zamenjava in je določen z indukcijo na konstrukcijo:

(i) osnova:: predmet se ujema s spremenljivko. Potem;

(ii) osnova:: predmet se ujema s konstanto. Potem za poljubne atomske;

(iii) korak: : objekt ni atomski in ima videz aplikacije. Potem;

(iv) korak:: objekt ni atomski in je abstrakcija. Nato [;

(v) korak:: predmet je neatomski in je poleg tega abstrakcija. Nato:

za andor;

Zamenjava spremenljivk v programiranju

Zamenjava spremenljivka ( angleščina zamenjava) V aplikativno programiranje se razume takole. Za izračun vrednosti funkcije f na argument v vnos je uporabljen f(v)), Kje f določen z zasnovo f(x) = e. Zapis f(v) v tem primeru pomeni, da v izrazu e se dogaja zamenjava, ali zamenjava spremenljivke x na v. Zamenjava se izvede v skladu z semantika izračunov.

Zamenjava spremenljivka ( angleščina dodelitev) V programiranje razumeti kot dodelitev. Operator dodelitve je manifestacija von Neumannovega učinka ozkega grla za tradicionalne programske jezike . Brez tega aplikativni računalniški sistemi.

http://math.nsc.ru/LBRT/u3/bard/fails/Brenner_Evans.pdf

21 Generiranje funkcij.Generatorska funkcija (števec) in števalna tvorna funkcija za kombinacije brez ponovitev.

Generatorske funkcije: 1) Z-transformacije 2) generator 3) generirna funkcija 4) generirajoča funkcija zaporedja (a r ) na bazi (g r ) - funkcija f, ko jo razširimo v vrsto funkcij fiksne baze (g r ), nastane to zaporedje koeficientov (a r ). …………*)

Ta serija je formalna. Ime formalno pomeni, da formulo *) obravnavamo kot priročen zapis za naše zaporedje - v tem primeru ni pomembno, za katere (dejanja in kompleksne) vrednosti konvergira. Vloga t je zmanjšana na razlikovanje koeficientov zaporedja A0, A1,…Ar….zato se v teoriji generiranih funkcij vrednosti te serije nikoli ne izračunajo za določeno vrednost spremenljivke t. Nad takšnimi nizi se izvedejo samo nekatere operacije, nato pa se določijo samo nekatere operacije na takih nizih, nato pa se določijo koeficienti za posamezne potence spremenljivke t.

Ponavadi kot

22 Generatorska funkcija. Generatorska funkcija (števec) in števalna tvorna funkcija za kombinacije s ponovitvami.

Proizvodni obrat za:

Pravilo gradnje

1) Če je element tipa i mogoče vključiti v kombinacije K 1 ali K 2 ali ... K i-krat, potem ima ustrezen množitelj

3) Še vedno je treba najti koeficient. pri

eksponentna generirajoča funkcija za pravilo konstrukcije umestitev

25) Kombinatorna števila vključujejo tudi Stirlingove številke prve in druge vrste. Ta števila so definirana kot koeficienti v enačbah

in imajo preprost kombinatorni pomen - enako številu elementov permutacijske skupine, ki so produkti točno k disjunktnih ciklov in enako številu particij n- vklopljen element k neprazne podmnožice. To je očitno. Podobna vsota Stirlingovih števil druge vrste se imenuje n- Številka zvonca in enaka številu vseh particij n- komplet elementov. Rekurentna formula velja za Bellova števila.

Pri reševanju kombinatoričnih problemov je pogosto uporaben formula vključitve-izključitve

ki omogoča najti kardinalnost unije množic, če je znana kardinalnost njihovih presečišč. Uporabimo vključitveno-izključitveno formulo, da dobimo eksplicitno formulo za Stirlingova števila druge vrste.

Stirlingova števila prve vrste

Gradivo iz Wikipedije - proste enciklopedije

Pojdi do: navigacijo, Iskanje

Stirlingova števila prve vrste(nepodpisano) - količina permutacije naročilo n z k ciklov.

Opredelitev

Stirlingova števila prve vrste(z znakom) s(n, k) se imenujejo koeficienti polinom:

Kje ( x) n - Pochhammer simbol (padajoči faktoriel):

Kot je razvidno iz definicije, imajo številke izmenične znake. Njihove absolutne vrednosti določajo število permutacije komplet sestavljen iz n elementi z k ciklov.

Rekurenčna relacija

Podana so Stirlingova števila prve vrste ponavljajoče se razmerje:

s(n,n) = 1, za n ≥ 0,

s(n,0) = 0, za n > 0,

za 0< k < n.

Dokaz.

Za n=1 se ta enakost preveri neposredno. Naj bo permutacija ( n-1) red razpade na k ciklov. številka n lahko dodate za katero koli številko v ustrezni zanki. Vse nastale permutacije so različne in vsebujejo k ciklov, njihovo število ( n-1)· s(n-1, k). Iz katere koli permutacije ( n-1)th naročilo, ki vsebuje k-1 cikel, se lahko oblikuje ena permutacija n naročilo, ki vsebuje k cikle z dodajanjem cikla, ki ga tvori ednina n. Očitno ta konstrukcija opisuje vse permutacije n-th naročilo, ki vsebuje k ciklov. Tako je enakost dokazana.

Primer

Prve vrste:

IN kombinatorika Stirlingovo število druge vrste od n Avtor: k, označeno z ali, je število neurejenih predelne stene n- elementarni kompleti na k neprazne podmnožice.

Formula ponovitve

Stirlingova števila druge vrste izpolnjujejo ponavljajoče se razmerje:

Za n ≥ 0,

Za n > 0,

Eksplicitna formula

Primer

Začetne vrednosti Stirlingovih števil druge vrste so podane v tabeli:

Lastnosti

Dvojno Preslikava je preslikava, ki ima lastnosti, da je hkrati injektivna in surjektivna.

1. Najprej si opomnimo definicijo pomembne številsko teoretične Möbiujeve funkcije

1, če je n = 1

µ (n)=0, če obstaja praštevilo p, p2 n (-1)k, če je n = p1 ... pk je produkt k različnih praštevil.

Dokažimo glavno lastnost Möbiusove funkcije:

1. izrek.

♦ Če je n = 1, potem je edini delitelj d = 1 in (1) velja, ker µ (1) = 1. Naj bo n > 1. Predstavimo ga v obliki

n = p1 s 1 ps 2 2 K ps k k ,

kjer so pi, i 1, k praštevila, si njihove potence. Če je d delitelj n, potem je d = p1 d 1 pd 2 2 K pd k k ,

kjer je 0 ≤ di ≤ si, i 1, k. Če je di > 1 za nek i 1, k, potem je µ (d) = 0. To pomeni, da moramo v (1) upoštevati samo tiste d, za katere je di ≤ 1, i 1, k. Vsak tak delitelj so-

je sestavljen iz produkta r različnih praštevil, kjer je r 1, k, in njegovega prispevka k vsoti

(1) je enako (-1)r in vseh je k. Tako dobimo

			µ (d) = 1 −	K + (− 1) k	0. ♦
			Izrek 2. (Mobiusova inverzijska formula). Naj sta f(n) in g(n) funkciji naravnega
ralni argument. Potem pa enakost
					∑f(d)
je resnična, če in samo če je enakost resnična
					∑ µ (d)g(

♦ Naj velja (2) za vsak n. Potem

g(d n ) = ∑ f(d′ )

d ′ d n

Če zamenjamo desno stran (3), dobimo

∑ µ (d)g(			) = ∑ µ (d) ∑ f(d′ )
					d′

Dvojno seštevanje na desni se izvede po vseh parih d, d′, tako da je d d′ n. Če izberete d ′, bo d tekel skozi vse delilnike d n ′. torej

∑ µ (d)g(

) = ∑ f(d′ ) ∑ µ (d′ )

d′

d′

d′

n > d′

Toda glede na (1) imamo ∑

µ (d′ ) =

n = d′

d′

d′

To pomeni, da je vzpostavljena enakost (3). Naj zdaj velja (3) za vsak n. Potem

∑ f(d) =

∑ ∑ µ (d′ )g(

) , d′′ = d d ′ - je delitelj n in dvojna vsota lahko

d′

n d′

prepisati kot

∑ µ (d′ )g(d′′ ) =

∑ g(d′′ )

∑ µ (d′ )

d''

n d ′

d''

d''

d′

d''

V skladu z (1) se zadnja vsota spremeni v enoto v primeru d′′ = n, v ostalih primerih

V vsakem primeru je nič. To dokazuje (2). ♦ 2. Razmislite o uporabi Möbiusove inverzije.

Naj bo dana abeceda A s črkami. V dani abecedi je sn besed dolžine n. Za vsako besedo w0 = a1 a2 … lahko definiramo n - 1 besed

w1 = a2 a3 … an a1 , w2 = a3 a4 … a1 a2 , … , wk-1 = an a1 … an-1 , pridobljeni drug od drugega s cikličnimi premiki. Na množici vseh besed sn uvedemo ekvivalenčno relacijo: dve besedi razglasimo za enakovredni, če je ena pridobljena iz druge s cikličnim premikom. Zanimalo nas bo število razredov, ki vsebujejo točno n besed. Ta problem se pojavi v teoriji sinhroniziranja kod.

Besedo w bomo imenovali degenerirana, če je ekvivalenčni razred, ki vsebuje w, sestavljen iz manj kot n besed. W imenujemo periodično, če beseda u obstaja in naravno število m, tako da je w = u u … u (m-krat).

Izrek 3. Beseda w je periodična, če in samo če je izrojena.

kot u lahko vzamemo a 1 a 2 … a p in kot m =

♦ Jasno je, da če je w periodičen, potem je degeneriran. Naj bo w degeneriran. Naj bo p najmanjše celo število tako, da je w = wp. Potem, če

w = a1 a2 … an , potem je wp = a1+p a2+p … an+p (indeksi po modulu n). Od tu dobimo to v n p . (Zlahka je videti, da p n). ♦ Ozadje

pomembno skozi M(d) - število kvadratov, ki vsebujejo d besed. Iz prejšnjega imamo

d n. Tako je formula veljavna∑ dM(d) = s n . d n

Uporabimo Möbiusovo inverzijsko formulo za primer g(n) = sn , f(d) = dM(d). Potem dobimo

nM(n) = ∑ µ (d)s n d d n

∑ µ (d)sn d

Tako je M(n) število, ki nas zanima. Če je n = p praštevilo, potem

− s)

Obstaja multiplikativna različica Möbiusove inverzije. Pošteno

Izrek 4. Naj sta f(n) in g(n) ustrezno povezani funkciji naravnega argumenta

nošenje

f(n) = ∏g(d)

µ(n

g(n) = ∏ f(d)

in obratno pa iz (5) sledi (4).

Z uporabo Möbiusove inverzijske formule je mogoče rešiti praktično pomemben problem števila nezmanjšljivih polinomov fiksne stopnje nad končnim poljem. Naj bo GF(q) polje q elementov in m naravno število. Potem za številko

Φ m (q) nereducibilnih polinomov nad poljem GF(q) velja naslednja formula:

Predstavimo tabelo prvih nekaj vrednosti funkcije Φ m (2)

Φ m (2)

§ 5. Permanentne in njihova uporaba na enumerativne

1. Permanente se uporabljajo za reševanje številnih kombinatoričnih problemov. Razmislite o numerični matriki

A = (ai, j), i = 1, n, j = 1, m, n ≤ m

Permanentna matrika A (oznaka - per A) je določena z enakostjo

na A = ∑			a 2 j L a nj
(j1 ,K , jn )

kjer se seštevanje izvaja po vseh n-permutacijah m elementov 1, 2, m. Z drugimi besedami, stalnica matrike je enaka vsoti produktov elementov, vzetih po enega iz vsake vrstice in različnih stolpcev.

Iz formule (1) sledi nekaj očitnih lastnosti permanenta, podobnih lastnostim determinante za kvadratne matrike.

1. Če ena od vrstic(n× m) matrika A (n ≤ m) je sestavljena iz ničel, potem je per A = 0. Za n = m enako velja za stolpce.

2. Ko vse elemente ene od vrstic matrike A pomnožimo z določenim številom, se vrednost permanenta A pomnoži z istim številom.

3. Permanent se ne spremeni, ko so njegove vrstice in stolpci preurejeni.

Z Aij označimo matriko, ki jo dobimo iz A z brisanjem i-te vrstice in j-tega stolpca.

4. Velja formula za razgradnjo permanenta v i-ti vrsti: per A = ai1 per Ai1 + ai2 per Ai2 + ... + aim per Aim (2)

tako so številne lastnosti trajnic podobne lastnostim determinant.

Vendar pa glavna lastnost determinant det(A B) = detA detB ni izpolnjena za permanente in ta okoliščina zelo oteži njihov izračun.

npr.

					2, per
Vendar pa 4 = per						≠ per

Oglejmo si eno najpomembnejših aplikacij koncepta permanenta v kombinatoričnih problemih.

dachas Naj bo X = (x1, xm) končna množica in X1, …, Xn sistem podmnožic

V tem primeru naj bi element xi predstavljal množico Xi. Potreba po iskanju sistema različnih predstavnikov se pojavi pri reševanju številnih uporabnih problemov. Razmislite o naslednjem problemu kodiranja. Naj bo kakšen predlog, t.j. urejen nabor besed v neki abecedi. Ta stavek je treba kodirati tako, da je vsaki besedi dodeljena ena črka in ta črka mora biti del te besede, različne črke pa morajo ustrezati različnim besedam.

Primer: stavek a bc ab d abe c de cd e je mogoče kodirati kot abecd. Hkrati pa stavka ab ab bc abc bcd ni mogoče zakodirati na ta način, saj prve štiri besede skupaj vsebujejo le tri črke.

Za sistem množic X1 , … , Xn definiramo incidenčna matrika A = (aij), i = 1, n,

				1 če xi
		a ij =
				0 drugače.
		Pošteno
		Izrek 1. Naj bo A = (aij), i =					(n ≤ m) incidenčna matrika

množice X1, …, Xn, kjer je Xi X, i = 1, n, X = (x1, …, xm). Potem za število sistemov

osebnih predstavnikov R(X1 , … , Xn ) množic X1 , … , Xn velja naslednja enakost:

R(X1, …, Xn) = na A

♦ Dejansko, ker je v matriki A element aij = 1, če sta xj Xi in aij = 0,

če xj

K, xi

) elementi X je sistem različnih pred-

Xi , nato niz (xi

pripone za X1 , … , Xn

če in samo če a1i

K ,a ni

policaji a1i

K ,a ni

so v različnih stolpcih matrike A. Seštejmo številke

a1i ,K ,a ni

nad vsemi n-permutacijami elementov 1, 2, …, m. Potem dobimo od sto

ronov, število sistemov različnih predstavnikov za X1, ..., Xn, na drugi strani pa vrednost per-

manenta matrica A. ♦

a 1i 1 a 2i 2 L a ni n

Posledica. Sistem različnih predstavnikov za X1, …, Xn obstaja, če in samo če je za ustrezen matrični incident A izpolnjeno:

Ker je v formuli (1) m(m - 1) ... (m - n +1) členov, je izračun permanenta na podlagi definicije težaven. V ta namen predstavimo splošno formulo.

2. Omejimo se na obravnavanje kvadratnih numeričnih matrik A = (aij), i, j = 1, n.

Potem je per A = ∑

(i1 ,K ,in )

kjer se vsota razteza čez vse permutacije i1 , … , v elementih

1, 2, …, n. Uporabimo vključitveno-izključitveno formulo za izračun permanenta matrike A. Vsaki množici priredimo i1, ..., v uteži, ki je enaka a1i 1,K,a ni n.

To pomeni, da je permanent A vsota uteži tistih množic, ki ustrezajo permutacijam. Vstavimo n lastnosti P1 , … , Pn na množico vseh zbirk i1 , i2 , … , v od 1, 2, … , n, pri čemer lastnost Pi pomeni, da v zbirki i1 , … , ni elementa i, v. Tako je permanent A vsota uteži množic i1, ..., in, ki nimajo nobene od lastnosti P1, ..., Pn. Ostaja še določiti vsoto uteži W(Pi 1 ,K , Pi k ) množic s k lastnostmi

Pi 1 ,K , Pi k . Imamo za vsoto uteži W(0) vseh množic i1 , … , ik .
W(0) = ∑			K, ani		= (a 11 + L + a 1n )(a 21 + L + a 2n ) L (a n1 + L + a nn )
i1 ,K ,in
W(N(Pi )) =			a1i ,K ,a ni				= (a 11 + L + a 1i	L + a1n )L (a n1 + L a ni + L + a nn ) (9)
	≠i

kjer znak ^ nad elementom matrike A pomeni, da je treba ta element izpustiti. Podobno za sij (tj< j) имеем

W(N(Pi , Pj )) = (a11 + L + a1i	L+a 1j	L + a1n )L (a n1 + L a ni + L + a nj + L + a nn ) (10)

Zdaj z uporabo formule vključitve-izključitve dobimo Raiserjevo formulo za trajno A:

na A = ∏ i n = 1 (ai1 + L + ain ) − ∑∏ k n = 1 (a k1 + L + a ki + L + a kn )+ L +
+ (− 1)s	∑∏n
		(a k1 + L + a ki1	L+a ki	L +a kn ) +L
	1≤i1< L < is ≤ k n= 1

Izračun trajne z uporabo formule Raiser je mogoče organizirati tako, da zahteva

(2n - 1)(n - 4) množenja in (2n - 2)(n + 1) seštevanja. Čeprav ta vrednost hitro raste z n, ta formula daje največ učinkovita metoda izračuni stalnih.

3. Razjasnimo zdaj vprašanje pogojev, da je permanentna (0, 1) matrika enaka nič. Omejimo se na primer kvadratne matrike.

Izrek 2. Naj bo A = (aij ), i, j = 1, n (0, 1) matrika reda n. Potem

per A= 0, če in samo če A vsebuje podmatriko ničel velikosti s × t, kjer je s + t = n + 1.

♦ Naj takšna ničelna podmatrika obstaja v A. Ker se permanent ne spreminja zaradi permutacij vrstic in stolpcev, lahko domnevamo, da se ta podmatrika nahaja v spodnjem levem kotu, tj.

kjer je O - (s × t) matrika ničel, ima podmatrika B velikost (n - s) × t. Vsak člen permanenta A mora vsebovati en element iz prvih t stolpcev. Če torej iščemo pozitiven člen permanenta, morajo elementi teh stolpcev pripadati po paru različnih vrstic s številkami 1, 2, ..., n - s. Vendar je n - s = t - 1< t и поэтому данное условие выполнить нельзя, т.е. per A = 0.

Naj bo per A = 0. Izrek dokažemo z indukcijo na n. Za n = 1 je trditev očitna (A = (0)). Naj velja za vse rede, manjše od n. Če je A ničelna matrika reda n, potem je izjava očitna. Če A ni ničelna matrika, naj bo aij = 1. Zapišimo dekompozicijo A vzdolž vrstice i:

na A = ai1 Ai1 + … + ain Ain

Ker je per A = 0, potem je per Aij = 0. Toda Aij ima velikost (n - 1) × (n - 1) in po indukcijski hipotezi obstaja podmatrika ničel velikosti

s1 × t1, pri čemer je s1 + t1 = n - 1 + 1 = n. Preuredimo vrstice in stolpce tako, da je ta ničelna podmatrika v spodnjem levem kotu:

A → B =

kjer je O ničelna podmatrika velikosti s1 × t1, s1 + t1 = n, C - ima velikost (n - s1) × t1, D -

ima velikost s1 × (n - t). To pomeni, da sta matriki C in D kvadratni in imata vrstni red (t1 × t1) oziroma (s1 × s1). Po definiciji permanenta imamo per B = per A in,

per B = per C per D in zato iz per A = 0 sledi bodisi per C = 0 bodisi per D = 0.

Naj bo per C = 0. Po indukcijski hipotezi obstaja ničelna podmatrika velikosti

u × v, kjer je u + v = t1 + 1. Naj se nahaja v vrsticah s številkami i1, …, iu in stolpcih s številkami j1, …, jv. Razmislite o podmatriki B, sestavljeni iz vrstic

i1, …, iu, t1 + 1, …, n in stolpci j1, …, jv. To je ničelna podmatrika velikosti (u + n - t1) × v,

kjer je u + n - t1 + v = n + +1. Torej matrika B vsebuje ničelno podmatriko velikosti s × t, kjer je s + t = n + 1. Ker se matriki A in B razlikujeta v permutaciji vrstic in stolpcev, je izrek dokazan. ♦

Oglejmo si zdaj pomemben poseben primer matrike A. Označimo z A(k, n) matriko 0,1 elementov velikosti n × n s k enicami za vsako vrstico in vsak stolpec (k > 0).

Izrek 3. Za katero koli matriko A(k, n) velja A(k, n) > 0.

♦ Predpostavimo nasprotno, da je per A(k, n) = 0. Potem po izreku 2 obstaja ničelna

podmatriko velikosti s × t, kjer je s + t = n + 1. Nato s preurejanjem vrstic in stolpcev matrike A(k, n) dobimo matriko

kjer je O ničelna (s × t) matrika.

Preštejmo število enic v matrikah B in D. Ker ima A(k, n) k enic v vsaki vrstici in vsakem stolpcu, je v vsakem stolpcu B in vsaki vrstici D točno k enic.

enote. V A(k, n) je skupaj n k enot, torej je nk ≥ tk + sk = (t + s)n. Na ta način

som, n ≥ t + s, kar je nemogoče, ker s + t = n + 1 Iz tega protislovja sledi, da

veljavnost izjave. ♦ Dokazuje se na podoben način

Izrek 3a. Naj bo A (0,1) matrika velikosti n × m (n≤ m). Potem je perA = 0, če in samo če vsebuje ničelno podmatriko velikosti s×t, kjer je s+t=m+1.

4. Zdaj razmislimo o uporabi obravnavanih vprašanj pri gradnji la-

Tinini kvadratki. latinica (n × m)-pravokotnik nad množico X=(x1 ,…,xm )

se imenuje (n × m) -matrika elementov X, v kateri je vsaka vrstica n-permutacija X, vsak stolpec pa je m-permutacija množice X. Za n=m se latinski pravokotnik imenuje latinski kvadrat.

Jasno je, da je za n=1 število latinskih pravokotnikov 1×m enako m!. Ko je n=2, potem ko je izbrana prva vrstica, se lahko katera koli permutacija vzame kot druga vrstica.

nov izdelek, ki je v nasprotju z izbranim. Število takih permutacij je Dm, torej je število 2× m

latinskih pravokotnikov je enako m! Dm.

V zvezi z induktivno konstrukcijo latinskih kvadratov se pojavi naravno vprašanje. Konstruirajmo latinski (n × m) pravokotnik (n< m). Можно ли его расширить до ((n+1)× m) -прямоугольника добавлением (n+1)-й строки?

Pošteno

Izrek 4. Vsak latinski (n× m)-pravokotnik n

♦ Naj bo X=(x1,…,xm) in L-latinski (n×m)-pravokotnik z elementi iz X. Razmislite o množici množic A1,…,Am, kjer so Ai elementi i-tega stolpca latinski pravokotnik L. Naj bo A incidenčna matrika sistema množic A1 ,… ,Am . Ima velikost m×m in vsaka vrstica matrike A vsebuje natanko n enic, saj je Ai = n, i = 1, m. Vsak element xi X se lahko pojavi v stolpcih L največ m-krat, sicer bi obstajala vrstica, v kateri se ta element pojavi dvakrat. Skupno število elementov

L je enak m n, zato se vsak element xi X pojavi natanko n-krat v stolpcih. Iz tega sledi, da vsak stolpec matrike A vsebuje točno n enot. Oglejmo si zdaj matriko A, ki jo dobimo tako, da vsako 1 zamenjamo z ničlo in vsako ničlo z 1.

Matrika A je incidenčna matrika sistema množic X1, …, Xn, kjer je Xi = X\Ai,

i = 1, m. Vsebuje m - n enot v vsaki vrstici in v vsakem stolpcu. Po izreku

> 0. Naj bo ai1

…a mi

≠ 0 . Potem imamo xi X1 ,K , xi

Xm in vsi elementi

xi ,K ,xi

po paru različni. Linija

xi ,K ,xi

lahko vzamemo kot (n + 1)-to

za latinski (n × m)-pravokotnik L. Če nadaljujemo ta postopek, dobimo latinski

nebeški kvadrat. ♦

Označimo z l n - število latinskih kvadratov reda n, z elementi iz množice X = (1, 2, ..., n), v kateri so elementi prvega stolpca in prve vrstice v naravnem vrstnem redu. Tukaj je tabela več znanih vrednosti števila l n:

5. Matriko A = (aij) velikosti n × n z realnimi, nenegativnimi elementi imenujemo dvakrat stohastično, Če