Funcția Möbius. Formula de inversare a lui Möbius. Banda Mobius - descoperire uimitoare „Magia” benzii Mobius

Instituție de învățământ bugetar municipal liceu şcoală cuprinzătoare cu studiul aprofundat al individului

articole cu. Terbuny

banda Mobius

Completat de: Chepurina Anna Vitalievna,

elev de clasa a X-a

Șef: Kirikova M.A.

primul profesor de matematică

categoria de calificare

satul Terbuny

2015

Introducere………………………………………………………… .................3

Contextul istoric…………………………………………………………4

Banda Möbius este începutul unei noi științe a topologiei...................................5

Realizarea unei benzi Mobius………………………………………6

Experimente cu banda Mobius.................................................. ...... .................9

Proprietățile topologice ale benzii Möbius…………..11

Teoreme pe banda Möbius……………………………………………….12

Trucuri cu banda Mobius………………………………………………………15

Aplicarea benzii Möbius………………………………………………..16

Concluzie................................................. ........................................23

Lista literaturii utilizate.................................................. .......... .25

Aplicație

Introducere

În zilele noastre, este important să studiem diferitele proprietăți și aplicații non-standard ale figurilor neobișnuite.

Ați auzit vreodată de o bandă Möbius? Cum poate fi realizat, cum este legat de matematică și unde este folosit în viață.

În timp ce făceam această lucrare, am ajuns la concluzia că, deși banda Möbius a fost descoperită în secolul al XIX-lea, a fost relevantă atât în ​​secolul XX, cât și în secolul XX. Proprietățile uimitoare ale benzii Möbius au fost și sunt folosite în gătit, tehnologie, fizică, pictură, arhitectură și în designul de bijuterii și bijuterii. El a inspirat creativitatea multor scriitori și artiști.

Interesul pentru banda Möbius nu a scăzut până în prezent. La Moscova, în septembrie 2006, a avut loc Festivalul de matematică artistică. Discursul unui profesor din Tokyo a fost primit cu mare succes.

Am fost foarte interesat și intrigat de acest subiect. Am studiat literatura, apoi am făcut eu o bandă Mobius și apoi am efectuat cercetări, am efectuat experimente, am studiat proprietățile magice, extraordinare ale acesteia.

O bandă Möbius este o bandă de hârtie cu un capăt întors cu jumătate de tură (adică 180 de grade) și lipit de celălalt capăt. Milioane de oameni din toate părțile lumii nici nu realizează că folosesc o bandă Möbius în fiecare zi.

Ţintă : spune-le și arată-le colegilor tăi că o panglică aparent simplă, s-a întors

jumătate de tură cu capete lipite, poate conține mult

surprize.

Obiectul de studiu: bandă Möbius.

Sarcini: să identifice sursele și literatura pe această temă și să le analizeze;

faceți cunoștință cu istoria fâșiei Mobius;

învață cum să faci o bandă Mobius;

studiază diferitele proprietăți ale benzii Möbius;

În timp ce lucram la subiect, am folosit următoarele metode: analiză, sinteză,

observație, experiment, comparație și anchetă sociologică.

CAPITOL eu

„Fâșia Möbius – începutul unei noi științe”

1. 1. Context istoric

Misteriosa și celebra bandă Möbius a fost inventată în 1858 de un geometru germanAugust Ferdinand Mobius . Se spune că Mobius a fost ajutat să-și deschidă „frunza” de o servitoare care a cusut greșit capetele unei panglici lungi. A așteptat șapte ani ca munca sa să fie revizuită și, fără să aștepte, și-a publicat rezultatele.

În același timp cu Möbius, un alt student al lui K. F. Gauss a inventat această frunză -Listare Johann Benedict, Profesor la Universitatea din Göttingen. Și-a publicat opera cu trei ani mai devreme decât Mobius, în 1862. A. F. Mobius s-a născut în orașul Schulpforte. De ceva vreme, sub îndrumarea lui K. Gauss, a studiat astronomia. El a început să efectueze observații astronomice independente la Observatorul Pleisenburg în 1818. a devenit directorul acesteia. În acele vremuri, matematica nu era susținută, iar astronomia oferea destui bani pentru a nu se gândi la ele și lăsa timp pentru propriile gânduri. Devenind profesor la Universitatea din Leipzig, în 1816 Möbius a introdus pentru prima dată geometria proiectivă, un sistem de coordonate și metode analitice de cercetare; a stabilit existența suprafețelor unilaterale (fâșii Möbius), poliedre, pentru care nu se aplică „legea muchiilor” și care nu au volum. Möbius este unul dintre fondatorii teoriei transformărilor geometrice, precum și ai topologiei. A obținut rezultate importante în teoria numerelor (funcția Möbius) și a devenit unul dintre geometrii de frunte ai timpului său.

1.2. Banda Möbius - începutul unei noi științe a topologiei

Din momentul în care matematicianul german A. F. Möbius a descoperit existența unei coli de hârtie uimitoare cu o singură față, a început să se dezvolte o ramură cu totul nouă a matematicii, numită topologie. Termenul „topologie” poate fi atribuit două ramuri ale matematicii. O topologie, al cărei fondator a fost Poincaré, a fost numită combinatorie multă vreme. Celălalt, ale cărui origini au fost omul de știință german Georg Cantor, a primit numele de general sau teoretic set-theoretic.

Topologia combinatorie este o ramură a geometriei. „Geometrie” este un cuvânt grecesc, tradus în rusă înseamnă „agrimensura terenului” („geo” înseamnă pământ în greacă, iar „metreo” înseamnă a măsura) studiază proprietățile figurilor. Ca orice știință, geometria este împărțită în secțiuni.

1. Planimetrie (cuvânt latin, „planum” - suprafață + geometrie), o secțiune a geometriei care studiază proprietățile figurilor pe un plan (triunghi, pătrat, cerc, cerc etc.)

2. Stereometrie (greacă, „stereos” - spațiu + geometrie) - o secțiune de geometrie care studiază proprietățile figurilor din spațiu (sferă, cub, paralelipiped etc.)

H. Topologia (greacă „topos” - loc, teren + logică) este una dintre cele mai „tinere” secțiuni ale geometriei moderne, care studiază proprietățile unor astfel de figuri care nu se schimbă dacă sunt îndoite, întinse, comprimate, dar nu lipite. și nu se rupe, adică nu se schimbă atunci când sunt deformate. Exemple de obiecte topologice sunt: ​​literele I și H, baloane lungi și subțiri.

Topologia combinatorie studiază proprietățile forme geometrice, care rămân neschimbate în mapările unu-la-unu și continue. Multă vreme, topologia a fost percepută ca o știință departe de viață, menită doar să „slăvească mintea umană”. Dar în timpul nostru a devenit clar că are legătură directă cu explicarea structurii universului.

Topologia generală este adiacentă teoriei mulțimilor și stă la baza matematicii. Aceasta este o teorie axiomatică concepută pentru a explora concepte precum „limită”, „convergență”, „continuitate”, etc. Bazele axiomaticii spațiului topologic au fost puse de Felix Hausdorff și completate. matematician rus Pavel Sergheevici Alexandrov.

1.3. Cum se face o bandă Möbius

● Banda Möbius este una dintre (surprizele matematice) Pentru a face o bandă Möbius, luați o bandă dreptunghiulară ABCD, răsuciți-l la 180 de grade și lipiți părțile opuse AB șiCD, adică deci punctele A și vor coincideCși puncte Dși V.

Vezi adj. unsprezece.

● Formele și dimensiunile benzilor de hârtie pentru banda Möbius.

Banda ar trebui să fie îngustă și lungă, cu cel mai mare raport posibil dintre lungime și lățime. Nu poți face o bandă Möbius dintr-o foaie pătrată de hârtie. Acest lucru este adevărat, dar nu trebuie subestimat faptul că restricțiile de dimensiune contează atunci când hârtia nu are voie să se încrețe. Dacă mototolirea hârtiei nu este interzisă, atunci o bandă Möbius poate fi lipită nu numai dintr-un pătrat, ci dintr-un dreptunghi de orice dimensiune - laturile lipite pot fi chiar de orice număr de ori mai lungi decât cele nelipite.

● Suprafata de dezvoltare.

Deoarece cerința de a nu încreți hârtia este importantă, să vedem care este sensul ei matematic.

Este ușor de înțeles că interdicția împotriva mototolării hârtiei limitează semnificativ

capacitatea de a manipula o coală de hârtie. De exemplu, o coală de hârtie poate fi rulată într-un tub sau pliată în jumătate fără să se încrețe, dar nu poate fi pliată în patru. Puteți face un con dintr-o foaie de hârtie fără a o mototoli, dar nu puteți face o sferă sau măcar o bucată din ea: apăsați foaia de hârtie pe glob și cu siguranță vor apărea pliuri. După cum puteți vedea, unei coale de hârtie nu i se poate da nicio formă. Vezi adj. 2.

Suprafețele care pot fi făcute dintr-o foaie de hârtie prin îndoirea acesteia fără a o zdrobi sunt numite de matematicieni suprafețe dezvoltabile. În matematică, suprafețele dezvoltabile sunt definite diferit: în limbajul metamatematic nu există cuvinte „hârtie”, „motolit”, „face”. Există o întreagă teorie a suprafețelor dezvoltabile, printre realizările căreia se află un răspuns satisfăcător la întrebarea ce pot fi acestea; matematicienii numesc aceasta „clasificare” (răspunsul îi aparține lui Leonardo Euler). Să prezentăm doar câteva proprietăți ale suprafețelor dezvoltabile ca fapte experimentale.

Vezi adj. 3

1. Prin fiecare punct A al unei suprafețe dezvoltabile care nu se află pe limita sa trece un segment care se află pe suprafața care nu se termină în A. Cu alte cuvinte, către fiecare punct de pe o suprafață dezvoltabilă (o curbă, dar nu mototolită). foaie de hârtie) un ac de tricotat poate fi atașat astfel încât să fie adiacent suprafeței într-o anumită măsură pe ambele părți ale punctului luat. Un astfel de segment se numește generatoare a suprafeței (să fim de acord că acest nume se aplică numai segmentelor de lungime maximă care se află în întregime pe suprafață, adică segmentelor care nu sunt conținute în segmente mari cu această proprietate).

