산화 [607168] · MS 2015 · 쪽지

2016-03-11 01:38:27
조회수 3,332

조합에서 궁금한 것 있습니다!!

게시글 주소: https://ip1ff8si.orbi.kr/0008123464

저는 아직도 중복조합이 왜 조합으로 표현될 수 있는 지 아직도 이해가 안되요..

nHr = n-r+1Cr  이거말입니다!!

서로다른 n개에서 r개를 순서없이 뽑는게 조합이고,
서로다른 n개에서 r개를  중복을 허용해서 순서없이 뽑는게 조합인뎅.
n-r+1개는  서로다른 n-r+1이 아니지 않나요?


그냥 외워서 적용하긴 했다만, 궁금한 점이었어요..

0 XDK (+0)

  1. 유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.

  • 광염 소나타 · 561736 · 16/03/11 02:08 · MS 2015

    한석원T가 그거 유도원리 생각질서에서 알려주시던뎅.. 쓰질않다보니 까먹었네요

  • 산화 · 607168 · 16/03/11 02:13 · MS 2015

    아!! 알고싶어요 !!

  • Zenith · 640530 · 16/03/11 02:11 · MS 2016

    칸막이

  • 산화 · 607168 · 16/03/11 02:13 · MS 2015

    저도 나름 교과서를 중심으로 개념을 잡았던 터라, 칸막이 예시로 조합을 유도했다는 것 까진 이해가 가지만,

    서로다른이란 조건에 충족하지도 않으면서 어떻게 저렇게 되는 지가 매우 궁금해요.

  • 프로깃수생 · 643067 · 16/03/11 02:23 · MS 2016

    A B C 3종류의 알파벳을 중복을 포함하여 8개 뽑는 경우의 수를 생각해 보자. (어떤 알파벳은 안 뽑아도 됨)
    어떤 알파벳을 뽑았는지 모르니까 전부 X로 표시하자. XXXXXXXX 가 되는데, 이러면 구분이 안 된다.
    구분을 하기 위해 구분선을 넣어주자. XXXX/XXX/X
    이러면 맨 왼쪽은 A, 중간은 B, 오른쪽은 C라고 구분할 수가 있게 된다.
    가령 위의 예시는 (A,B,C)=(4,3,1)이고, XXX/XX/XXX 는 (3,2,3) 뭐 이렇게.
    (0,0,8) 같은 것도 //XXXXXXXX 로 표현하면 된다.

    즉, 구분선 (3종류를 구분해야 하니까) 3-1 = 2개, 알파벳 8개를 합쳐서
    10개의 문자로 중복조합을 모두 표현할 수 있는 것이다.
    그러면 이제 10개의 자리 중에 문자가 들어갈 8개를 정해 주면 구분선 2개는 알아서 자리를 잡는다.
    (이는 구분선이 들어갈 자리를 먼저 정해 줘도 마찬가지)

    일반화.
    문제에서 n=3, r=8 이었다.
    (3-1)+8 = 10개의 자리에서 문자가 들어갈 8개를 정하는 것 = 10C8
    (n-1)+r = n+r-1개의 자리에서 문자가 들어갈 r개를 정하는 것 = (n+r-1)Cr

    구분선이 들어갈 자리를 먼저 정해 주면 10C2, (n+r-1)C(n-1) 인데 성질에 의해 어차피 값은 같다.

  • 프로깃수생 · 643067 · 16/03/11 02:27 · MS 2016

    중복조합은
    서로다른 n개에서 중복을 포함하여 ~ 보다는
    n종류를 중복을 포함하여 r개 뽑는 ~ 으로 생각하는 것이 오해의 소지가 없습니다.

    A B C가 각각 5개씩 있는데 여기서 뽑는다~ 라면
    n에 15를 넣을지 3을 넣을지 헷갈려져요

  • 산화 · 607168 · 16/03/11 23:06 · MS 2015

    오오! 제대로 알아갑니다. 감사합니다.!!

  • 산화 · 607168 · 16/03/11 02:23 · MS 2015

    아 ㅋㅋ 제가 바보였군요. 쓰잘데 없이 머리썼습니다...ㅋㅋ

    결국 네이버의 힘을 빌려 해결했습니다!