[일반] 조합론에서 이 식 성립하는 원리가 그건가?

[시트르산(energy040227)]

n개의 원소 중 짝수개를 뽑는 경우의 수인데

n개 중 원소 a를 하나 잡아서

a를 제외한 나머지 원소들은 뽑는 경우, 안 뽑는 경우 두개 중 하나를 고르는게 n-1 번이고, 뽑은 결과가 홀수개일 경우 a를 포함시키고 짝수개일 경우 a를 포함시키지 않는다

해서 2^(n-1) ?

[wlltmprdclvr4(wlltmprdclvr4)]

잘은 모르겠고 그냥 이항계수로도 되지않나

[익명(39.7)]

nCa=nC(n-a) - dc App

[시트르산(energy040227)]

아 그거 하나면 간단히 되네

[ㅅㄲㅁㅇ(as1392)]

이거론 n이 짝수일때 곤란함

[익명(39.7)]

홀수 짝수 경우나눠서 따지면 될걸? - dc App

[익명(58.140)]

그냥 (1+x)^n 이항계수 x=1, -1넣고 더하면 됨

[ㅅㄲㅁㅇ(as1392)]

nC0 으디갔어 요놈아

[익명(49.143)]

nC0도 저 덧셈에 포함시켜야 할것이고.. 그냥 {1,2,..,n}의 임의의 부분집합 A에 대해서, A가 1을 포함하면 f(A)=A-{1}, 1을 포함하지 않으면 f(A)=A∪{1}이라는 함수 f : P({1,2,..,n}) -> P({1,2,..,n})을 생각해보면, f^2가 identity니까 이 함수는 bijection이고 f({홀수 크기의 집합})={짝수 크기의 집합}이니 결국 짝수 크기의 집합의 개수와 홀수 크기의 집합의 개수가 같다는 결론을 얻을수 있지.

[웨리(49.143)]

퍄퍄 - dc App

[웨리(49.143)]

와 진짜 머임ㅋㅋㅋㅋㅋㅋㅋㅋ - dc App

[ㅅㄲㅁㅇ(as1392)]

combinatorial proof 개꿀잼

[웨리(49.143)]

idempotent를 저렇게 쓰는거구나 ㄹㅇ ㅆㅅㅌㅊ - dc App

[익명(49.143)]

idempotent는 보통 T^2=T꼴인 operator T를 의미하고, T^2=id인 operator를 involution이라고 하는데 이러한 involution을 이용해서 어떤 항등식을 증명하는건 조합론에서 굉장히 일반적인 도구야.

[Rafle(probaroque)]

내가 involution이라고 댓글 달려고 했는데 빠르넹..

[웨리(49.143)]

않되

[익명(49.143)]

얼마전에 올라온 질문
https://gall.dcinside.com/mgallery/board/view/?id=math&no=4156
에도 마찬가지로 involution을 이용해서 답변을 달았었는데, 구체적으로 A_n을 연속된 두 수가 출현하지 않는 n자리 홀수의 모임, B_n을 연속한 두 수가 출현하지 않는 n자리 짝수의 모임이라 할때, A_n-{1010...10}과 B_n-{1010...01}의 크기가 같다는걸 증명하기 위해서 A_n∪B_n - {1010...10, 1010...01} 안에서의 involution을 만들었어.

[웨리(49.143)]

어우야 길다 언제 한 번 읽어볼게 고마워

[익명(49.143)]

그리고 다른 예는 Zagier의 페르마의 두 제곱수 정리에 대한 몇줄짜리 아름다운 증명이 있음.
https://en.wikipedia.org/wiki/Proofs_of_Fermat%27s_theorem_on_sums_of_two_squares#Zagier's_%22one-sentence_proof%22

[익명(39.7)]

솔직히 두 제곱수 정리보면 발기되는거 인정해야함 - dc App

[coco(175.196)]

원글의 풀이도 더할 나위 없이 좋은데.