Алмаштырма

1,2, ...n һандарының ҡабатланмайынса тәртипкә килтерелгән йыйылмаһы

Алмаштырма (рус. Перестановкакомбинаторикала — һандарының ҡабатланмайынса тәртипкә килтерелгән йыйылмаһы, ғәҙәттә күмәклегендә, һанына йыйылманан -сы элементты ярашлы ҡуйған биекция булараҡ трактовкалана. Шул уҡ ваҡытта һаны алмаштырманың оҙонлоғо тип атала[1].

Өс шарҙан 6 алмаштырма

Төркөмдәр теорияһында ирекле күмәклектең алмаштырмаһы тип был күмәклектең үҙ-үҙенә биекцияһы атала. Был мәғәнәлә «алмаштырма» һүҙенә синоним булараҡ ҡайһы бер авторҙар подстановка һүҙен ҡулланалар. (Башҡа авторҙар алмаштырманы яҙыуҙың күрһәтмә ысулын подстановка тип атай. Унан да мөһимерәк айырма шунда, подстановка - ул туранан-тура функция, ә алмаштырма - был функцияны эҙмә-эҙлелек элементтарына ҡулланыу һөҙөмтәһе ул.)

«Алмаштырма» термины тәүҙә нисектер урынлаштырылған объекттар алынғанға, ә тәртипкә килтереүҙең башҡа алымдары был объекттарҙы алмаштырып ҡуйыуҙы талап иткәнгә килеп тыуа[2].

Алмаштырма тип бер үк элементтарҙан торған, элементтарҙың урынлашыу тәртибе менән генә айырылған йыйылмалар атала[3].

Үҙсәнлектәре үҙгәртергә

  элементтан бөтә алмаштырмалар һаны   элементтан  -шар урынлаштырмалар һанына, йәғни   факториалға тигеҙ[4][5][6][7]:

 .

Функциялар композицияһы бер оҙонлоҡтағы алмаштырмаларҙа ҡабатлау ғәмәлен билдәләй:   Был ғәмәлгә ҡарата   элементтан алмаштырмалар күмәклеге төркөм төҙөй, уны симметрик тип атайҙар һәм ғәҙәттә   тип тамғалайҙар.

  элементтан теләһә ниндәй сикле төркөм   симметрик төркөмөнөң ниндәйҙер аҫтөркөмөнә изоморфлы (Кэли теоремаһы). Был ваҡытта һәр   элементы   элементтарында   тождествоһы менән бирелгән   алмаштырмаһы менән тиңләштерелә, бында   —  -ла төркөм операцияһы.

Бәйле билдәләмәләр үҙгәртергә

Алмаштырма вәкиле   — ул   күмәклегенең   тип билдәләнгән аҫкүмәклеге.

  алмаштырмаһының хәрәкәтһеҙ нөктәһе тип   сағылышының һәр хәрәкәтһеҙ нөктәһе, йәғни   күмәклегенең элементы атала.   алмаштырмаһының бөтә хәрәкәтһеҙ нөктәләре күмәклеге уның  -та вәкиленең ҡушымтаһы була.

  алмаштырмаһында Инверсия тип һәр шундай индекстар пары   атала, бында   һәм  . Алмаштырмала инверсиялар һанының йоплоғо алмаштырманың йоплоғон билдәләй.

Алмаштырмаларҙың махсус төрҙәре үҙгәртергә

  • Тождестволы алмаштырма — һәр   элементын үҙенә сағылдырыусы   алмаштырмаһы:  
  • Инволюция — үҙенә үҙе кире булған алмаштырма  , йәғни  
  • Буталыш — хәрәкәтһеҙ нөктәһе булмаған алмаштырма.
  •   оҙонлоғондағы Цикл тип   аҫкүмәклегенән башҡа бөтә   күмәклегендә тождестволы булған һәм   үтәлгән   подстановкаһы атала. Тамғаланышы:  .
  • Транспозиция — ике элементты урындары менән алмаштырыусы   күмәклеге элементтары алмаштырмаһы. Транспозиция оҙонлоғоғо 2 булған цикл була.

Подстановка үҙгәртергә

  күмәклегенең   алмаштырмаһы подстановка күренешендә яҙыла ала, мәҫәлән:

 

бында   һәм  .

Циклдар ҡабатландығы һәм алмаштырма тамғаһы үҙгәртергә

Теләһә ниндәй   алмаштырмаһы   оҙонлоғондағы киҫешмәүсе циклдар ҡабатландығына (циклдар композицияһына) тарҡатыла ала, шуның менән бергә ҡабатландыҡта циклдарҙың урынлашыу тәртибенә тиклем аныҡлыҡ менән берҙән-бер ысул менән. Мәҫәлән:

 

Шулай уҡ йыш ҡына алмаштырманың хәрәкәтһеҙ нөктәләрен 1 оҙонлоҡтағы үҙ аллы циклдарҙан ғибәрәт тип иҫәпләйҙәр һәм алмаштырманың цикллы тарҡалыуын улар менән тулыландыралар. Өҫтә килтерелгән миҫал өсөн бындай тулыландырылған тарҡатыу ошолай була:  . Төрлө оҙонлоҡтағы циклдар һаны, атап әйткәндә   һандар йыйылмаһы, бында   —   оҙонлоғондағы циклдар һаны, алмаштырманың цикл структураһын билдәләй. Шуның менән бергә   дәүмәле алмаштырманың оҙонлоғона тигеҙ, ә   дәүмәле циклдарҙың дөйөм һанына тигеҙ.   элементтан   циклы менән алмаштырмалар һаны беренсе төрҙәге тамғаһыҙ Стирлинг һаны   менән бирелә.

Теләһе ҡайһы цикл (киҫешмәүсе булыуы мотлаҡ түгел) транспозициялар ҡабатландығына тарҡатылырға мөмкин. Шул уҡ ваҡытта 1 оҙонлоҡтағы циклды (ысынында иһә тождестволы алмаштырма   булып торған) транспозицияларҙың буш ҡабатландығы йәки, мәҫәлән, теләһә ниндәй транспозицияның квадраты рәүешендә күрһәтергә мөмкин:     оҙонлоғондағы циклды   транспозициялар ҡабатландығына ошолай тарҡатырға мөмкин:

 

Циклдарҙың транспозициялар ҡабатландығына тарҡалмаһы берҙән-бер түгеллеген билдәләп китергә кәрәк:

 

Шулай итеп, теләһә ниндәй алмаштырма транспозициялар ҡабатландығына тарҡатылырға мөмкин. Быны күп ысулдар менән эшләргә мөмкин булһа ла, шундай бөтә тарҡатыуҙарҙа транспозициялар һанының йоплоғо бер төрлө. Был   алмаштырмаһының тамғаһын (алмаштырманың йоплоғо йәки алмаштырма сигнатураһы) ошолай билдәләргә мөмкинлек бирә:

 

бында   — ҡайһылыр   тарҡалмаһында транспозициялар һаны. Шуның менән бергә, әгәр   булһа  -ны йоп алмаштырма тип атайҙар, һәм, әгәр   булһа, таҡ алмаштырма тип атайҙар.

Эквивалентлы, алмаштырманың тамғаһы уның цикл структураһы менән билдәләнә:   элементтан,   циклдан торған   алмаштырмаһының тамғаһы

 -гә тигеҙ.

  алмаштырманың тамғаһы шулай уҡ  -ның   -ла инверсиялар һаны аша ла билдәләнергә мөмкин:

 .

Ҡабатланыусы алмаштырма үҙгәртергә

Төрлө   типтағы   элементты ҡарайыҡ, шуның менән бергә һәр типта бөтә элементтар бер төрлө. Ул саҡта бөтә был элементтарҙан алмаштырмалар бер типтағы элементтарҙың урынлашыу тәртибенә тиклем аныҡлыҡ менән ҡабатланыусы алмаштырма тип аталалар. Әгәр   —  -сы типтағы элементтар һаны булһа, ул саҡта   һәм бөтә мөмкин булған ҡабатланыусы алмаштырмалар һаны   мультиномиаль коэффициентҡа тигеҙ.

Ҡабатланыусы алмаштырманы шулай уҡ ҡеүәте   булған   мультикүмәклек алмаштырмаһы итеп ҡарарға мөмкин.

Осраҡлы алмаштырма үҙгәртергә

Осраҡлы алмаштырма тип   осраҡлы векторы атала, уны бөтә элементтары 1-ҙән алып  -ға тиклемге натураль ҡиммәттәр ҡабул итәләр һәм шуның менән бергә теләһә ниндәй ике элементтың тап килеү ихтималлығы 0-гә тигеҙ.

Бәйһеҙ осраҡлы алмаштырма тип шундай   осраҡлы алмаштырма атала, уның өсөн:

 

ҡайһы бер шундай   өсөн:

 
 

Шуның менән бергә әгәр    -гә бәйле булмаһа,   алмаштырмаһын бер төрлө төркөмләнгән тип атайҙар. Әгәр  -ҡа бәйлелек булмаһа, йәғни   ул саҡта   алмаштырмаһын бер төрлө тип атайҙар.

Шулай уҡ ҡарағыҙ үҙгәртергә

Иҫкәрмәләр үҙгәртергә

  1. Евгений Вечтомов, Дмитрий Широков. Математика: логика, множества, комбинаторика. Учебное пособие для академического бакалавриата. — 2-е изд.. — Litres, 2018-03-02. — С. 145—146. — 244 с. Архивная копия от 7 апрель 2022 на Wayback Machine
  2. Учебник по математике для СПО / Башмаков М. И., 10-11 класс. — С. 67
  3. Теория вероятностей и элементы математической статистики 2022 йыл 1 февраль архивланған.
  4. Виленкин Н.Я. Глава III. Комбинаторика кортежей и множеств. Размещения с повторениями // Популярная комбинаторика. — М.: Наука, 1975. — С. 80. — 208 с.
  5. Теория конфигураций и теория перечислений. Дата обращения: 30 декабрь 2009. Архивировано 23 ғинуар 2010 года.
  6. Глава 3. Элементы комбинаторики 2010 йыл 4 ғинуар архивланған.. // Лекции по теории вероятностей.
  7. Дональд Э. Кнут — Искусство программирования. Том 1. Основные алгоритмы. 1.2.5. Перестановки и факториалы

Әҙәбиәт үҙгәртергә

Һылтанмалар үҙгәртергә