2. Dacă două generatoare diferite trec printr-un punct A, care nu se află la limita unei suprafețe, iar A nu este capătul niciunuia dintre ele, atunci o bucată suficient de mică din suprafața din jurul lui A este plată. În acest caz, vom numi punctul A bemol.

3. Dacă punctul A, care nu se află la limita suprafeței, este capătul unui generator, să spunem:A , atunci vecinătatea punctului A este structurată astfel: prin punctul A trece singura generatrică care nu se termină acolo, să zicemb . Această generatoare împarte suprafața în două părți. Pe cealaltă parte a generatriceib , cu care este localizată generatoareaA , la generator b o bucată plată este adiacentă, pe cealaltă parte ab , în mod arbitrar din punctul A, există puncte neplate. În această situație vom numi punctul A semi-plat.

Subliniem că, dacă un punct de pe o suprafață nu este nici limită, nici plat, atunci trece prin el o singură generatrică care nu se termină la el, iar capetele acestei generatrice se află la limita suprafeței.

●Exemple: O coală de hârtie rulată într-un cilindru sau un con nu are puncte plate (sau semiplate). Într-un cilindru, generatoarele alcătuiesc familia segmente paralele, un con are o familie de segmente care se extind dintr-un punct. Sunt posibile aranjamente mai complexe ale generatricelor.

Vezi adj. 4 .

De exemplu, generatoarele și punctele plate ale unei suprafețe în curs de dezvoltare sunt prezentate în figură (în care suprafața este desfășurată într-o coală plată de hârtie): liniile subțiri sunt generatoare, iar zonele umbrite constau din puncte plate.

Punctele situate la limita unei regiuni de puncte plate sunt fie puncte de limită pentru întreaga suprafață, fie semi-plate. Dacă o suprafață este formată dintr-un poligon de hârtie (să zicem, un dreptunghi), atunci punctele plane formează unul sau mai multe poligoane plane, fiecare dintre aceste poligoane având vârfuri situate la limita suprafeței și laturi fie situate pe graniță, fie constând de puncte semiplane.

CAPITOLUL 2

2.1. Experimente cu banda Mobius

Fiecare dintre noi are o idee intuitivă despre ce este „suprafața”. Suprafața unei foi de hârtie, suprafața pereților unei săli de clasă, suprafața globului sunt cunoscute de toată lumea. Poate exista ceva misterios într-un concept atât de obișnuit? Da, poate un exemplu este banda Möbius. Pentru a-i studia proprietățile, am efectuat mai multe experimente (împărțindu-le în două grupuri) pe cont propriu.

eu grup de experimente

Experienţa nr 1. Suntem obişnuiţi cu faptul că la orice suprafaţă de pe care

avem de-a face (coală de hârtie, bicicletă sau tub de volei) –

două părți.

Am început să pictez banda Mobius fără să o răsturn.

Rezultat . Banda Möbius a fost complet vopsită.

„Dacă cineva decide să coloreze doar o parte

suprafața benzii Möbius, lăsați-l să-l scufunde imediat într-o găleată de vopsea.” - scrie Richard Courant și Herbert Robins într-un mod excelent

cartea "Ce este matematica?"

Experiența nr. 2. Am făcut un păianjen și o muscă din hârtie și le-am trimis „la plimbare”.

un inel obișnuit, dar le interzicea să treacă granițele.

Rezultat. Păianjenul nu a putut ajunge la muscă.

Experimentul nr. 3. Am trimis acești păianjen și zboară doar de-a lungul fâșiei Mobius. ȘI

le-a interzis să se târască peste graniță.

Rezultat.Biata musca va fi mancata daca, bineinteles, paianjenul alearga

Mai repede!

Experiența nr. 4. Am făcut un omuleț din hârtie și l-am trimis să călătorească de-a lungul fâșiei Mobius.

Rezultat. Omulețul se va întoarce la punctul de plecare, unde și-ar întâlni imaginea în oglindă.

II grup de experimente

asociat cu tăierea benzii Möbius, rezultatele sunt enumerate în tabel

experienţă

Descrierea experienței

Rezultat

Am tăiat un inel simplu pe lungime în mijloc.

Am primit două inele simple, de aceeași lungime, de două ori mai late, cu două chenare.

Fâșia Möbius a fost tăiată pe lungime pe mijloc.

Am primit 1 inel, a cărui lungime este de două ori mai lungă, lățimea este de două ori mai îngustă, răsucit 1 tură completă, cu un chenar.

Lățimea benzii Möbius

5cm taiat pe lungime la o distanta de 1cm de margine.

Am primit două inele legate între ele: 1) o bandă Mobius - lungime = lungimea celui original, lățime 3 cm; 2) lățime 1 cm, lungime de două ori față de original, răsucit două ture complete, cu două chenare.

Lățimea benzii Möbius

5cm taiat pe lungime la o distanta de 2cm de margine.

Am primit două inele interconectate între ele: 1) inelul este o bandă Möbius de 1 cm lățime, lungime = lungimea celui original; 2) inel - 2 cm latime, de doua ori mai lung decat cel original, rasucit cu doua ture complete, cu doua chenare.

O bandă Möbius de 5 cm lățime, tăiată pe lungime la o distanță de 3 cm de margine.

Am două inele legate între ele: 1) inelul este o bandă Möbius cu lățimea

1 cm de aceeași lungime; 2) inel – 2 cm lățime, lungimea sa este de două ori mai mare decât cea originală, răsucite două ture complete.

Rezultatele unui sondaj sociologic realizat cu elevi de clasa a X-a.

Întrebări

da

Nu

Ai auzit

1. Știți ce este topologia?

2. Știți ce este o bandă Mobius?

3. Știai că proprietățile unei benzi Moebius?

Doar 5% dintre elevii de clasa a X-a știu ce este topologia. 30% dintre studenți știu ce este o bandă Mobius 20% au auzit de ea. 50% habar nu au despre banda Mobius. 25% dintre studenți cunosc proprietățile benzii, 10% au auzit despre ele, 65% nu știu nimic despre proprietățile benzii Möbius.

2.2.Proprietăți topologice ale benzii Möbius

Pe baza rezultatelor experimentelor, putem formula următoarele proprietăți topologice ale benzii Möbius legate de surprizele matematice.

Unilateralitatea este o proprietate topologică a benzii Möbius, caracteristică doar acesteia.

Continuitate - pe o bandă Möbius, orice punct poate fi conectat

cu orice alt punct. Nu există pauze - continuitate completă.

Din punct de vedere topologic, un cerc nu se distinge de un pătrat,

pentru că sunt ușor de transformat unul în altul fără a se rupe

continuitate.

Conectivitate – vor fi necesare două tăieturi pentru a înjumătăți inelul. În ceea ce privește banda Möbius, numărul de conexiuni este înlocuit în funcție de modificarea numărului de spire ale benzii: dacă o spire este conectată dublu, dacă două spire sunt conectate simplu, dacă trei spire sunt conectate dublu etc. împărțiți pătratul în două părți, avem nevoie doar de o tăietură. Conectivitatea este de obicei evaluată prin numărul Betti sau, uneori, se folosește caracteristica Euler.

4. Orientarea este o proprietate care este absentă în banda Möbius. Deci, dacă o persoană ar putea călători de-a lungul tuturor curbelor benzii Mobius, atunci s-ar întoarce la punct de start, dar s-ar transforma în imaginea lui în oglindă.

5. „Numărul cromatic” este numărul maxim de zone care pot fi desenate pe o suprafață astfel încât fiecare dintre ele să aibă o margine comună cu toate celelalte. Numărul cromatic al benzii Möbius este șase.

6.Teoreme pe banda Möbius

Teorema 1: λ ≥ π/2

Din cauza complexității dovezii, nu o iau în considerare în munca mea.

Teorema 2: λ ≤ √3

Această teoremă este mai simplă decât cea anterioară: pentru a o demonstra, este suficient să explicăm cum se lipește o bandă Möbius dintr-o bandă a cărei lungime este mai mare de √3. Să presupunem mai întâi că lungimea sa este exact √3. Apoi puteți plasa două triunghiuri regulate pe această bandă. Să îndoim banda de-a lungul laturilor acestor triunghiuri, alternând direcțiile de pliere. Marginile AB și CD ale benzii se vor alinia, iar punctul A se va alinia cu punctul D și punctul B cu punctul C. Rezultatul va fi o bandă Möbius, ale cărei margini sunt poziționate cap la cap (vezi Anexa 1.2). )

În această construcție, regula principală a fost încălcată - nu încreți hârtia. Dar este ușor de înțeles că, dacă lungimea benzii este cel puțin puțin mai mare de √3, atunci ruptura de-a lungul generatricei poate fi înlocuită prin îndoirea efectuată într-o secțiune îngustă. Pe scurt, nu ne este frică de o îndoire de-a lungul unui segment drept: poate fi înlocuit cu o îndoire aproape de el. (Sifonarea ireparabilă a hârtiei apare atunci când două linii de pliere se intersectează, adică atunci când foaia este pliată ca o batistă - toate acestea ne sunt cunoscute din experiența de zi cu zi.) Structura sa poate fi imaginată după cum urmează: trei triunghiuri regulate identice ABC, A"B"C", A"B"C" sunt paralele între ele, vârfurile corespunzătoare sunt deasupra vârfurilor corespunzătoare; laturile AB și A"B", B"C" și B"C", C"A" și CA sunt conectate prin jumperi. Linia de lipire trece de-a lungul medianei unuia dintre triunghiuri.

De ce nu putem găsi λ mai precis?

Până când problema nu este rezolvată, este greu de spus de ce nu este rezolvată. Cu toate acestea, uneori, în diverse probleme nerezolvate, este posibilă urmărirea dificultăților comune, marcarea, ca să spunem așa, locuri dificile pe o hartă matematică, ceea ce face uneori posibilă prezicerea succesului sau eșecului în rezolvarea unei anumite probleme.

Teorema 3. O bandă Möbius cu auto-intersecții poate fi lipită împreună dintr-o bandă de orice lungime mai mare de π/2.

