parking function의 정의1
parking function의 정의2
구글링을 해도
두 가지 정의가 동등하다는 것만나오고
동등성에 대한 증명은 안나와서
직접 해보려했거든.
정의1 => 정의2 는 귀류법써서 쉽게 증명되는데
정의2 => 정의1이 아무리해도 증명이안됨..
정의2 => 정의1을 증명하기위해서
보조정리로
정의1 parking function의 임의의 재배열수열도
정의1 parking function이다
를 증명하면 정의2를 가정하면 정의1임이 바로 보여지는데
보조정리 증명이 아무리 해도 안되더라고..
보조정리의 증명자체가 정의2=>정의1을 가정해야 증명이
되는거같기도해서..
보조정리를 증명해서 정의2=>정의1을 증명한다는 거 자체가
순환논법인가 싶기도해.
정의2=>정의1을 어떻게증명해야할까?
보조정리의 증명을통해 증명할수있을까?
그게 아니면 완전히 새로운 방법으로해야할까?
도움좀..
- dc official App
보조정리에서 임의의 재배열을 임의의 인접한 두 차량의 순서를 바꾼 것으로 내리고 바꾸기 전후의 parking ft 여부가 같음을 확인하면 가능할거임
임의의 인접 두 수 순서 바꾸는걸 유한번반복하면 임의재배열이가능하게되나?? - dc App
당연히될거같긴한데그건어떻게증명하지 - dc App
아 생각해보니 버블정렬이랑 똑같은거니까 원하는 재배열 수열에 1,2,..,번호 마킹해서 오름차순정렬됏다생각하면 버블정렬알고리즘이라 되는수나 - dc App
rearrangement 는 그냥 주차 순서만 정렬한 거라 동일함 b_1, b_2, ... 순서대로 1, 2, ... 에 하나씩 주차시켜보면 b_i<=i 가 해당 조건이니 동치임