주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[대한수학회] 대13. 그래프의 a-넘버②

2017.12.29

같이 풀어볼까?

네이버밴드 구글플러스

지난 달에는 그래프 \large G에 정의된 그래프 불변값 \large a(G)에 대해서 알아봤다. 단순그래프 \large G에 대해 \large a(G)는 다음과 같이 정의된다.

(1) \large a(\o )=1  (\large V가 공집합인 경우는 \large G=\o으로 표현한다)

(2) \large G가 홀수 개수의 점을 가지는 연결 성분을 가진다면 \large a(G)=0

(3)

이제 \large a(G)에 대해 어느 정도 이해했으면 조금 더 어려운 문제를 풀어보도록 하자.

음이 아닌 정수 \large i에 대해 \large a_i(G)\large G의 부분유도그래프 중에서 점의 개수가 \large 2i인 것의 \large a값을 모두 다 더한 것의 절댓값이다. 이때 지난 달 4번 문항의 결과를 이용하면 점의 개수가 \large 2i인 것의 \large a값의 부호는 \large (-1)^i와 같으므로, 다음이 성립함을 알 수 있다.

한편, \large a(G)\large G의 점의 개수가 짝수일 때만 유의미한 값을 가지지만, \large a_i(G)\large G의 점의 개수가 홀수인 경우에도 0이 아닌 값을 가질 수 있다.

 

문제5. 완전그래프란 모든 점의 쌍이 서로 연결돼 있는 그래프를 의미한다. 점의 개수가 \large n개인 완전그래프 \large K_n에 대해 \large a_0(K_n), \, a_1(K_n), \, a_2(K_n) 을 계산하여라.

 

 

문제6. 점의 개수가 \large n개인 경로그래프 \large P_n에 대해 \large a_i(P_n)\large n\large i에 대한 이중수열로 나타내고, 이 수열이 가진 성질에 대하여 조사해 보아라.

 

 

문제7. 점의 개수가 \large 2m-1개 혹은 \large 2m인 임의의 단순그래프 \large G에 대해 \large a_i(G)가 다음 성질을 가지고 있음을 증명 혹은 반증하여라.

\large a_0(G)\leq a_1(G)\leq a_2(G) \leq \cdots \leq a_m_-_1(G)

 

 

※알립니다.

문제 5번은 수학장님이 해결했습니다. 간단한 문제라 부분해결 딱지는 다른 문제를 풀리면 달도록 하겠습니다. 

주정훈 멘토에 따르면, 현재 5번을 제외한 나머지 문제는 미해결이라고 합니다!!

