[대학교이상] 이거 이산수학 과젠데 어디부터 건들여야함?

[샤온(bsjme122107257257)]

시작을 못 하겠음... 둘이 같은 걸 증명하라는데 꽤 고민해본 것 같은데도 어디서부터 시작해야하는지 감이 안 잡힘.

[익명(59.11)]

r에 대해 induction hypothesis를 잡고 x에 대해 미분하면 될거같은데

[샤온(bsjme122107257257)]

지금 induction 잡을 수 있는 게 n이랑 r 두 개 같은데 이럴 땐 그냥 하나에만 적용하면 되는 건가? 아직 2학년이라 induction 변수 2개일 때는 적용을 안 해봤어

[샤온(bsjme122107257257)]

ㅈㅁ 검색하고 다시 댓글달게

[샤온(bsjme122107257257)]

웅 찾아봤는데 n이랑 r둘 다에 대해서 induction 써볼게

[익명(59.11)]

풀었는지 모르겠는데 (1+x)^n = sum C(n,k)x^k 의 binomial expansion 을 1, 2, ... , r번 미분후 양변에 x^1, x^2, ..., x^r을 곱한 n(1+x)^(n-1)(x^1) = sum{k=0 to n} C(n,k)kx^k n(n-1)(1+x)^(n-2)(x^2) = sum{k=0 to n} C(n,k)k(k-1)x^k n(n-1)..(n-r)(1+x)^(n-r)(x^r) = sum{k=0 to n} C(n,k)k(k-1)(k-2)..(k-r+1)x^k 에서 우변 1, k, k(k-1), k(k-1)...(k-r+1)을 스털링 수를 이용해 k^r로 만들어 나온 게 저 식임

[익명(59.11)]

그냥 쓰면 복잡할 거 같아서 귀납법 쓰라고 한 거였는데 잘 안 풀리면 이대로 쓰셈

[샤온(bsjme122107257257)]

지금 도합 3시간 고민했는데 안 풀렸었음... ㄱㅅ...

[샤온(bsjme122107257257)]

형 혹시 나 귀납법 쓰던 거 올리면 봐줄 수 있어?

[익명(59.11)]

ㅇㅇ

[샤온(bsjme122107257257)]

근데 마지막 부분에서 "1 k k(k-1) k(k-1)....(k-r+1)을 스털링 수를 이용해 k^r로 만들어"부분이 이해가 안 가ㅠㅠ

[익명(59.11)]

m!C(k,m) = k(k-1)...(k-m-1) 을 편의상 k_m으로 표기함 각각 양변에 S(r,0), S(r,1), ... S(r,r) 을 곱하면 S(r,0)n_0(1+x)^n = sum{k=0 to n} C(n,k)S(r,0)k_0x^k S(r,1)n_1(1+x)^(n-1)x = sum{k=0 to n} C(n,k)S(r,1)k_1x^k S(r,2)n_2(1+x)^(n-2)x^2 = sum{k=0 to n} C(n,k)S(r,2)k_2x^k ... S(r,r)n_r(1+x)^(n-r)x^r = sum{k=0 to n} C(n,k)S(r,r)k_rx^k 세로로 쭉 더하면 좌변은 증명하려는 식의 우변이고, sum {j=0 to r} S(r,j)k_j = k^r 이니 우변은 증명하려는 식의 좌변이 됨

[익명(59.11)]

여기서 sum {j=0 to r} S(r,j)k_j = k^r 는 스털링 수의 성질이니 증명할 필요는 없을 듯 그리고 귀납법 써서 증명하는 것도 식 전개는 좀 까다로운데 S(r+1, j) = jS(r, j) + S(r, j-1) 이용하면 풀리더라

[샤온(bsjme122107257257)]

일단 올렸옹

[익명(119.67)]

좀 더 combinatorical하게 생각해보면,

[익명(119.67)]

좌변은 n개 중 k개를 뽑아서 각각에 x를 곱하고, {1,...,r}에서 이 k개로 가는 함수를 하나 고르는 거

[익명(119.67)]

우변은 이 함수의 치역이 되는 j개를 먼저 뽑아서 {1,...,r}에서 치역으로 가는 함수를 스털링수로 골라주고 k개 중 치역이 되지 못한 나머지와 치역 j개에 각각 x를 곱해주는 거

[익명(119.67)]

이렇게 생각하면 일대일대응이 잡힌다는 걸 생각해볼 수 있음

[익명(119.67)]

x가 미지수여서 경우의 수로 생각하기가 조금 미묘하기는 한데, 약간 technical하게 이 부분을 해결해보자면 양변이 n차 다항식이니까, 공통근을 n+1개 이상 가지면 양변이 서로 같다는 점에서 착안해서 임의의 자연수 x에 대해 양변이 같음을 보이면 양변이 다항식으로서 같다는 걸 보일 수 있음

[샤온(bsjme122107257257)]

오 이거도 해볼게. 일단 좀 쉬어야겠다 이 문제 붙잡고 4시간 지났네ㅋㅋㅋ

[익명(119.67)]

좀 더 formal하게 적자면, 양변이 number of tuples (S, f, g) where S \subset {1,...,n}, f:{1,...,k}->S, g:S->{1,...,x}와 같음을 설명하면 됨

[샤온(bsjme122107257257)]

음 근데 우변에서 (1+x)^{n-j}는 어떻게 생각해야 돼?

[익명(119.67)]

S의 원소 중에서 image of f에 안 들어가는 녀석을 골라주는 과정이라고 생각하면 됨 {1,...,n} - im(f)의 원소 n-j개 중 S에 들어가는 쪽이 x, 안 들어가는 쪽이 1에 해당됨

[샤온(bsjme122107257257)]

아 대강은 이해한듯. S가 r개의 원소를 갖고 있는 친구고 g는 bijection이 되는 거 맞나?

[익명(119.67)]

아 잘못 적었다 f:{1,...,k}->S가 아니라 f:{1,...,r}->S임 S의 원소가 k개가 될 거고, im(f)의 원소가 j개가 될 거임 g는 bijection일 필요는 없음

[샤온(bsjme122107257257)]

아 그렇구나. 다시 생각해볼게 고마워