Se face așa. Să luăm un n impar suficient de mare și să construim un n-gon regulat înscris într-un cerc cu diametrul 1. Să considerăm, în continuare, n triunghiuri care conțin centrul cercului, fiecare dintre ele limitat de o latură și două diagonale ale lui n- gon (n=7). Aceste triunghiuri acoperă n-gonul nostru, unele dintre locurile sale de mai multe ori. Să aplicăm acum aceste n triunghiuri unul altuia, după care tăiem jumătate din triunghiul din stânga de-a lungul medianei lungi și o aplicăm pe triunghiul cel mai drept. Rezultatul este o bandă dreptunghiulară cu un raport dintre lungime și lățime mai mare de π/2 și tinde spre π/2 ca n, tinde spre ∞ (lățimea benzii tinde spre 1, iar lungimea către π/2). Îndoiți în mod constant această bandă de-a lungul tuturor liniilor trasate pe ea, alternând direcțiile de pliere. Segmentele AB și CD aproape vor coincide - vor exista doar câteva straturi de hârtie îndoită între ele. În această „aproape aliniere”, punctul A se va alinia cu D, iar punctul B se va alinia cu C, așa că dacă am putea „trece banda prin” și lipici |AB| cu |CD|, atunci rezultatul ar fi o bandă Möbius. Dacă luați banda un pic mai mult, puteți evita pliurile, așa cum am făcut în demonstrația Teoremei 2. Am obținut o bandă Möbius, ale cărei margini sunt separate de mai multe straturi de hârtie, vezi Anexa 1.3. Dar să revenim la banda Möbius. Teorema 1, după cum am văzut, se aplică de fapt benzilor care se intersectează. Este puțin probabil ca condiția fără auto-intersecție să nu aibă efect asupra lui λ; cu toate acestea, nu este posibil să se țină cont de acest efect, deoarece matematica nu dispune de mijloace tehnice suficiente pentru a studia autointersecțiile în spațiul tridimensional. Dimpotrivă, este destul de probabil ca Teorema 2 să nu poată fi îmbunătățită. La urma urmei, îmbunătățirea acesteia înseamnă a veni cu un nou design de bandă. Experiența arată că construcțiile optime sunt simple și armonioase, ceea ce este construcția din demonstrația teoremei 2. Este firesc să presupunem că, dacă ar fi existat cea mai bună construcție, s-ar fi găsit - după atâția ani!

Acesta este motivul pentru care ne putem aștepta la λ = √3.

Moebius strip trucuri

Problema nodurilor

Cum să faci un nod într-o eșarfă fără a renunța la capete? Se poate face așa. Așezați eșarfa pe masă. Încrucișează-ți brațele peste piept. Continuând să le țineți în această poziție, aplecați-vă peste masă și luați un capăt al eșarfei cu fiecare mână pe rând. După ce brațele sunt depărtate, se va forma automat un nod în mijlocul eșarfei. Folosind terminologia topologică, putem spune că mâinile privitorului, corpul și eșarfa lui formează o curbă închisă sub forma unui nod „cu trei frunze”. La desfășurarea brațelor, nodul se mișcă doar de la mâini la eșarfă.

Faceți un nod în eșarfă cu o mână, fără a da drumul la capătul eșarfei din mână. Răspunsul la acest puzzle poate fi găsit în cartea „Minuni și mistere matematice” de M. Gardner.

Din punct de vedere topologic, vesta poate fi considerată ca o suprafață cu două fețe cu trei margini care nu se intersectează, fiecare dintre acestea fiind o curbă obișnuită închisă. Vesta cu nasturi este o suprafață cu două fețe cu patru margini.

Buclă misterioasă.

Spectatorul care poartă vesta are o buclă plasată pe mână și apoi i se cere să-și pună degetul mare în buzunarul de jos al vestei. Acum îi poți invita pe cei prezenți să scoată bucla din mână fără a scoate degetul din buzunarul vestei. Soluția este următoarea: bucla trebuie trasă în orificiul vestei pentru mânecă, aruncată peste capul privitorului, scoasă prin a doua gaură pentru mânecă și mutată sub al doilea braț. Ca urmare a acestor acțiuni, bucla va fi sub vestă, înconjurând pieptul. Coborâți-l până când apare de sub vestă, apoi lăsați-l să cadă pe podea.

Întoarcerea vestei pe dos fără a o scoate de la persoană.

Proprietarul vestei trebuie să-și strângă degetele la spate. Cei din jurul tău ar trebui să întoarcă vesta pe dos, fără a separa mâinile proprietarului. Pentru a demonstra această experiență, este necesar să desfaceți vesta și să o trageți peste mâinile din spatele purtătorului. Vesta va atârna în aer, dar, bineînțeles, nu se va desprinde, deoarece mâinile sunt împreunate. Acum trebuie să luați tivul stâng al vestei și, încercând să nu încreți vesta, să o împingeți cât mai mult posibil în armura dreaptă. Apoi luați armurița dreaptă și introduceți-o în aceeași armurie și în aceeași direcție. Mai rămâne doar să îndrepti vesta și să o tragi pe proprietar. Vesta va fi intoarsa pe dos. Am făcut acest truc și l-am filmat împreună cu colegii noștri de clasă. Este cuprins în prezentarea „Fâșia Mobius”.

2.3. Aplicarea benzii Möbius

∞ La intrarea în Muzeul de Istorie și Tehnologie din Washington, o panglică de oțel răsucită cu o jumătate de tură se rotește încet pe un piedestal. În 1967, când a avut loc Congresul Internațional de Matematică în Brazilia, organizatorii săi au emis un timbru comemorativ în valori de cinci centavos. Înfățișa o bandă Möbius. Atât monumentul, înalt de peste doi metri, cât și ștampila minusculă sunt monumente unice ale matematicianului și astronomului german August Ferdinand Möbius.

Vezi Anexa 5.

Serviciul de brevete a înregistrat multe invenții bazate pe aceeași suprafață unilaterală.

∞ Banda Möbius este folosită în multe invenții inspirate de studiul atent al proprietăților unei suprafețe unilaterale. Banda cu bandă transportoare, realizată sub formă de bandă Möbius, îi permite să lucreze de două ori mai mult deoarece întreaga suprafață a foii se uzează uniform. În 1923, a fost eliberat un brevet inventatorului Lee de Force, care a propus înregistrarea sunetului pe film fără a schimba rolele pe ambele părți simultan. Au fost inventate casetele pentru magnetofone, unde banda este răsucită și lipită într-un inel, ceea ce face posibilă înregistrarea sau citirea informațiilor din ambele părți simultan, ceea ce dublează capacitatea casetei și, în consecință, timpul de redare. La imprimantele cu matrice de puncte, banda de cerneală avea forma unei benzi Möbius pentru a crește durata de valabilitate. Acest lucru oferă economii semnificative. Banda Möbius este folosită în tuburi pentru ciclism și volei.

∞ Mai recent, i-au găsit o altă utilizare - a început să joace rolul unui arc, doar un arc special. După cum știți, un arc încărcat trage în direcția opusă. Banda Mobius, contrar tuturor legilor, nu schimbă direcția de funcționare, ca și mecanismele cu două poziții stabile. Un astfel de arc ar putea deveni de neprețuit în jucăriile cu vânt - nu poate fi răsucit ca unul obișnuit - un fel de mașină cu mișcare perpetuă.

Vezi adj. 6.

∞ În 1971, inventator din Urali P.N. a aplicat un filtru sub forma unei benzi Mobius.

∞ Frunza de Mobius este folosită în gătit pentru a crea un aspect interesant și apetisant pentru chifle, biscuiți și tufiș. Și, de asemenea, în fabricarea de instrumente pentru prepararea și decorarea diverselor feluri de mâncare, structuri de putere (agitator).

Vezi adj. 7.

∞ Cu ajutorul unei benzi Möbius, sunt create capodopere întregi.

Banda Möbius a servit drept inspirație pentru sculpturi și artă grafică. Escher a fost unul dintre artiștii care l-au iubit în mod deosebit și și-a dedicat câteva dintre litografiile sale acestui obiect matematic. Unul celebru arată furnici care se târăsc pe suprafața unei benzi Möbius.

Vezi anexa 9.

∞ Banda Möbius apare, de asemenea, în mod regulat în science-fiction, cum ar fi în povestea lui Arthur C. Clarke „The Wall of Darkness”. Uneori, poveștile științifico-fantastice sugerează că Universul nostru poate fi un fel de bandă Möbius generalizată. În povestea autorului A.J. Deitch, metroul din Boston construiește o nouă linie, al cărei traseu devine atât de confuz încât se transformă într-o bandă Mobius, după care trenurile încep să dispară pe această linie.

∞ Există o ipoteză că spirala ADN-ului în sine este, de asemenea, un fragment al unei benzi Mobius și acesta este singurul motiv pentru care codul genetic este atât de greu de descifrat și perceput. Mai mult decât atât, o astfel de structură explică destul de logic motivul apariției morții biologice: spirala se închide pe sine și are loc autodistrugerea.

Anexa 10.

∞ Fâșia Möbius a fost plăcută nu numai de matematicieni, ci și de magicieni

De peste 100 de ani, banda Möbius a fost folosită pentru a efectua diverse trucuri magice și divertisment. Proprietățile uimitoare ale frunzei au fost demonstrate chiar și la circ, unde au fost suspendate panglici strălucitoare lipite împreună sub formă de benzi Möbius. Magicianul și-a aprins o țigară și cu capătul arzând a atins linia de mijloc a fiecărei panglici, care era făcută din nitrat de potasiu. Calea de foc a transformat prima panglică într-una mai lungă, iar a doua în două panglici, înfiletate una în cealaltă. (În acest caz, magicianul a tăiat fâșia Mobius nu la mijloc, ci la o distanță de o treime din lățimea ei).

∞ Fizicienii susțin că toate legile optice se bazează pe proprietățile benzii Mobius, în special, reflectarea într-o oglindă este un fel de transfer în timp, pe termen scurt, care durează sutimi de secundă, pentru că vedem în fața noastră. . așa e, oglinda noastră dublă.

∞Există o ipoteză că Universul nostru este destul de probabil închis în aceeași bandă Mobius, conform teoriei relativității, cu cât masa este mai mare, cu atât curbura spațiului este mai mare. Această teorie confirmă pe deplin presupunerea că nava spatiala, zburând drept tot timpul, se poate întoarce la punctul de plecare, asta confirmă nelimitatul și finitudinea Universului.

Vezi adj. unsprezece.