댓글 109

  • 구머 2017.12.29 15:42:18

    6번에 경로그래프의 정의가 뭔지 알수 있을까요? 

    좋아요0 댓글수5
    • 구머 2017.12.29 16:26:45

      아 지난달 문제에 정의되어있네요 죄송합니다.

      좋아요0
    • 여백 패르마 2017.12.31 11:59:08

      제 눈이 이상한가...않보이네요..

      좋아요0
    • 구머 2017.12.31 13:02:28

      3번에 있어요

      좋아요0
    • 여백 패르마 2017.12.31 14:20:40

      이앵???부분유도그래프에 관한것 밖에 없는데요??

      좋아요0
    • 여백 패르마 2017.12.31 14:22:51

      아아아 푸는 문제 3번에 있었군요...

      좋아요0
  • 수학장 2017.12.29 18:29:53

    완전그래프는 모든 점의 쌍이 서로 연결되 있는 그래프이므로 완전그래프의 부분유도그래프도 완전그래프입니다.

    a_{0}(K_{n})=1임은 자명하고, a_{1}(K_{n})은 (n개의 점 중 점 2개를 뽑는 경우의 수)x(점의 개수가 2인 완전그래프의 a값)이므로\left | \binom{n}{2}\times (-1)\right |=\binom{n}{2}\times 1이고, a_{2}(K_{n})=\binom{n}{4}\times 5입니다. 5번 해결 완료! 5번은 쉽군요

    좋아요0 댓글수1
    • 수학장 2017.12.29 18:34:54

      완전그래프의 예입니다. 완전그래프가 이해 안 되시는 분은 참고하세요.

      좋아요0
  • 구머 2017.12.30 00:21:14

    으아 6번 생성함수로 구하려고 하는데 끔찍한 계산...

    좋아요0 댓글수3
    • 수학장 2017.12.30 12:59:38

      a_{1}(P_{n})=n-1, a_{2}(P_{n})=\frac{n^{2}-5n+8}{2} , a_{3}(P_{n})=2n^{2}-21n+59가 나오더군요(단, n>=7) 결론 : 도움이 전혀 안 됨

      여러 가지 방법으로 풀어보고 있는데 잘 안 되네요

      좋아요0
    • 수학장 2017.12.30 13:25:47

      ㅋㅋ이렇게 유도했는데 너무 복잡해서 일반항 유도는 못하겠네요

      a_{i}(P_{n})=\sum_{\alpha +\beta +..=2i, \alpha +1+\beta +1+...=n+1} (\frac{1}{(n+1)}\binom{2\alpha }{\alpha }\binom{2\beta }\beta....)좀 간단하게 해봤는데 여전히 복잡함.... 이때 알파, 베타 등은 0보다 크거나 같은 짝수입니다.

      좋아요0
    • 여백 패르마 2017.12.30 22:17:10

      ㄷ ㄷ 엄청 복잡하네요..

      좋아요0
  • 여백 패르마 2017.12.30 14:53:59

    7번 풀이입니다 저번처럼 너무 일찍이여서 오류가 있을 것이고 전체를 읽으시기 바랍니다.(저번같이 속은 느낌들기 싫어서요...ㅋㅋ)

    좋아요0 댓글수4
    • 수학장 2017.12.30 16:18:49

      검증하기 귀찮음... 무슨 말인지도 이해가 안 되요. 국가수리과학연구소 문제 언제 나오지

      좋아요0
    • 구머 2017.12.30 16:19:47

      아.. 저번에 속은 느낌을 받으셨군요 죄송합니다 ㅜㅜ

      좋아요0
    • 여백 패르마 2017.12.30 16:39:07

      괜찮습니다. 속은 느낌은 일시적이였어요!!^^

      또,2번은 수학적 귀납법을 이용해서 나오는 것인데요..

      좋아요0
    • 여백 패르마 2017.12.30 22:00:33

      그리고 참고로 아래에 적혀있는 더 간단히 말하는 것을 참고하시면 됩니다.

      좋아요0
  • 여백 패르마 2017.12.31 15:36:51

    제 풀이를 조금 바꿀께요.

    다 읽고 싶지 않은 사람 용:  a0(G)<a1(G)는 자명하다. 또, 임의의 수 n이 있을 때 an(G)(1)<=an+1(G)(2) 이 성립하는 이유는 (1)의 부분유도그래프의 개수가 (2)의 부분유도그래프의 개수보다 더 적고, (1)의 부분유도그래프의 a값의 절대값이 (2)의 부분유도그래프의  a값의 절대값보다 더 적기 때문이다. 수학적 귀납법으로 7번은 성립한다.

    다 읽어도 되는 사람들용: a값들의 합이 (1)과 (2)모두 y라고 가정하자. 또,2m-1C2n-2=x이라고 하자.(사실 2m-1이 아니라 2m이여도 괜찮다.) (1)번의 부분유도그래프의 개수의 평균은 가장 심각한 상황에서는 x/2+1/2이다. 또, (2)번에서의 부분유도그래프의 개수의 평균은 가장 심각한 때는{( 2m-1-2n)^2/(2n+1)^2}x+1/2이다. 즉, {x/2+1/2}y<=[{(2m-2n-1)^2/(2n+1)^2}x+1/2}y이라는 것을 증명해야 하고, 즉 간단화시키면 1/2<=(2m-2n-1)^2/(2n+1)^2(3) 이라는 것을 증명해야 한다. 또, n=최대 m이기 때문에 1/루트2 <= 1-2/m이라는 것을 증명해야 하고 이 것은 m이 2이하일때만 성립하는데, 직접 해보면 m이 2이하일때는 맞다는 것을 알 수 있다. 즉, (3)은 참이다. 즉, 수학적 귀납법으로 7번 증명!!!    

     

    좋아요0 댓글수3
    • 여백 패르마 2017.12.31 15:39:43

      제 컴퓨터가 수식 편집가 안돼서 그런거라서 좀 중간에 끊어져도 양해 부탁드립니다.

      좋아요0
    • 수학장 2017.12.31 20:28:07

      "(1)의 부분유도그래프의 a값의 절댓값이 (2)의 부분유도그래프의 a값의 절댓값보다 적기 때문이다"부분이 잘못된 것 같은데요. 그리고 '가장 심각한 상황'이 아니라 모든 경우를 증명해야 합니다. 7번이 가장 어려운 문제예요. 일단 6번부터 같이 해결해봐요.

      좋아요0
    • 여백 패르마 2018.01.01 19:52:30

      기징 어렵다고 처음 문제들 먼저 해야하진 않지요.(그렇다고 풀 자신 있는거 아니예요...)

      좋아요0
  • 여백 패르마 2018.01.01 19:55:34

    좋아요0 댓글수7
    • 수학장 2018.01.01 21:06:31

      a_{n-1}(G)-a_{n}(G)=(\sqrt{a_{n-1}(G)}+\sqrt{a_{n}(G)})(\sqrt{a_{n-1}(G)}-\sqrt{a_{n}(G)}) 이걸 계속하면 \lim_{t\rightarrow \infty }(\sqrt[k]{a_{n-1}(G)}-\sqrt[k]{a_{n}(G)})를 생각해야 하죠 그러면 0이고, 그러므로

      \sqrt{a_{n-1}(G)}-\sqrt{a_{n}}\geq 0 \\\ \therefore a_{n-1}(G)\geq a_{n}(G)

      가 되요. 이 부분 설명해주실 수 있나요?

      좋아요0
    • 여백 패르마 2018.01.02 13:30:14

      당연 한것 아닌가요??참고로 부등호 방향 바꿔야 합니다.

      좋아요0
    • 구머 2018.01.02 15:33:35

      증명이 되게 신기하네요. 'n'과 'n-1'의 위치를 전부 바꿔도 성립합니다. (즉, an-1(G)>an(G)라는 결론이 나옵니다.)

      좋아요0
    • 여백 패르마 2018.01.02 16:39:56

      ?!!!

      좋아요0
    • 여백 패르마 2018.01.02 16:59:17

      그리고 모든 자연수에 대해 a>b가 언제나 성립한다고 나와요...

      좋아요0
    • 수학장 2018.01.02 17:38:15

      부등호 방향 틀린 거 아니예요 구머님이 말씀해주셨지만 n과 n-1이 바뀌어도 성립하므로, 뭔가 문제가 있다는 뜻이죠

      좋아요0
    • 여백 패르마 2018.01.02 18:29:09

      그런거 같네요..

      좋아요0
  • 여백 패르마 2018.01.02 08:55:18

    좋아요0 댓글수3
    • 수학장 2018.01.02 11:16:37

      죄송한데 잘 안 보임

      좋아요0
    • 여백 패르마 2018.01.02 12:18:01

      좋아요0
    • 여백 패르마 2018.01.02 16:44:12

      빼먹은 거에요..

      좋아요0
  • 여백 패르마 2018.01.02 16:53:10

    좋아요0 댓글수10
    • 여백 패르마 2018.01.02 16:54:41

      구머님 말처럼  전 풀이는 진짜 이상하고 수학장님 말처럼 잘 않보여서 잘 보이도록 진짜 열심히 했습니다.

      좋아요0
    • 여백 패르마 2018.01.02 17:03:59

      자고로 순서 바꿨습니다.

      좋아요0
    • 수학장 2018.01.02 23:08:23

      a_{n-1}=\sum ^{k}_{i=1}a_{i}x_{i}인거죠? 그 윗부분까진 이해가 되는데 이 부분부터 이해가 안되네요.

      좋아요0
    • 구머 2018.01.03 01:58:56

      맨 마지막에 ya/k<=2ya를 보여야 한다고 하셨는데,2ya가 아니라 2za가 되어야 합니다.(z=y1+y2+...+yk)

      그리고 풀이를 작성하실때 계산값들을 '근사'하셔서 푸셨는데, 이 경우 비교적 극단적인 사례가 발생할경우 예외가 발생할 수도 있어서, 별로 추천드리진 않습니다.

      좋아요0
    • 여백 패르마 2018.01.03 13:39:45

      네 제트가 들어가는 식이 맞지만 제트가 와이보다 더 크기 때문에 와이로 넣어 해도 성립하면 제트도 성립합니다.

      좋아요0
    • 수학장 2018.01.03 13:48:05

      여잭페르마님 y가 성립하면 z도 성립하는 게 아니라 z가 성립하면 y가 성립하는 거예요

      좋아요0
    • 여백 패르마 2018.01.03 14:25:49

      또, 가장 극단적인 때에는 제가 증명을 했습니다.12.31에 쓴 댓글에 말이에요.또,덜극단적일 수록 제 풀이가 더 맞게 됩니다.

      좋아요0
    • 여백 패르마 2018.01.03 14:27:14

      아뇨 제트가 더 크기 때문에 맞는데요...

      좋아요1
    • 수학장 2018.01.03 17:57:06

      아 그러네요(헷갈림) 국가수리과학연구소 문제도 관심 좀 가져줘요

      좋아요0
    • 구머 2018.01.04 00:34:24

      그러면 이 증명과 위쪽 극단적인 부분 한의 증명에 있는 그래프들이 모든 그래프 G를 이룸을 증명해야합니다.

      좋아요0
  • 여백 패르마 2018.01.06 12:18:15

    마지막(?) 수정 풀이이고 대댓글에  빠트렸던 풀이 있습니다.

    좋아요0 댓글수2
    • 여백 패르마 2018.01.06 12:20:45

      빠트렸던 풀이 입니다..

      좋아요0
    • 여백 패르마 2018.01.07 20:50:06

      이런...오류가 있군요.. 그리고 고쳐봤어요.

      좋아요0
  • 여백 패르마 2018.01.07 20:55:33

    좋아요0 댓글수4
    • 여백 패르마 2018.01.07 20:56:32

      이미 아시다시피 순서는 뒤바뀌었습니다.

      좋아요0
    • 여백 패르마 2018.01.08 15:57:11

      아놔. 또 오류

      좋아요0
    • 수학장 2018.01.08 19:30:20

      오류 발견하고 수정하면 그냥 댓글 수정하면 안되나요...? 새 댓글 달지 마시고....

      좋아요0
    • 여백 패르마 2018.01.09 09:08:26

      사진이여서 수정이 힘들어요.

      좋아요0
  • 여백 패르마 2018.01.09 09:16:40

    좋아요0 댓글수18
    • 여백 패르마 2018.01.09 09:19:31

      이제 제 눈에 오류가 안보이네요. 그런데 오류가 있을 지도 모르니 찾으신 분은 대댓글로 올려주시길 바랍니다.

      좋아요1
    • 구머 2018.01.12 22:13:36

      2번째 페이지 마지막줄, 세번째 페이지 첫번째 줄의 전개가 잘못된것 같습니다. 그나저나 꽤 오랜만에 들어왔는데, 아무도 댓글을 안달았네요ㅜ

      좋아요0
    • 여백 패르마 2018.01.13 07:18:46

      그러면 뭐가 맞게 한것인가요??

      좋아요0
    • 여백 패르마 2018.01.13 07:26:14

      네 그리고 아무도 댓글을 않달아서 ㅠㅠ 했었어요.

      좋아요0
    • 구머 2018.01.13 12:50:02

      으악 잘못봤네요 세번째 페이지 둘째줄이 왜 자명한지 설명 부탁드립니다 

      좋아요0
    • 여백 패르마 2018.01.14 17:49:49

      당연하지 않나요??(귀찮다..)

      좋아요0
    • 여백 패르마 2018.01.14 21:18:12

      세번째 페이지 세번째 줄의 말이 참이기 때문에 당연히 둘쩨줄도 맞습니다. a와 b라는 양수가 있고, a>b이면 a>b2가 됩니다.

      좋아요0
    • 구머 2018.01.14 23:58:25

      제가 질문을 잘못했네요 둘째셋째줄 통째로 물어볼걸..어쨌든 그럼 셋째줄도 설명 가능할까요?(참고로 Xx<Yx는 성립할 수 있지만 bx>ax는 상황에 따라 성립하지 않을 수 있습니다)

      좋아요0
    • 여백 패르마 2018.01.15 09:10:15

      어떤 경우에 성립하지 않죠??(에이가 비보다 큰 경우요.)

      좋아요0
    • 구머 2018.01.15 10:33:48

      그런데 Xi와 Yi가 어떻게 대응되는 거죠? 

      좋아요0
    • 여백 패르마 2018.01.16 21:35:57

      네?? 대응한다고요??

      좋아요0
    • 구머 2018.01.16 22:16:45

      대응하는 개념이 아니라면 반례가 너무나 많습니다. 직접 찾아보시는 것을 추천드립니다.

      좋아요0
    • 여백 패르마 2018.01.17 13:45:32

      아니 대응한다는 개념이 뭐냐라고하는것이고 그리고 대웅하는게 뭔지 말하는 것이였는데요..,

      좋아요0
    • 구머 2018.01.17 15:06:14

      제가 제기한 의문은 'X1이 무엇입니까?, 혹시 X1,X2,...Xk를 정의할 때 어떤 기준을 가지고 정의했습니까?' 였고, 제 생각에는 페르마 님이 기준을 정의하시진 않은 것 같은데, 그렇다면 X1은 어떤 모양의 그래프가 되어도 무방하니 반례가 많이 생길 것이라고 의견을 드렸습니다.

      좋아요0
    • 수학장 2018.01.17 22:33:31

      구머님 말씀은, a_{n-1}(G)의 부분유도그래프들은 많을 텐데, 어떤게 x_{1}, x_{2}, ......인지 x_{i}이 뭔지 설명해달라는 것 같습니다.(예 : 그래프의 크기 순) 정확히 정의를 모르면, x_{i}에 어떤 부분유도그래프가 들어가도 되니까, 반례가 많이 생길 것이라는 의견입니다.

      좋아요0
    • 수학장 2018.01.18 09:48:07

      그리고 a_{n-1}(G)=\left |\sum_{i=1}^{k}a_{i}x_{i} \right | 로 절댓값 붙어야 합니다.............

      좋아요0
    • 여백 패르마 2018.01.20 08:35:21

      아 절댓값 붙인 기호가 엑스 아이 와이 아이 로 정정하겠습니다.그리고,에이 아이가 비 아이보다 더 큰 경우는 없다고 증명했습니다.

      좋아요0
    • 구머 2018.03.15 23:44:31

      아 이제 보네요 ai가 bi보다 큰 반례가 존재합니다. G=완전그래프 K2t에서 n=t일때가 그 예시죠.점이 t개인 그래프는 2tCt개 존재하고, 점이 t+1개인 그래프는 2tCt+1개로 점이 t개인 그래프가 더 많습니다.

      좋아요0
  • 구머 2018.01.19 18:20:06

    풀이에 앞서, 대13 문제는 a(G) 값의 부호에 의미를 두지 않으므로, 풀이에서 사용된 모든 a값들은 그 절댓값으로만 계산할 것이다. 또, 편의상 ai(Pn)를 [i,n]이라고 하자. 이때, [i,n]은 n=2i일 때는 과 값이 똑같고, n<2i일때는 값을 가질 수 없으므로, n>=2i+1인 경우에만 값을 찾으면 된다.

    #1. 점화식

     '점의 개수가 2i개인 Pn의 부분유도그래프들'을 Pn의 맨 앞에 있는 점을 포함하는 연결 그래프의 길이에 따라 분류하자. 이때, 대12 문제의 3번 풀이의 논리와 비슷하게 식을 계산하면, [i,n]은 다음과 같이 계산된다. (단, 주의해야 할 것이 있는데, n=2i일 때는 위의 논증이 불가능하다. 애초에 나올 수 있는 부분유도그래프가 한 가지(Pn)밖에 없기 때문이다. 따라서 n>2i인 경우에만 다음 부등식이 성립할 것이다.)

    [i,n]=a(P_0)[i,n-1]+a(P_2)[i-1,n-3]+...+a(P_{2i})[0,n-2i-1]=C_0[i,n-1]+...+C_i[0,n-2i-1]

    #2. 생성함수

     [i,n]을 구하기 위해 우리는 생성함수를 이용할 것이다. 생성함수 f(x,y)과 g(x,y)을 다음과 같이 정의하자.

    f(x,y)=\sum _{2i\leq n, \left \{n,i\right \} \subseteq {\mathbb{N}_0} }^\infty [i,n]x^iy^n               g(x,y)=\sum _{ i\subseteq {\mathbb{N}_0}}^\infty C_ix^iy^{2i+1}

    이때, 점화식에 의해서 f(x,y)g(x,y)=\sum_{2i<n, \left \{ n,i \right \}\subseteq \mathbb{N}_{0}}^\infty [i,n]x^iy^n=f(x,y)+\sum _{i\subseteq \mathbb{N}_0}^\infty C_ix^iy^{2i}가 성립한다. 여기서 f(x,y)를 구하면,

    f(x,y)=\frac { \sum_ {i\subseteq \mathbb{N}_0}^\infty C_ix^iy^{2i}}{g(x,y)-1}----<1>

    또, 카탈란 수의 생성함수 C(x)=\sum_{i\subseteq \mathbb{N}_0} C_ix^i는 \frac{1-\sqrt{1-4x}}{2x}로 잘 알려져있다. 따라서 g(x,y)=\sum _{ i\subseteq {\mathbb{N}_0}}^\infty C_ix^iy^{2i+1}=\frac{1-{\sqrt{1-xy^2}}}{2xy}이고, 이를 식 <1>에 대입하면

    f(x,y)=\frac{\frac{1-{\sqrt{1-4xy^2}}}{2xy^2}}{\frac{1-{\sqrt{1-4xy^2}}}{2xy}-1}=\frac{{1-{\sqrt{1-4xy^2}}}}{{y-2xy^2-y{\sqrt{1-4xy^2}}}}= \frac{1}{y}(1+\frac{2xy}{1-2xy-\sqrt{1-4xy^2}})가 된다. 이제 저것을 유리화하면

    \frac{1}{y}(1+\frac{2xy}{1-2xy-\sqrt{1-4xy^2}})=\frac{1}{y}(1+\frac{2xy(1-2xy+\sqrt{1-4xy^2})}{(1-2xy)^2-(1-4xy^2)})=\frac{1}{y}(1-\frac{{1-2xy+\sqrt{1-4xy^2}}}{2-2xy-2y})이 된다. 이제 뉴턴의 이항정리를 이용하여 루트, 분모에 있는 항들을 x,y에 대한 다항식으로 표현할 것이다. 또, 뉴턴의 이항정리에 의하면 \frac{1}{2-2xy-2y}=\frac{1}{2}(1+(xy+y)+(xy+y)^2+....)\sqrt{1-4xy^2}=1-2\sum_{i\subseteq \mathbb{N}_0}\frac{1}{i+1}\binom{2i}{i}(xy^2)^{i+1}가 성립할 것이므로 이를 대입하여 정리하면f(x,y)=\frac{1}{y}(1-(1-xy-\sum_{i\subseteq \mathbb{N}_0}\frac{1}{i+1}\binom{2i}{i}(xy^2)^{i+1})(1+(xy+y)+...))가 된다. 여기서 f(x,y)=\sum _{2i\leq n, \left \{n,i\right \} \subseteq {\mathbb{N}_0} }^\infty [i,n]x^iy^n와 계수를 비교하여 주면, 2i<n인 경우,                          

     

    [i,n]=\sum_{t=0}^{i-1}C_t\binom{n-2t-1}{i-t-1}-\binom{n}{i}

     

    라는 결론이 나옵니다. 이는

    //풀었습니다. 답은 (n+2 C i)-(nCi)

    좋아요0 댓글수19
    • 구머 2018.01.19 18:20:29

      작성 중...(참고로 아직 미완성된 풀이입니다)

      좋아요0
    • 수학장 2018.01.19 19:47:54

      대단하시네요..... 전 이게 뭔지 1도 모르겠음..... 괴물같은 수식이네요. 그리고 뒷부분 식 잘못 쓰신 것 같은데

      C_{i}가 i번째 카탈란 수를 의미하는 건가요?

      그리고 한 시간이 지났는데 왜 완성된 풀이는 안 나오죠?

      생성함수가 뭐죠?

      좋아요0
    • 구머 2018.01.19 19:54:41

      지금 더 써야 하는데 시간부족으로 좀 있다 다시 써야 겠네요ㅜ 그리고 i번째 카탈란수 맞습니다

      좋아요0
    • 수학장 2018.01.19 19:56:09

      네 기대할게요^^ (어차피 뭔지 하나도 모를 거지만)

      아! 생각해보니까 생성함수 전 내용은 뭔지 알겠네요. 제가 시도해보려다가 포기한 풀이라.....

      네이버에서 생성함수 강의 듣는 중.....

      좋아요0
    • 구머 2018.01.19 20:22:24

      혹시 뒷부분 어디 식 잘못됬는지 알려주실수 있나요? 그리고 생성함수 이번에 처음 써봐서..틀릴지도 몰라요

      좋아요0
    • 수학장 2018.01.19 20:58:22

      아 잘못 봤어요. 아레에 있는 f(x,y)g(x,y)=\sum_{2i<n, \left \{ n,i \right \}\subseteq\mathbb{N}_{0} }^{\infty }[i,n]x^{i}y^{n}이 부분을 오른쪽을 f(x,y)랑 똑같은 걸로 봤어요. 워낙 비슷해서ᅟᅲ 틀렸는지 맞았는지 모르겠어요. 구머님은 생성함수를 처음 써보지만 저는 처음 봐서........ 나머지도 작성해주세요.

      좋아요0
    • 수학장 2018.01.20 18:34:23

      완성해주세요>< 궁금해요>< ^^

      닉 좀 바꾸고 싶은데 추천 좀

      좋아요0
    • 여백 패르마 2018.01.20 21:41:22

      그런데, 제가 책에서 생성함수를 읽어봐서 아는데, 그 생성함수를 안다고 해도 어떻게 그 생성함수의 각 항의 계수를 알 수 있는가요?? 그리고, \mathbb{N}0은 뭔가요??

      좋아요0
    • 구머 2018.01.20 23:17:39

      각 항의 계수는 저기서 유도를 해야죠.

      그리고 n0는 자연수 집합에 0을 포함한 집합입니다

      좋아요0
    • 여백 패르마 2018.01.21 19:38:55

      아무리 봐도 모르겠는데, 카틀란 수(인가?), 즉 Ci  가 뭔가요??

      좋아요0
    • 수학장 2018.01.21 20:55:24

      여백패르마님 카탈란 수열은 이 파스칼의 삼각형을 이렇게 나열한 후에 n=2k 위에 있는 수들의 수열입니다. n번째 카탈란 수는 \frac{1}{n+1}\binom{2n}{n}=\frac{(2n)!}{n!(n+1)!}입니다.(아래의 파스칼의 수열의 저건 귀찮아서 초록창에 검색해서 블로그에서 퍼온 것임) 카탈란 수열의 정의는 또 여러 가지가 있는데, n+2각형을 n개의 3각형으로 나누는 방법의 수이기도 합니다. 또한, n*n격자에서 왼쪽 위로 대각선을 그어봅시다. 그런 다음, (0,0)에서 (n,n)까지 가는데, 대각선 아래로만 가는 경로의 수이기도 합니다. 저도 수학책에서 본 게 아니라 지난 달에 구머님이 3번 문제 풀었을 때 초록창으로 공부했기 때문에 어떤 게 처음에 발견된 방법인지는 모릅니다.

      좋아요0
    • 여백 패르마 2018.01.28 13:28:50

      그리고 (a+b)^{n}은 \binom{n}{r}의 생성함수라고 알고있는데, 어떻게  (a+b)^{n}에서 \binom{n}{r}의 공식인 \frac{n!}{n-r!r!}를 유도할 수 있지요?

      좋아요0
    • 구머 2018.01.30 17:57:58

      내용을 조금더 추가했습니다. 남는 시간이 그리 많이 없어서 이렇게 조금씩만 추가해서 쓸 생각입니다. 그리고 패르마님 이항계슈 생섬함수로 저 공식을 유도하는 것은 가능하긴 하지만 굳이 생성함수를 사용할 필요가 없고, 생성함수를 쓰면 편리한 것들(ex 카탈란수)을 생성함수를 이용하여 유도합니다.

      https://ko.wikipedia.org/wiki/%EC%B9%B4%ED%83%88%EB%9E%91_%EC%88%98 사이트 참조

      좋아요1
    • 수학장 2018.01.30 18:10:23

      너무 어려워서 잘 이해는 안 가지만 마지막 식을 정리하면

      \frac{1}{y}(1+\frac{2xy(1-2xy+\sqrt{1-4xy^{2}})}{4xy(xy+y+1)})=\frac{1}{y}(1+\frac{1-2xy+\sqrt{1-4xy^{2}}}{2(xy+y+1)})=\frac{1}{y}\frac{2y+3+\sqrt{1-4xy^{2}}}{2(xy+y+1)}=\frac{2y+3+\sqrt{1-4xy^{2}}}{2y(xy+y+1)}

      이네요. 이걸 더 정리 할 수는 없겠죠? 이 다음 과정부터 설명해주시면 됩니다.

      좋아요0
    • 여백 패르마 2018.01.31 12:36:19

      제가 사이트를 봤는데, 그곳에서 뉴턴의 이항정리가 뭐죠??

      이항정리는 (x+y)^{n}=\sum \binom{n}{r} x^{r}y^{n-r}아니였나요??

      즉, 왜 뉴턴이 붙죠?

      좋아요0
    • 구머 2018.02.02 15:26:57

      뉴턴의 이항정리는 (1+a)^n에서 n이 자연수가 아닐 때 계산하는 방법입니딘.

      좋아요0
    • 구머 2018.02.17 22:55:53

      약간의 내용을 추가했습니다^^

      좋아요0
    • 여백 패르마 2018.02.18 19:54:48

      Oh My God

      좋아요0
    • 구머 2018.03.12 01:24:33

      드디어 해결했습니다! 계산실수가 있을지도 모릅니다.

      좋아요0
  • 여백 패르마 2018.01.20 21:10:09

    좋아요0 댓글수3
    • 여백 패르마 2018.01.20 21:14:19

      수수정 풀이 판입니다. 그리고,ai 같은 것들의 그래프들은 제 생각으로는 크기 순서로 하겠습니다.

      좋아요0
    • 구머 2018.01.20 22:01:16

      덧붙이는게 어떤 의미가 있죠? 그리고 xi랑 yi의 크기 관계도 증명 부탁드립니다.

      좋아요0
    • 여백 패르마 2018.01.21 19:36:04

      사실 ai같은 것들의 그래프의 부분유도그래프들의 집합는 bi같은것들의 부분유도그래프들의 집합의 부분집합이기 때문이 당연히 xi <yi 가 성립합니다.

      좋아요0
  • 여백 패르마 2018.01.24 17:18:00

    좋아요0 댓글수3
    • 여백 패르마 2018.01.24 17:19:18

      수학장님의 식을 좀 쉽게 변형했습니다.

      좋아요1
    • 구머 2018.01.24 18:35:16

      근사한 값은 정확한 답이 될수 없습니다.

      좋아요0
    • 여백 패르마 2018.01.24 19:27:25

      네 압니다만, 그래서 접근입니다.

      좋아요0
  • 여백 패르마 2018.01.28 13:21:55

    그냥 혹시나 해서 그러는 건데, 수학동아 2월호가 집에 오신 분 게시나요?

    좋아요0 댓글수4
    • 여백 패르마 2018.01.28 13:32:34

      저는 아직 안 왔어요.

      좋아요0
    • 수학장 2018.01.28 13:50:22

      저도 안 옴

      좋아요0
    • muse 2018.01.30 10:42:01

      저는 28일에 왔어요.

      좋아요0
    • 여백 패르마 2018.01.31 12:38:21

      이제 왔네요.

      좋아요0
  • 여백 패르마 2018.01.31 12:37:20

    언제 평가가 나올것인가요??

    좋아요0 댓글수4
    • 여백 패르마 2018.01.31 12:38:00

      5번하고 제 7번 검토바랍니다.

      좋아요0
    • 수학장 2018.02.02 16:54:15

      5번은 왜요? 6번이겠죠....

      좋아요0
    • 김우현 기자 2018.02.20 09:07:08

      여백 패르마 친구의 (7)번 풀이는 현재 확인 중에 있습니다!!! 과연 결과는 어떻게 될지!?

      조금만 더 기다려 주세요! +_+ (앗, 미안해요. 문제 번호 수정 완료!)

      좋아요0
    • 여백 패르마 2018.02.20 15:55:20

      엥? 전 7번인데요..

      좋아요0