Šikmá sloučená permutace - Skew-merged permutation - Wikipedia

V teorii permutační vzory, a šikmá sloučená permutace je permutace které lze rozdělit na rostoucí sekvenci a klesající sekvenci. Nejprve je studoval Stanková (1994) a pojmenovali podle Atkinson (1998).

Charakterizace

Dvě nejmenší permutace, které nelze rozdělit na rostoucí a klesající sekvenci, jsou 3412 a 2143. Stanková (1994) byl první, kdo prokázal, že permutaci sloučenou se zkosením lze také ekvivalentně definovat jako permutaci, která se vyhýbá dvěma vzorům 3412 a 2143.

Permutace je zkosená sloučena tehdy a jen tehdy, je-li přidružena permutační graf je dělený graf, graf, který lze rozdělit na a klika (odpovídá sestupné subsekvenci) a an nezávislá sada (odpovídá vzestupné subsekvenci). Dva zakázané vzory pro permutace sloučené se zkosením, 3412 a 2143, odpovídají dvěma ze tří zakázaných indukované podgrafy pro dělené grafy cyklus čtyř vrcholů a graf se dvěma disjunktními hranami. Třetí zakázaný indukovaný podgraf, cyklus pěti vrcholů, nemůže existovat v permutačním grafu (viz Kézdy, Snevily & Wang (1996) ).

Výčet

Pro ${ displaystyle n = 1,2,3, tečky}$ počet zúžených permutací délky ${ displaystyle n}$ je

1, 2, 6, 22, 86, 340, 1340, 5254, 20518, 79932, 311028, 1209916, 4707964, 18330728, ... (sekvence A029759 v OEIS ).

Atkinson (1998) byl první, kdo ukázal, že generující funkce z těchto čísel je

${ displaystyle { frac {1-3x} {(1-2x) { sqrt {1-4x}}}},}$

z čehož vyplývá, že počet zkosení sloučených permutací délky ${ displaystyle n}$ je dáno vzorcem

${ displaystyle { binom {2n} {n}} součet _ {m = 0} ^ {n-1} 2 ^ {n-m-1} { binom {2m} {m}}}$

a že tato čísla poslouchají relace opakování

${ displaystyle P_ {n} = { frac {(9n-8) P_ {n-1} - (26n-46) P_ {n-2} + (24n-60) P_ {n-3}} {n }}.}$

Další derivaci generující funkce pro šikmé sloučené permutace dal Albert & Vatter (2013).

Výpočetní složitost

Testování, zda je jedna permutace vzorem v jiné, lze efektivně vyřešit, když je větší ze dvou permutací zešikmena, jak ukazuje Albert a kol. (2016).

Reference

• Albert, Michael; Vatter, Vincent (2013), "Generování a výčet 321 - vyhýbání se a zkosení sloučených jednoduchých permutací", Electronic Journal of Combinatorics, 20 (2): Paper 44, 11 pp., PAN  3084586.

• Albert, Michael; Lackner, Marie-Louise; Lackner, Martin; Vatter, Vincent (2016), "Složitost shody vzorů pro 321 vyhýbání se a zkosení sloučených permutací", Permutační vzory 2015, Diskrétní matematika a teoretická informatika, 18 (2): P11: 1–17, arXiv:1510.06051, Bibcode:2015arXiv151006051A, PAN  3597961.

• Atkinson, M. D. (1998), "Permutace, které jsou spojením rostoucí a klesající posloupnosti", Electronic Journal of Combinatorics, 5: RP6: 1–13, PAN  1490467. Viz také přiložený komentář Volkera Strehla.

• Kézdy, André E .; Snevily, Hunter S .; Wang, Chi (1996), „Rozdělení permutací na zvyšování a snižování subsekcí“, Journal of Combinatorial Theory, Series A, 73 (2): 353–359, doi:10.1016 / S0097-3165 (96) 80012-4, PAN  1370138

• Sloane, N. J. A. (vyd.). „Sequence A029759“. The On-line encyklopedie celočíselných sekvencí. Nadace OEIS.

• Stanková, Zvezdelina E. (1994), „Zakázané subsekvence“, Diskrétní matematika, 132 (1–3): 291–316, doi:10.1016 / 0012-365X (94) 90242-9, PAN  1297387. Viz zejména Věta 2.9, s. 303–304.