∞ Interesul pentru banda Möbius nu a scăzut până în prezent. Festivalul de matematică artistică a avut loc la Moscova în septembrie 2006. Discursul profesorului din Tokyo Jin Akiyama a fost primit cu mare succes. Prestația sa amintea de spectacolul unui iluzionist, unde era loc pentru banda Möbius (lucrare cu hârtie „Fâșia Möbius și modificările sale”).

SPORTUL

Expansor manual "Robur"

Vezi adj. 12 .

Unul dintrelucrurile preferate de toți profesorii de educație fizică din școală, care potrivit acestoraîn propriile sale cuvinte, „antrenează nunumai muşchii mâinii, darşi muşchiul creierului."Extensor carpian dinStudioul Artemy Lebedev repetă forma unei benzi Möbius. Un remediu excelent pentru ameliorarea stresului, gândindu-se lainfinit şidoar o modalitate utilă de a-ți ține mâinile ocupate.

PARFUM

Parfum Bugatti

Vezi adj. 13

CompanieBugattia început să producă nu numai mașini extrem de scumpe (modelVeyroncostă 1,3 milioane de euro), dar și... parfum. Fiecare sticla, realizata din cristal si acoperita cu aur adevarat, este conceputa sub forma unei benzi Möbius neobisnuite, care are o singura fata. Pretul parfumuluiBugattieste de 3500 euro.

Parfum Loewe Quzas, Quizas, Quizas

Vezi adj. 14 .

În toamna anului 2011, a fost lansată o versiune purpurie a parfumului, a cărei sticlă este învelită într-o bandă Mobius - un simbol al ciclului pasiunilor din natură. Bogăția compoziției constă în prospețimea portocalelor asiatice, bergamotă, fructe de pădure roșii, continuă cu o inimă florală de magnolie, frezie și petale de portocală și se termină cu o dâră senzuală de lemn de cașmir, chihlimbar auriu și vetiver.

Parfum Ediție limitată UFO, Kenzo

Vezi adj. 15 .

Prezentare de parfumKenzoa avut loc în 2009 la o expoziție retrospectivă a lucrărilor lui Ron Arad (RonArad) la Centrul Pompidou din Paris. Acest artist și arhitect a fost cel care a creat designul cosmic al sticlei sub forma unei benzi Mobius. Este conceput pentru a se potrivi exact în palma mâinii tale.NeidentificatParfumObiect, sau „Obiect aromatic neidentificat”, este limitat la doar 180 de bucăți și se vinde cu amănuntul la 188 USD.

MOBILA

Masa Mobius

Vezi adj. 16

O masă cu o singură suprafață la care poți sta, sta și sta confortabil.

Raft Infinity

Vezi adj. 17.

Designerul Job Kelevius a spart modelul când și-a proiectat biblioteca Infinity. Folosind conceptul matematic de Lemniscate și ceva similar cu banda Möbius, designerul a întruchipat conceptul fizic de infinit în Raftul Infinit. Asta înseamnă că, dacă ai citit toate cărțile de pe acest raft, consideră că ai înțeles întreaga infinitate a literaturii.

Canapea Mobius

Vezi adj. 18.

Născut sub motto-ul „Scaun dublu – dublă plăcere”, scaunul de canapeaMoebiusDublaFotoliucreat de designerGaebronzatVandeWyerdin Belgia și aduce o viziune proaspătă asupra mobilierului pentru îndrăgostiți.

LOGOS

Logo-ul companiei Woolmark

Vezi adj. 19.

Logo-ul a fost creat în 1964 ca urmare a unui concurs de design. Membru al juriuluiFrancoGrignaninu a putut rezista și și-a oferit propria versiune, ascunzându-se sub un pseudonimFrancescoseraglio. Acest logo seamănă cu o bandă Mobius și este un simbol al eternității și flexibilității companiei.

Simbol de reciclare

Vezi adj. 20.

Simbolul internațional pentru reciclare este banda Möbius. Reciclare (alți termeni: reciclare, reciclare a deșeurilor, reciclare și reciclare)- reutilizarea sau repunerea în circulație a deșeurilor industriale sau a gunoiului. Cele mai frecvente sunt secundare, terțiare și T. e. reciclarea la o scară sau alta a materialelor precum sticlă, hârtie, aluminiu, asfalt, fier, țesături și diverse tipuri de plastic. Folosit și din cele mai vechi timpuri în agricultură deșeuri organice agricole și menajere.

Simbol matematică

Vezi adj. 21.

Fâșia Möbius este considerată un simbol al matematicii moderne, deoarece el a fost cel care a dat impuls noilor cercetări matematice.

Imbracaminte si incaltaminte

Pantofi

Vezi adj. 22.

Fondată în 2003 de arhitectul Ram Di Koolhaase și cizmarul Galahad ClarkUnitNudeste specializată în producția de pantofi inovatori de designer. Una dintre cele mai de succes dezvoltări ale companiei sunt pantofiiMobius , numit după geometrul August Möbius și ideea sa de suprafață unilaterală. Ideea pantofilor este aceasta: partea superioară din piele a pantofilor și talpa sunt o singură panglică, răsucite într-un anumit fel.

eșarfă Mobius

Vezi adj. 23.

Un lucru interesant este eșarfa Möbius care apare în garderoba secolului XXI. Puteți face singur o eșarfă Möbius legând capetele eșarfei și răsucind-o cu o tură.

Pictura

Graffiti

Vezi adj. 24.

O bandă modernă Möbius este pictată pe un perete din Praga, Republica Cehă.

 Două tipuri de vehicule se deplasează de-a lungul centurii: tancuri și echipamente de construcție a drumurilor civilizație modernă: distruge-construieste-distruge-construieste..

ARHITECTURĂ

Clădirea bibliotecii

Vezi adj. 25.

În prezent, se analizează un proiect de construire a unei biblioteci sub forma unei benzi Möbius în Kazahstan.

Curbele clădirii formează o bandă Möbius, astfel spațiul interior curge în exterior și invers; într-un mod similar, pereții se transformă în acoperiș, iar acoperișul se transformă din nou în pereți. Lumina naturală pătrunde în coridoarele interioare prin deschideri geometrice din carcasa exterioară, creând spații frumos luminate ideale pentru lectură.

Atracții

Vezi adj. 26.

Plimbarea cu montagne russe seamănă cu forma unei benzi Mobius. La Moscova există cel mai mare roller coaster inversat din lume, unde o persoană stă pe un scaun suspendat, iar picioarele sunt în aer. Viteză - 81 km/h, înălțime 30 m Înălțimea, în comparație cu analogii străini, este mică, dar se plătește mai mult cu abundența de spirale, inele și bucle.

Rolă de film

Vezi adj. 27.

În 1923, a fost eliberat un brevet inventatorului Lee de Force, care a propus înregistrarea sunetului pe film fără a schimba rolele, din ambele părți simultan.

Casetă

Vezi adj. 28.

Casetele au fost inventate pentru magnetofone, unde banda este răsucită și lipită într-un inel, ceea ce face posibilă înregistrarea sau citirea informațiilor din ambele părți simultan, ceea ce crește capacitatea casetei și, în consecință, timpul de redare.

Mașină Toyota MOB

Vezi adj. 29.

Banda Möbius este proiectată de designerul spaniol Jorge Marti Vidal și combină frumusețea și misterul unei benzi Möbius. Forma unică a caroseriei oferă mașinii de curse o aerodinamică bună

Imprimanta matriciala

Vezi adj. treizeci.

În multe imprimante matriciale, panglica de cerneală are și forma unei benzi Mobius pentru a-și crește resursele.

Rezistorul Möbius

Vezi adj. 31.

Acesta este un element electronic nou inventat, care nu are inductanță proprie.

Cureaua de slefuit

Vezi adj. 32.

În 1969, inventatorul sovietic Gubaidullin a propus o bandă de șlefuit fără sfârșit sub forma unei benzi Möbius.

Concluzie

Banda Möbius este prima suprafață unilaterală descoperită de un om de știință. Mai târziu, matematicienii au descoperit o serie întreagă de suprafețe unilaterale. Dar

acesta, chiar primul, care a pus bazele unei întregi direcții în geometrie, continuă să atragă atenția oamenilor de știință, inventatorilor, artiștilor și studenților noștri. Am fost foarte interesat de proprietățile deschise ale benzii Möbius:

Banda Mobius are o margine, o latură

O bandă Möbius este un obiect topologic. Ca orice figură topologică, nu își schimbă proprietățile până când nu este tăiată, ruptă sau piesele sale individuale sunt lipite împreună.

O margine și o latură a benzii Mobius nu sunt legate de poziția sa în spațiu și nu sunt legate de conceptele de distanță.

Banda Möbius găsește numeroase aplicații în gătit, tehnologie, fizică, pictură, arhitectură, design de bijuterii și studiul proprietăților Universului. El a inspirat creativitatea multor scriitori și artiști.

μ( n) este definit pentru toate numerele naturale nși ia valori în funcție de natura expansiunii numărului n la factori simpli:

• μ( n) = 1 dacă n fără pătrate (adică niciun număr prim nu este divizibil cu pătrat) și descompunerea n un număr par de factori;
• μ( n) = − 1 dacă n lipsit de pătrate și descompunere nîn factori primi este format dintr-un număr impar de factori;
• μ( n) = 0 dacă n nu lipsit de pătrate.

Prin definiție, presupunem și μ(1) = 1.

Proprietăți și aplicații

Funcția Möbius este multiplicativă: pentru orice numere coprime AȘi b egalitatea este valabilă μ( Ab) = μ( A)μ( b) .

Suma valorilor funcției Möbius peste toți divizorii unui număr întreg n, nu este egal cu unu, este egal cu zero

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

De aici, în special, rezultă că pentru orice mulțime finită nevidă numărul de submulțimi diferite constând din numar impar elemente este egal cu numărul de submulțimi diferite formate dintr-un număr par de elemente - fapt folosit în demonstrație.

Funcția Möbius este legată de funcția Mertens prin relație

Funcția Mertens, la rândul ei, este strâns legată de problema zerourilor funcției zeta Riemann, vezi articolul Ipoteza Mertens.

inversiunea Mobius

Prima formulă de inversare a lui Möbius

Pentru funcții aritmetice fȘi g ,

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

