Částečná permutace - Partial permutation

v kombinatorická matematika, a částečná permutacenebo sekvence bez opakování, na konečná množina Sje bijekce mezi dvěma zadanými podmnožiny z S. To znamená, že je definován dvěma podmnožinami U a PROTI stejné velikosti a one-to-one mapování z U na PROTI. Ekvivalentně je to částečná funkce na S které lze rozšířit na a permutace.^[1]^[2]

Zastoupení

Je běžné vzít v úvahu případ, kdy soubor S je jednoduše množina {1, 2, ..., n} první n celá čísla. V tomto případě může být částečná permutace reprezentována a tětiva z n symboly, z nichž některá jsou odlišná čísla v rozsahu od 1 do ${ displaystyle n}$ a zbývající jsou speciální symbol „díry“ ◊. V této formulaci je doména U částečné permutace se skládá z pozic v řetězci, které neobsahují díru, a každá taková pozice je mapována na číslo v této pozici. Například řetězec „1 ◊ 2“ by představoval částečnou permutaci, která mapuje 1 k sobě a mapuje 3 k 2.^[3]Sedm částečných permutací na dvou položkách je

◊◊, ◊1, ◊2, 1◊, 2◊, 12, 21.

Kombinatorický výčet

Počet částečných permutací na n položky, pro n = 0, 1, 2, ..., je dáno celočíselná sekvence

1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, ... (sekvence A002720 v OEIS )

Kde nta položka v pořadí je dána součtovým vzorcem

{ displaystyle sum _ {i = 0} ^ {n} i! { binom {n} {i}} ^ {2}}

ve kterém itento termín počítá počet částečných permutací s podporou velikosti i, tj. počet částečných permutací s i položky bez děr. Alternativně jej lze vypočítat pomocí a relace opakování

{ displaystyle P (n) = 2nP (n-1) - (n-1) ^ {2} P (n-2).}

To se určuje následovně:

${ displaystyle P (n-1)}$ částečné permutace, kde jsou vynechány konečné prvky každé sady:
${ displaystyle P (n-1)}$ částečné permutace, kde se konečné prvky každé sady vzájemně mapují.
${ displaystyle (n-1) P (n-1)}$ částečné permutace, kde je zahrnut poslední prvek první sady, ale nemapuje se na poslední prvek druhé sady
${ displaystyle (n-1) P (n-1)}$ částečné permutace, kde je zahrnut poslední prvek druhé sady, ale nemapuje se na poslední prvek první sady
${ displaystyle - (n-1) ^ {2} P (n-2)}$ , částečné permutace zahrnuté v obou počtech 3 a 4, ty permutace, kde jsou zahrnuty konečné prvky obou sad, ale navzájem se nemapují.

Omezené částečné permutace

Někteří autoři omezují částečné obměny na doménu^[4] nebo rozsah^[3] z bijekce je nucen sestávat z první k položky v sadě n pro některé položky jsou permutovány k. V prvním případě částečná permutace délky k z n-set je jen sekvence k podmínky z n- sada bez opakování. (V elementární kombinatorice se tyto objekty někdy matoucí nazývají „k-permutace "z n-soubor.)

Reference

^ Straubing, Howard (1983), „Kombinatorický důkaz Cayley-Hamiltonovy věty“, Diskrétní matematika, 43 (2–3): 273–279, doi:10.1016 / 0012-365X (83) 90164-4, PAN 0685635.
^ Ku, C. Y .; Leader, I. (2006), „An Erdős-Ko-Radova věta pro částečné permutace“, Diskrétní matematika, 306 (1): 74–86, doi:10.1016 / j.disc.2005.11.007, PAN 2202076.
^ ^A ^b Claesson, Anders; Jelínek, Vít; Jelínková, Eva; Kitaev, Sergey (2011), „Vyhýbání se vzorům v částečných permutacích“, Electronic Journal of Combinatorics, 18 (1): Papír 25, 41, PAN 2770130.
^ Burstein, Alexander; Lankham, Isaiah (2010), „Omezené třídění trpělivosti a vyhýbání se promlčeným vzorům“, Permutační vzorce, London Math. Soc. Přednáška Ser., 376, Cambridge: Cambridge Univ. Press, str. 233–257, arXiv:matematika / 0512122, doi:10.1017 / CBO9780511902499.013, PAN 2732833.

[1] Straubing, Howard (1983), „Kombinatorický důkaz Cayley-Hamiltonovy věty“, Diskrétní matematika, 43 (2–3): 273–279, doi:10.1016 / 0012-365X (83) 90164-4, PAN 0685635.

[2] Ku, C. Y .; Leader, I. (2006), „An Erdős-Ko-Radova věta pro částečné permutace“, Diskrétní matematika, 306 (1): 74–86, doi:10.1016 / j.disc.2005.11.007, PAN 2202076.

[cjjk-3] A ^b Claesson, Anders; Jelínek, Vít; Jelínková, Eva; Kitaev, Sergey (2011), „Vyhýbání se vzorům v částečných permutacích“, Electronic Journal of Combinatorics, 18 (1): Papír 25, 41, PAN 2770130.

[4] Burstein, Alexander; Lankham, Isaiah (2010), „Omezené třídění trpělivosti a vyhýbání se promlčeným vzorům“, Permutační vzorce, London Math. Soc. Přednáška Ser., 376, Cambridge: Cambridge Univ. Press, str. 233–257, arXiv:matematika / 0512122, doi:10.1017 / CBO9780511902499.013, PAN 2732833.

[1]

[2]

[3]

[4]