순서와 K-순열의 찾기 수 있지만 반복

Question

임 truggling는 K-순열 세트 카디널리티 N의 S의의 수에 대한 폐쇄 양식을 찾을 수 있습니다.

조합은 순서를 고려해야하지만 반복은 고려해야합니다.

예 :

|S| = n = 3 
S = {a,b,c} 
k = 2 

{a,b} 
{b,a} 
{b,c} 
{c,b} 
{a,c} 
{c,a} 

누구나 가능한 순열 (그리고 순열 자체)의 수를 계산하는 방법 나를 도울 수 있을까? 나는 무엇을 시도했다

: 나는 다른 물질을 통해 읽고 repitititions 포함 그것이 것을 발견했습니다

O(n) = n^k 

내 초기하지만 내가

같은 순열을 eliminiate 필요가 있었다

{a,a} 
{b,b} 
{c,c} 

그러나 나는 인식 할 수있는 반복의 숫자에 대한 닫힌 양식을 찾는 데 어려움을 겪고 있습니다.

Answer 1

카디널리티 n의 집합 S의 k- 순열 수를 찾고 있습니다.

공식은 잘 알려져있다 : n!/(n-k)!

의사 증거 : 1 요소

• , 당신은 S의 n 개의 요소 중에서 선택할 수 있습니다;
• 두 번째에만 해당 : n-1, 당신은 doublons을 원하지 않으므로;
• ...
• 다음 중 i : n- (i-1);
• ...
• , k-의 경우에만, n- (k-1);

그래서 최종적 : * N 개 (N-1) * ... * (N-1) * ... * (N-K + 1) = N !/(n-k)!