atunci și numai când

.

A doua formulă de inversare a lui Möbius

Pentru funcții cu valoare reală f(X) Și g(X) definit la ,

atunci și numai când

.

Aici suma este interpretată ca .

Fundația Wikimedia. 2010.

Vedeți ce este „funcția Mobius” în alte dicționare:

Funcția Möbius μ(n) este o funcție aritmetică multiplicativă folosită în teoria numerelor și combinatorică, numită după matematicianul german Möbius, care a considerat-o pentru prima dată în 1831. Cuprins 1 Definiție 2 Proprietăți și aplicații ... Wikipedia

Funcția Möbius μ(n) este o funcție aritmetică multiplicativă folosită în teoria numerelor și combinatorică, numită după matematicianul german Möbius, care a considerat-o pentru prima dată în 1831. Cuprins 1 Definiție 2 Proprietăți și aplicații ... Wikipedia

Tip de transformări pe planul complex (gri) și sfera Riemann (neagră) Cuprins 1 Definiție 2 Proprietăți algebrice... Wikipedia

Fracționat funcție liniară funcţie de forma în care z = (z1,...,zn) sunt variabile complexe sau reale, ai,b,ci,d sunt coeficienţi complecşi sau reali. Adesea, termenul „funcție liniară fracțională” este folosit pentru cazul său special de transformare... ... Wikipedia

Seria Möbius este o serie funcțională de forma Această serie a fost studiată de Möbius, care a găsit o formulă de inversare pentru această serie: unde μ(s) este funcția Möbius ... Wikipedia

METODE DE CERCETARE MEDICALĂ- eu. Principii generale ale cercetării medicale. Creșterea și aprofundarea cunoștințelor noastre, dotarea din ce în ce mai tehnică a clinicii, bazată pe utilizarea celor mai recente realizări ale fizicii, chimiei și tehnologiei, complicația asociată a metodelor... ... Marea Enciclopedie Medicală

O afecțiune patologică care s-a dezvoltat în timpul nașterii și se caracterizează prin deteriorarea țesuturilor și organelor copilului, însoțită, de regulă, de o tulburare a funcțiilor acestora. Factorii care predispun la dezvoltarea R. așa-numitele sunt incorecți... ... Enciclopedie medicală

Lema.

Dovada. Căci afirmația este evidentă. Fie și extinderea canonică a numărului . Apoi, ținând cont că divizorii au forma , unde , ,…, ; , primim

deoarece

Teorema. (Formula de inversare aditivă Möbius.) Fie și fie funcții ale argumentului natural . Atunci dacă

Dovada. Avem

Lăsa . Apoi, cel fix parcurge toate valorile divizorilor numărului. Aceasta înseamnă că semnele de însumare din ultima sumă dublă pot fi inversate, adică.

Acum, având în vedere asta

primim

Există o altă formă a teoremei dovedite:

Teorema. (Formula de inversiune Möbius multiplicativă.) Lăsa

unde simbolul denotă produsul extins la toți divizorii numărului.

Dovada:

Exemple de utilizare a formulei de inversare Möbius:

Problemă cu numărul de secvențe de apel. Vezi: Sala M. Combinatorică. M.: Mir, , § .

Numărul de polinoame ireductibile de un grad dat peste un câmp finit de elemente. Vezi: Berlekamp E. Teoria codificării algebrice. − M.: Mir, 1970, Ch. 3.

Gluhov M. M., Elizarov V. P., Nechaev A. A. Algebra. În t. M.: Helios, . T. , § .

Pentru auto-studiu :

Inversia Möbius pe mulțimi parțial ordonate. Principiul includerii-excluderii caz special Formule de inversare Möbius. Vezi: Sala M. Combinatorică. M.: Mir, , § ; Bender E., Goldman J. Despre aplicațiile inversării lui Möbius în analiza combinatorie. În cartea: Probleme enumerative de analiză combinatorie. M.: Mir, 1971. S. - .

Comparații pentru combinații de numere

Fie un număr prim.

Lema.

Dovada. Când numărătorul din formulă

Consecinţă.

Dovada.

Lema. Fie , , , numere întregi nenegative și fie , . Apoi

Dovada. Avem

Pe de alta parte,

Comparând coeficienții la aceleași grade, obținem rezultatul cerut. ∎

− reprezentări de numere întregi nenegative și radix. (Aici este orice număr întreg pentru care , ). Pe mulțimea numerelor întregi nenegative definim relația de ordine parțială (relația precedenta), presupunând , dacă și numai dacă

teorema lui Lucas ( ).

Dovada. Conform lemei anterioare,

Unde , . Aplicând lema în mod repetat de numărul corespunzător de ori, obținem rezultatul dorit. ∎

Cometariu. Teorema nu este adevărată pentru cele neprime. De exemplu (vezi Berlekamp, ​​​​p.),

Consecinţă.

II . Structuri algebrice

II. 1. Seturi cu operații binare. Grupoizi, semigrupuri, monoizi

Operație algebrică binară(sau legea compoziției) pe un set nevid S numită cartografiere : , potrivirea unei perechi de elemente cu un element definit în mod unic. Multe operații pot fi specificate pe un set. (Dacă, de exemplu, desigur, atunci numărul de moduri este egal cu , unde este numărul de elemente în .) Dacă doriți să evidențiați una dintre ele, de exemplu, scrieți , . Un astfel de obiect se numește algebră binară, sau grupoid. În loc de , ei scriu adesea , iar operația în sine este notă cu un simbol ( , , , etc.).

Cometariu. Alături de operațiile binare, sunt luate în considerare și operații -are mai generale (unare la, ternare la etc.). Structurile (sistemele) algebrice asociate acestora constituie subiectul de cercetare al așa-ziselor. algebre universale.

Se numește o operație binară pe o mulțime asociativ, Dacă

, pentru orice , , .

Se numește un grupoid cu o operație asociativă semigrup.

Un exemplu de grupoid non-asociativ. Pe platou definim operatia ca . Operația este neasociativă: , dar .

Teorema. Dacă o operație binară pe o mulțime este asociativă, atunci valoarea expresiei nu depinde de plasarea parantezelor în ea.

Dovada. Cu , sau afirmația este evidentă. Căci este suficient să arătăm, folosind inducția, că

pentru orice , . Prin ipoteza inducției, plasarea parantezelor în

Nu este semnificativ; în special, .

Daca atunci.

Daca atunci

Partea dreaptă a egalității care se dovedește (1) este de asemenea redusă la aceeași formă. ∎

Elementul este numit neutruîn ceea ce priveşte operaţiunea, dacă

pentru oricine .

Se numește un semigrup cu un element monoid(sau semigrup cu identitate) și notează , , .

Un semigrup (grupoid) poate avea cel mult un element neutru: dacă

, sunt elemente neutre, atunci

Se numește un grupoid (semigrup). subgrupoid (subsemigrup) grupoid (semigrup), , dacă

Și pentru orice, .

În acest caz ei spun că submulțimea închis în funcţiune. Monoid se numește submonoid monoid , , , dacă și .

Elementul monoidului, , se numește reversibil, dacă există un element astfel încât (evident, atunci o vom inversa). Dacă elementul are aceeași proprietate, i.e. , apoi din egalități rezultă că elementul este de fapt unic (față de ). Acest lucru ne permite să vorbim despre verso element , la (invertibil) element , cu proprietăți: , .

Dacă , sunt elemente inversabile ale monoidului , , , atunci produsul lor este, de asemenea, un element inversabil, deoarece , . Evident, este un element inversabil. Prin urmare, există

Teorema. Mulțimea tuturor elementelor inversabile ale monoidului , , este închisă sub operația ∗ și formează un submonoid în , , .

Grupuri

Definiția unui grup. Se numește un monoid , , , ale cărui elemente sunt inversabile grup.

Cu alte cuvinte, un grup este o mulțime cu o operație binară pentru care sunt valabile următoarele axiome:

. (Funcționare închisă.) , .

. (Operația asociativitate.) ,

. (Existența unui element neutru.) ∃ .

. (Existența unui element invers.) .

Cometariu. Revenind la structurile algebrice introduse mai sus, observăm următoarea ierarhie între ele: perechea , este grupoid, dacă axioma este satisfăcută; semigrup, dacă axiomele și ; monoid, dacă axiome , și ; grup, dacă axiomele , , și .

Gradele elementelor cu proprietăți evidente sunt determinate în mod natural:

( o singura data),

; , ( , , .

În general, este imposibil să rearanjezi elementele dintr-o expresie (de ex. ). Dacă , atunci elementele sunt numite permutabil, sau naveta. Dacă oricare două elemente ale unui grup fac naveta, atunci grupul este numit comutativ, sau Abelian(în onoarea matematicianului norvegian Riehl Henrik Abel ( - )).

O operație într-un grup este cel mai adesea indicată fie printr-un simbol (adăugare), fie printr-un simbol (înmulțire). În acest caz, grupul este numit în consecință aditiv sau multiplicativ, elementul său neutru este respectiv zero() sau unitate(). Într-un grup aditiv, elementul, inversul elementului, este numit opus si este desemnat , dar in schimb ei scriu . Într-un grup multiplicativ, de obicei scriu în schimb, omițând simbolul operației.

Exemple de grupuri de aditivi. 1) , , , , , , , – grupuri aditive ale inelului și câmpurilor , , . Ei scriu pur și simplu , , , . 2) Orice inel prin adunare este un grup abelian. În special, inelul de polinoame ,…, ] și inelul de matrice de ordine peste un câmp sunt grupuri abeliene. 3) Oricare spațiu vectorial peste un câmp în ceea ce privește adăugarea este un grup abelian. 4) , 1,…, – un sistem complet de resturi modulo cel puțin nenegative cu operația de adăugare modulo.

Exemple de grupuri multiplicative. 1) , , sunt grupuri multiplicative de câmpuri , , . 2) este mulțimea elementelor inversabile ale oricărui inel cu unitate sub înmulțire. În special, = ; , este mulțimea matricelor inversabile din . 3) − toate rădăcinile (reale și complexe).

, , 1,…, , − unitate imaginară,

ecuația este un grup abelian multiplicativ. 4) - mulțimea rotațiilor unui -gon regulat în plan și în spațiu - un grup necomutativ (pentru ).

Mai mult, forma multiplicativă de înregistrare a operației este mai des folosită. Grupul este de obicei desemnat printr-o singură literă fără a specifica operația. Se numește mulțimea tuturor elementelor unui grup setul principal al grupuluiși este notat cu aceeași literă. Dacă setul de bază este finit, atunci grupul este numit final; altfel se numeste fără sfârşit. Elementul numeric al unui grup finit se numește său în ordine. Se numește un grup de ordinul 1 singur, sau T rival. Se spune că are un grup infinit ordine infinită . Pentru a indica ordinea grupului (cardinalitatea setului principal), sunt folosite simbolurile egale Card (număr cardinal) și ().

Dacă , sunt submulțimi (ale mulțimii principale) ale grupului, atunci punem

, , .

Subgrup a unui grup este o submulțime în care este el însuși un grup în raport cu aceeași operație ca în . Cu alte cuvinte, o submulțime este un subgrup dacă și numai dacă ( unu în ) și este închisă sub înmulțire și reciprocă, i.e. , (de fapt aici sunt chiar și egalități). Dacă este un subgrup în , atunci scrieți ; dacă în același timp, atunci se numește proprii subgrup și acesta este notat ca .

Funcția Möbius  (n), Unde n– un număr natural, ia următoarele valori:

Funcția Möbius vă permite să scrieți funcția Euler ca o sumă:

Însumarea este peste toți divizorii lui n (și nu doar peste divizori primi).

Exemplu. Să calculăm φ (100) folosind funcția Möbius.

Toți divizorii lui 100 sunt (1, 2, 4, 5, 10, 20, 25, 50, 100).

(2) = (-1) 1 = -1 (doi au un divizor prim – 2)

(4) = 0 (4 este împărțit la pătratul a doi)

(5) = (-1) 1 = -1 (5 are un divizor prim – 5)

(10) = (-1) 2 = 1 (10 are două divizor prim– 2 și 5)

(20) = 0 (20 împărțit la pătratul a doi)

(25) = 0 (25 împărțit la pătratul a cinci)

(50) = 0 (50 este divizibil cu 2 2 și 5 5)

(100) = 0 (100 este divizibil cu 2 2 și 5 5)

Prin urmare,

Proprietatea funcției Möbius:.

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

16 O teoremă asupra numărului de moduri de a selecta k-elemente, dintre care nu există două adiacente, din n elemente aranjate pe rând. Demonstrați obținând o formulă de recurență.

17 Numărul de combinații cu repetări

Număr r-combinatii cu repetari din n-multimile sunt egale

.

– demonstrarea utilizând o formulă de recurență.

Metoda se bazează pe obținerea unei formule care vă permite să calculați pas cu pas valorile cantității dorite, pe baza valorilor inițiale cunoscute și a valorilor calculate în pașii anteriori.

Formula de recurențăr -a ordine– formula formei

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

Formula exprimă la n>r fiecare membru al secvenței ( A i) prin precedent r membrii. Construcția unei formule recurente constă din următorii pași.

1. Productie condiții inițiale pe baza oricăror relații evidente.

Să notăm prin f(n,r). Este evident că

2. Raționament logic. Să reparăm un element din set S. Apoi relativ la oricare r- combinatii cu repetari din n-seturi S putem spune dacă conține un element fix dat sau nu.

Dacă conţine, apoi restul ( r-1) elementul poate fi selectat f(n,r-1) moduri.

Dacă nu contine(acest element nu este în selecție), atunci r- o combinație formată din elemente ( n-1)-seturi (set S cu excepția acestui element fix). Numărul de astfel de combinații f(n-1,r).

Deoarece aceste cazuri se exclud reciproc, apoi conform regulii sumei

3. Verificarea formulei pe unele valori și deducerea unui model general.

1) Să calculăm f (n ,0) . Din (2) rezultă

Apoi f(n,0)=f(n,1)-f(n-1,1). De la (1) f(n,1)=n,f(n-1,1)=n-1.

Prin urmare, 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 =.

(suma progresiei aritmetice)

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) = … =

(suma progresiei geometrice)

5) f (n ,4) =

Pe baza unor cazuri particulare, se poate presupune că

4. Verificarea conditiilor initiale folosind formula rezultata.

,

care este în concordanță cu (1) #

19, 20) Numărul de arbori binari cu n vârfuri este egal cu C(n), unde C(n) este al n-lea număr catalan.

Numărul de arbori binari cu n vârfuri se numește număr catalan, care are multe proprietăți interesante. Al N-lea număr catalan se calculează folosind formula (2n)! / (n+1)!n!, care crește exponențial. (Wikipedia oferă mai multe dovezi că aceasta este o formă a numărului catalan.) Număr de arbori binari de o dimensiune dată 0 1 1 1 2 2 4 14 8 1430 12 208012 16 35357670

Substituţie

Mergi la: navigare, căutare

Acesta este un articol despre substituție ca operație sintactică petermice . S-ar putea să te interesezerearanjare .

ÎN matematicăȘi informatică substituţie- aceasta este o operațiune sintacticînlocuirea subtermenilor unui dat terma alți termeni, conform anumitor reguli. De obicei vorbim despre înlocuirea unui termen în loc de variabil.

Definiții și notații

Nu există o notație universală convenită pentru substituție și nici o definiție standard. Conceptul de substituție variază nu numai în cadrul secțiunilor, ci și la nivelul publicațiilor individuale. În general, putem evidenția substituirea contextuluiȘi înlocuire „în loc de”. În primul caz, se indică locul în termen în care are loc înlocuirea context, adică o parte din terma care „înconjoară” acest loc. În special, acest concept de substituție este utilizat în rescriere. A doua opțiune este mai comună. În acest caz, substituția este de obicei specificată de o funcție dintr-un set de variabile într-un set de termeni. A indica actiuni de substitutie, de regulă, folosiți notație postfixă. De exemplu, înseamnă rezultatul unei acțiuni de substituție asupra unui termen.

În majoritatea covârșitoare a cazurilor, se cere ca substituția să aibă un purtător finit, adică ca mulțimea era finită. În acest caz, poate fi specificat prin simpla enumerare a perechilor „valoare-variabilă”. Deoarece fiecare astfel de substituție poate fi redusă la o secvență de substituții care înlocuiesc doar o variabilă fiecare, fără pierderea generalității putem presupune că substituția este dată de o pereche. „valoare-variabilă”, care este ceea ce se face de obicei.

Ultima definiție a substituției este probabil cea mai tipică și folosită frecvent. Cu toate acestea, nu există nici o singură notație general acceptată pentru aceasta. Cel mai adesea folosit pentru a indica substituția Aîn loc de X V t se utilizează înregistrarea t[A/X], t[X:=A] sau t[X←A].

Substituția variabilă înλ-calcul

În calculul λ, substituția este determinată de inducția structurală. Pentru obiecte arbitrare și o variabilă arbitrară, se calculează rezultatul înlocuirii unei apariții libere arbitrare substituţieși se determină prin inducție asupra construcției:

(i) baza:: obiectul se potrivește cu variabila. Apoi;

(ii) baza:: obiectul se potrivește constant. Apoi pentru cele atomice arbitrare;

(iii) pas: : obiectul este neatomic și are aspectul unei aplicații. Apoi;

(iv) pas:: obiectul este non-atomic și este o abstractizare. Apoi [;

(v) pas:: obiectul este non-atomic și este, de altfel, o abstractizare. Apoi:

pentru andor;

Înlocuirea variabilelor în programare

Substituţie variabil ( Engleză substituţie) V programare aplicativă se înțelege după cum urmează. Pentru a calcula valoarea unei funcții f asupra argumentului v se aplică intrarea f(v)), Unde f determinat de proiectare f(x) = e. Record f(v)în acest caz înseamnă că în expresie e se întâmplă substituţie, sau substituție variabilă X pe v. Înlocuirea se efectuează în conformitate cu semantica calculelor.

Substituţie variabil ( Engleză misiune) V programareînțeles ca misiune. Operatorul de atribuire este o manifestare a efectului de blocaj von Neumann pentru limbajele de programare tradiționale . Liber de asta sisteme de calcul aplicative.

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

21 Funcții de generare.Funcție generatoare (numărător) și funcție generatoare de enumerare pentru combinații fără repetiții.

Funcții generatoare: 1) Z-transforme 2) generator 3) funcție generatoare 4) funcție generatoare a secvenței (a r ) pe baza (g r ) - funcția f, atunci când este extinsă într-o serie în funcții de bază fixă ​​(g r ), se formează această succesiune de coeficienţi (a r ). …………*)

Această serie este formală. Numele formal înseamnă că tratăm formula *) ca o notație convenabilă pentru secvența noastră - în acest caz, nu contează pentru ce valori (acțiuni și complexe) converge. Rolul lui t se rezumă la distingerea coeficienților șirului A0, A1,...Ar....prin urmare, în teoria funcțiilor generatoare, valorile acestei serii nu sunt niciodată calculate pentru o anumită valoare a variabila t. Doar unele operații sunt efectuate pe astfel de serii, apoi se determină doar unele operații pe astfel de serii, iar apoi se determină coeficienții pentru puteri individuale ale variabilei t.

De obicei ca

22 Funcția generatoare. Funcție generatoare (numărător) și funcție generatoare de enumerare pentru combinații cu repetiții.

Unitate de producție pentru:

Regula de construcție

1) Dacă un element de tip i poate fi inclus în combinațiile K 1 sau K 2 sau... K i ori, atunci are un multiplicator corespunzător

3) Rămâne de găsit coeficientul. la

funcția de generare exponențială pentru regula de construcție a plasamentelor

25) Numerele combinatorii includ și numere Stirling de primul şi al doilea fel. Aceste numere sunt definite ca coeficienți în egalități

și au o semnificație combinatorică simplă – egală cu numărul de elemente ale grupului de permutare care sunt produse de exact k cicluri disjunse și egale cu numărul de partiții n- element pus pe k submulţimi nevide. Este evident că. Se numește o sumă similară de numere Stirling de al doilea fel n- Numărul clopoțelului și egal cu numărul tuturor partițiilor n-set de elemente. Formula de recurență este valabilă pentru numerele Bell.

La rezolvarea problemelor combinatorii este adesea util formula de includere-excludere

ceea ce permite găsirea cardinalităţii unirii mulţimilor dacă se cunoaşte cardinalitatea intersecţiilor acestora. Să folosim formula de includere-excludere pentru a obține o formulă explicită pentru numerele Stirling de al doilea fel.

Numere Stirling de primul fel

Material de pe Wikipedia - enciclopedia liberă

Mergi la: navigare, căutare

Numere Stirling de primul fel(nesemnat) - cantitate permutări Ordin n Cu k cicluri.

Definiție

Numere Stirling de primul fel(cu semn) s(n, k) se numesc coeficienţi polinom:

Unde ( X) n - Simbolul Pochhammer (factorial descrescător):

După cum se poate vedea din definiție, numerele au un semn alternativ. Valorile lor absolute specifică numărul permutări set format din n elemente cu k cicluri.

Relația de recurență

Sunt date numere Stirling de primul fel recurent raport:

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

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

pentru 0< k < n.

Dovada.

Pentru n=1 această egalitate este verificată direct. Lasă permutarea ( n-1) ordinul se descompune în k cicluri. Număr n poate fi adăugat după orice număr din bucla corespunzătoare. Toate permutările rezultate sunt diferite și conțin k cicluri, numărul lor ( n-1)· s(n-1, k). Din orice permutare ( n-1) ordinul care conține k-1 ciclu, se poate forma o singură permutare n comanda care contine k cicluri prin adăugarea unui ciclu format dintr-un număr singular n. Evident, această construcție descrie toate permutările n-ordinea care contine k cicluri. Astfel egalitatea este dovedită.

Exemplu

Primele rânduri:

ÎN combinatorică Număr Stirling de al doilea fel din n De k, notat cu sau, este numărul de neordonate despărțitori n-elementar seturi pe k submulţimi nevide.

Formula de recurență

Numerele Stirling de al doilea fel satisfac recurent raport:

Pentru n ≥ 0,

Pentru n > 0,

Formula explicita

Exemplu

Valorile inițiale ale numerelor Stirling de al doilea fel sunt date în tabel:

Proprietăți

Bijectiv O mapare este o mapare care are proprietățile de a fi injectivă și surjectivă în același timp.

1. Să ne amintim mai întâi definiția importantei funcții Möbiu teoretice de numere

1 dacă n = 1

µ (n)=0, dacă există un număr prim p, p2 n (-1)k, dacă n = p1 ... pk este produsul a k factori primi diferiți.

Să demonstrăm proprietatea principală a funcției Möbius:

Teorema 1.

♦ Dacă n = 1, atunci singurul divizor este d = 1 și (1) este adevărată, deoarece µ (1) = 1. Acum să fie n > 1. Să-l reprezentăm sub forma

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

unde pi, i 1, k sunt numere prime, si sunt puterile lor. Dacă d este un divizor al lui n, atunci d = p1 d 1 pd 2 2 K pd k k ,

unde 0 ≤ di ≤ si, i 1, k. Dacă di > 1 pentru unele i 1, k, atunci µ (d) = 0. Aceasta înseamnă că în (1) trebuie să luăm în considerare numai acele d pentru care di ≤ 1, i 1, k. Fiecare astfel de divizor co-

constă din produsul a r numere prime diferite, unde r 1, k și contribuția sa la sumă

(1) este egal cu (-1)r și sunt k în total. Astfel, primim

			µ (d) = 1 −	K + (− 1) k	0. ♦
			Teorema 2. (Formula de inversare Mobius). Fie f(n) și g(n) funcții naturale
argument ral. Apoi egalitatea
					∑f(d)
este adevărată dacă și numai dacă egalitatea este adevărată
					∑ µ (d)g(

♦ Fie (2) adevărată pentru orice n. Apoi

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

d ′ d n

Înlocuind în partea dreaptă a lui (3), obținem

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

Însumarea dublă din dreapta se efectuează asupra tuturor perechilor d, d′ astfel încât d d′ n. Dacă alegeți d ′ , atunci d va trece prin toți divizorii d n ′ . Prin urmare

∑ µ (d)g(

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

d′

d′

d′

n > d′

Dar conform (1) avem ∑

µ (d′ ) =

n = d′

d′

d′

Aceasta înseamnă că egalitatea (3) este stabilită. Acum să fie (3) adevărată pentru orice n. Apoi

∑ f(d) =

∑ ∑ µ (d′ )g(

) , d′′ = d d ′ - este un divizor al lui n și suma dublă poate

d′

n d′

fi rescris ca

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

∑ g(d′′ )

∑ µ (d′ )

d′′

n d′

d′′

d′′

d′

d′′

Conform (1), ultima sumă se transformă în unitate în cazul d′′ = n, în alte cazuri

În orice caz, este zero. Aceasta dovedește (2). ♦ 2. Luați în considerare o aplicare a inversiunii de Möbius.

Să fie dat un alfabet A cu litere s. Există sn cuvinte de lungime n într-un alfabet dat. Pentru fiecare cuvânt w0 = a1 a2 … pot fi definite n - 1 cuvinte

w1 = a2 a3 … an a1 , w2 = a3 a4 … a1 a2 , … , wk-1 = an a1 … an-1 , obținute unul de la altul prin deplasări ciclice. Pe mulţimea tuturor sn cuvinte introducem o relaţie de echivalenţă: declarăm două cuvinte echivalente dacă unul este obţinut din celălalt printr-o deplasare ciclică. Ne va interesa numărul de clase care conțin exact n cuvinte. Această problemă apare în teoria sincronizării codurilor.

Vom numi un cuvânt w degenerat dacă clasa de echivalență care conține w este formată din mai puțin de n cuvinte. Numim w periodic dacă cuvântul u există și numar natural m, astfel încât w = u u … u (m ori).

Teorema 3. Un cuvânt w este periodic dacă și numai dacă este degenerat.

după cum putem lua o 1 a 2 … a p și ca m =

♦ Este clar că dacă w este periodic, atunci este degenerat. Să fim degenerați. Fie p întregul minim astfel încât w = wp. Atunci dacă

w = a1 a2 … an , apoi wp = a1+p a2+p … an+p (indici modulo n). De aici obținem că în n p . (Este ușor de observat că p n). ♦ Tapet

semnificativ prin M(d) - numărul de pătrate care conțin d cuvinte. Din precedenta avem

d n. Astfel, formula este valabilă∑ dM(d) = s n . d n

Să aplicăm formula de inversare a lui Möbius pentru cazul g(n) = sn , f(d) = dM(d). Apoi primim

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

∑ µ (d)sn d

Astfel, M(n) este numărul care ne interesează. Dacă n = p este un număr prim, atunci

− s)

Există o versiune multiplicativă a inversiunii Möbius. Corect

Teorema 4. Fie f(n) și g(n) funcții ale unui argument natural legate în mod corespunzător

purtare

f(n) = ∏g(d)

µ(n

g(n) = ∏f(d)

Și invers, din (5) urmează (4).

Folosind formula de inversare a lui Möbius, se poate rezolva problema practic importantă a numărului de polinoame ireductibile de grad fix peste un câmp finit. Fie GF(q) un câmp de q elemente și m un număr natural. Apoi pentru număr

Φ m (q) de polinoame ireductibile pe câmpul GF(q), se respectă următoarea formulă:

Să prezentăm un tabel cu primele câteva valori ale funcției Φ m (2)

Φ m (2)

§ 5. Permanente şi aplicarea lor la cele enumerative

1. Permanentele sunt folosite pentru a rezolva multe probleme combinatorii. Luați în considerare matricea numerică

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

Matricea permanentă A (desemnarea - per A) este determinată de egalitate

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

unde însumarea se realizează peste toate n-permutările m elemente 1, 2, m. Cu alte cuvinte, permanenta matricei este egală cu suma produselor elementelor luate câte unul din fiecare rând și coloane diferite.

Din formula (1) urmează unele proprietăți evidente ale permanentului, similare cu proprietățile determinantului pentru matrice pătrată.

1. Dacă una dintre rânduri(n× m)-matricea A (n ≤ m) este formată din zerouri, apoi pe A = 0. Pentru n = m același lucru este valabil și pentru coloane.

2. Când toate elementele unuia dintre rândurile matricei A sunt înmulțite cu un anumit număr, valoarea permanentului A este înmulțită cu același număr.

3. Un permanent nu se schimbă atunci când rândurile și coloanele sale sunt rearanjate.

Să notăm cu Aij matricea obținută din A prin ștergerea rândului i și coloanei j.

4. Este valabilă formula de descompunere a permanentului din al-lea rând: per A = ai1 per Ai1 + ai2 per Ai2 + ... + target per Aim (2)

astfel, multe proprietăți ale permanenților sunt similare cu cele ale determinanților.

Cu toate acestea, proprietatea principală a determinanților det(A B) = detA detB nu este satisfăcută pentru permanenți, iar această împrejurare face calculul lor foarte dificil.

De exemplu,

					2, per
Cu toate acestea, 4 = per						≠ per

Să luăm în considerare una dintre cele mai importante aplicații ale conceptului de permanent în problemele combinatorii.

dachas. Fie X = (x1, xm) o mulțime finită și X1, …, Xn un sistem de submulțimi

În acest caz, se spune că elementul xi reprezintă mulțimea Xi. Necesitatea de a găsi un sistem de reprezentanți diferiți apare atunci când se rezolvă multe probleme aplicate. Luați în considerare următoarea problemă de codare. Să fie o propunere, adică un set ordonat de cuvinte într-un anumit alfabet. Este necesară codificarea acestei propoziții, astfel încât fiecărui cuvânt să i se atribuie o literă, iar această literă trebuie să facă parte din acest cuvânt, iar litere diferite trebuie să corespundă unor cuvinte diferite.

Exemplu: Propoziția a bc ab d abe c de cd e poate fi codificată ca abecd. În același timp, propoziția ab ab bc abc bcd nu poate fi codificată în acest fel, deoarece primele patru cuvinte împreună conțin doar trei litere.

Pentru un sistem de mulțimi X1 , … , Xn definim matricea de incidență A = (aij), i = 1, n,

				1 dacă xi
		a ij =
				0 altfel.
		Corect
		Teorema 1. Fie A = (aij), i =					(n ≤ m) matrice de incidență

setează X1, …, Xn, unde Xi X, i = 1, n, X = (x1, …, xm). Apoi pentru numărul de sisteme

reprezentanții personali R(X1 , … , Xn ) ai mulțimilor X1 , … , Xn este valabilă următoarea egalitate:

R(X1 , … , Xn ) = pe A

♦ Într-adevăr, întrucât în ​​matricea A elementul aij = 1, dacă xj Xi și aij = 0,

dacă xj

K, xi

) elementele X este un sistem de diverse pre-

Xi, apoi mulțimea (xi

sufixe pentru X1 , … , Xn

daca si numai daca a1i

K ,a ni

politisti a1i

K ,a ni

sunt în coloane diferite ale matricei A. Să însumăm numerele

a1i ,K ,a ni

peste toate n-permutările elementelor 1, 2, …, m. Apoi ajungem de la o sută

rons, numărul de sisteme de reprezentanți diferiți pentru X1, ..., Xn și, pe de altă parte, valoarea per-

matricea manentei A. ♦

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

Consecinţă. Un sistem de reprezentanți diferiți pentru X1, …, Xn există dacă și numai dacă pentru matricea corespunzătoare incidentul A este satisfăcut:

Deoarece în formula (1) există m(m - 1) ... (m - n +1) termeni, calcularea permanentului pe baza definiției este dificilă. Să prezentăm o formulă generală în acest scop.

2. Să ne limităm la a considera matricele numerice pătrate A = (aij), i, j = 1, n.

Atunci pe A = ∑

(i1 ,K ,in )

unde suma se extinde peste toate permutările i1 , … , în elemente

1, 2, …, n. Să aplicăm formula de includere-excludere pentru a calcula permanenta matricei A. Atribuim fiecărei mulțimi i1,..., într-o pondere egală cu a1i 1,K,a ni n.

Aceasta înseamnă că permanentul A este suma greutăților acelor mulțimi care corespund permutărilor. Să introducem n proprietăți P1 , … , Pn pe mulțimea tuturor colecțiilor i1 , i2 , … , în din 1, 2, … , n, unde proprietatea Pi înseamnă că nu există niciun element i în colecția i1 , … , în. Astfel, permanentul A este suma greutăților mulțimilor i1, ..., în, care nu au niciuna dintre proprietățile P1, ..., Pn. Rămâne de determinat suma greutăților W(Pi 1 ,K , Pi k ) a mulțimilor cu k proprietăți

Pi 1 ,K , Pi k . Avem pentru suma greutăților W(0) tuturor mulțimilor 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

unde semnul ^ deasupra unui element al matricei A înseamnă că acest element trebuie omis. În mod similar pentru sij (i< 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)

Acum, folosind formula de includere-excludere, obținem formula Raiser pentru permanent A:

pe 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

Calculul permanentului folosind formula Raiser poate fi organizat în așa fel încât să necesite

(2n - 1)(n - 4) înmulțiri și (2n - 2)(n + 1) adunări. Deși această valoare crește rapid cu n, această formulă oferă cel mai mult metoda eficienta calculele permanentelor.

3. Să clarificăm acum problema condițiilor pentru ca matricea permanentă (0, 1) să fie egală cu zero. Să ne limităm la cazul unei matrice pătrate.

Teorema 2. Fie A = (aij ), i, j = 1, n o matrice (0, 1) de ordinul n. Apoi

pe A= 0 dacă și numai dacă A conține o submatrice de zerouri de dimensiunea s × t, unde s + t = n + 1.

♦ Fie ca o astfel de submatrice zero să existe în A. Deoarece permanentul nu se schimbă din cauza permutărilor rândurilor și coloanelor, putem presupune că această submatrice este situată în colțul din stânga jos, adică.

unde O - (s × t) este o matrice de zerouri, submatricea B are dimensiunea (n - s) × t. Fiecare membru al permanentului A trebuie să conțină un element din primele t coloane. Prin urmare, dacă căutăm un termen pozitiv al permanentului, atunci elementele acestor coloane trebuie să aparțină unor rânduri diferite perechi cu numerele 1, 2, ..., n - s. Cu toate acestea, n - s = t - 1< t и поэтому данное условие выполнить нельзя, т.е. per A = 0.

Fie acum per A = 0. Demonstrăm teorema prin inducție pe n. Pentru n = 1 afirmația este evidentă (A = (0)). Să fie adevărat pentru toate ordinele mai mici decât n. Dacă A este o matrice zero de ordinul n, atunci afirmația este evidentă. Dacă A nu este o matrice zero, atunci fie aij = 1. Să scriem descompunerea lui A de-a lungul rândului i:

pe A = ai1 Ai1 + … + ain Ain

Deoarece per A = 0, atunci per Aij = 0. Dar Aij are dimensiunea (n - 1) × (n - 1) și prin ipoteza de inducție există o submatrice de zerouri de dimensiune

s1 × t1, cu s1 + t1 = n - 1 + 1 = n. Să rearanjam rândurile și coloanele astfel încât această submatrice zero să fie în colțul din stânga jos:

A → B =

unde O este submatricea zero de dimensiunea s1 × t1, s1 + t1 = n, C - are dimensiunea (n - s1) × t1, D -

are dimensiunea s1 × (n - t) . Aceasta înseamnă că matricele C și D sunt pătrate și au ordine (t1 × t1) și respectiv (s1 × s1). Conform definiției unui permanent, avem per B = per A și,

per B = per C per D și, prin urmare, din per A = 0 rezultă că fie per C = 0, fie per D = 0.

Fie per C = 0. Prin ipoteza de inducție, există o submatrice zero de dimensiune

u × v, unde u + v = t1 + 1. Fie situat în rânduri cu numerele i1, …, iu și coloane cu numere j1, …, jv. Să considerăm o submatrice B constând din rânduri

i1, …, iu, t1 + 1, …, n și coloanele j1, …, jv. Aceasta este o submatrice zero de dimensiune (u + n - t1) × v,

unde u + n - t1 + v = n + +1. Deci, matricea B conține o submatrice zero de dimensiunea s × t, unde s + t = n + 1. Deoarece matricele A și B diferă în permutarea rândurilor și coloanelor, teorema este demonstrată. ♦

Să considerăm acum un caz special important al matricei A. Să notăm cu A(k, n) o matrice de 0,1 elemente de dimensiune n × n cu k pentru fiecare rând și fiecare coloană (k > 0).

Teorema 3. Pentru orice matrice A(k, n) pe A(k, n) > 0.

♦ Să presupunem contrariul, că per A(k, n) = 0. Atunci, prin teorema 2, există un zero-

submatrice de dimensiunea s × t, unde s + t = n + 1. Apoi, rearanjand rândurile și coloanele matricei A(k, n) obținem matricea

unde O este matricea zero (s × t).

Să numărăm numărul de unități din matricele B și D. Deoarece A(k, n) are k în fiecare rând și în fiecare coloană, atunci există exact k în fiecare coloană a lui B și în fiecare rând a lui D.

unitati. Există n k unități în total în A(k, n), deci nk ≥ tk + sk = (t + s)n. Pe aici

som, n ≥ t + s, ceea ce este imposibil, deoarece s + t = n + 1 Din această contradicţie rezultă că

validitatea declarației. ♦ Se dovedește în mod similar

Teorema 3a. Fie A o matrice (0,1) de dimensiunea n× m (n≤ m). Atunci perA = 0 dacă și numai dacă conține o submatrice zero de dimensiunea s×t, unde s+t=m+1.

4. Să luăm acum în considerare aplicarea problemelor luate în considerare la construirea la-

Tina pătrate. latină (n × m)-dreptunghi peste mulțimea X=(x1 ,…,xm )

se numește (n× m) -matrice a elementelor X, în care fiecare rând este o n-permutare a lui X, iar fiecare coloană este o m-permutare a mulțimii X. Pentru n=m, dreptunghiul latin se numește pătrat latin.

Este clar că pentru n=1 numărul dreptunghiurilor latine 1×m este egal cu m!. Când n=2, după ce primul rând este selectat, orice permutare poate fi luată ca al doilea rând.

produs nou care îl contrazice pe cel ales. Numărul de astfel de permutări este Dm, deci numărul 2× m este

de dreptunghiuri latine este egal cu m! Dm.

O întrebare firească apare în legătură cu construcția inductivă a pătratelor latine. Să construim un dreptunghi latin (n× m) (n< m). Можно ли его расширить до ((n+1)× m) -прямоугольника добавлением (n+1)-й строки?

Corect

Teorema 4. Fiecare dreptunghi latin (n× m) n

♦ Fie X=(x1,…,xm) și un dreptunghi L-latin (n×m) cu elemente din X. Să considerăm o mulțime de mulțimi A1,…,Am unde Ai sunt elementele coloanei i a lui dreptunghiul latin L. Fie A matricea de incidență a sistemului de mulțimi A1 ,… ,Am . Are dimensiunea m×m, iar fiecare rând al matricei A conține exact n, deoarece Ai = n, i = 1, m. Fiecare element xi X poate apărea în coloanele lui L de cel mult m ori, altfel ar exista un rând în care acest element apare de două ori. Numărul total de elemente

L este egal cu m n, deci fiecare element xi X apare exact de n ori în coloane. Rezultă că fiecare coloană a matricei A conține exact n. Să considerăm acum matricea A obţinută prin înlocuirea fiecăruia cu un zero şi fiecare zero cu unul.

Matricea A este matricea de incidență a sistemului de mulțimi X1, …, Xn, unde Xi = X\Ai,

i = 1, m. Conține m - n unități în fiecare rând și în fiecare coloană. Prin teoremă

> 0. Fie ai1

…un mi

≠ 0 . Atunci avem xi X1 ,K , xi

Xm și toate elementele

xi ,K ,xi

perechi diferite. Linia

xi ,K ,xi

poate fi luat ca (n + 1)-lea

pentru un dreptunghi latin (n × m) L. Continuând acest procedeu, obținem un latin

pătrat cerul. ♦

Să notăm l n - numărul de pătrate latine de ordinul n, cu elemente din mulțimea X = (1, 2, ..., n), în care elementele primei coloane și ale primului rând sunt în ordine naturală. Iată un tabel cu mai multe valori cunoscute ale numărului l n:

5. O matrice A = (aij) de dimensiune n × n cu elemente reale, nenegative se numește de două ori stocastică, Dacă