Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Permutations mean: take n objects and put them in to k spots, order matters ($abc \neq acb$)

Combinations mean: take n objects and put them in to k spots, order doesn't matter ($abc = acb$)

But what are combinations or permutations which have less objects than spots to put, and how to calculate all posible combin. or permut?

For example:

I want to know how many 4 digit numbers I can make using numbers 0 and 1.(Permutations) I don't know how to write it in latex, but it would look like '2P4', but thats not valid.

What I want to get:

0000 0001 0010 0011 ... 1111 (16 permutations)

share|improve this question
    
Since you can reuse numbers, there are $n^s$ possible words of length $s$ over your alphabet of size $n$. –  Anthony Labarre Jul 15 '11 at 8:43
    
@AnthonyLabarre What about combinations? For my example they would be 0000 0001 0011 0111 1111 –  anonymous Jul 15 '11 at 8:58
    
@anonymous: That would be combinations with repetitions. But for binary it's even easier: you just need to select when you stop putting $0$s and start putting $1$s, and there are five possible places (before the first, i.e., no 0s; in between positions $n$ and $n+1$, $n=1,2,3$; or after the fourth positions, i.e., no 1s). –  Arturo Magidin Jul 15 '11 at 18:35

1 Answer 1

up vote 1 down vote accepted

You’re not using the terms permutation and combination with their usual meanings. If I understand you correctly, you have $n$ kinds of object (e.g., the numbers $0,1,\dots,n-1$), and you want to form strings of $k$ of them, allowing repetitions and not requiring that every kind of object appear. (In your example, $n=4$ and $k=2$.) You want to count such strings in two ways.

(1) What you’re calling permutations: the order of the $k$ things matters. This is the case that Anthony Labarre answered: there are $n$ ways to choose the first object, $n$ ways to choose the second, and so on right down to the $k$-th and last object, so there are altogether $n^k$ such strings. If the objects are the numbers $0,1,\dots,n-1$, you’re counting the number of base $n$ integers that can be written with at most $k$ digits.

(2) What you’re calling combinations: all you care about now is how many of each kind of object appears in the string. In your example, for instance, $0111,1011,1101$, and $1110$ all have one $0$ and three $1$s, so they get counted as a single ‘combination’. Suppose that the objects are the numbers $0,1,\dots,n-1$. For $i=1,2,\dots,n-1$ let $k_i$ be the number of times $i$ occurs in a string; since each string has $k$ objects altogether, we must have $k_0 + k_1 + \dots + k_{n-1} = k$, where each $k_i$ is a non-negative integer. Conversely, any list $\langle k_0,k_1,\dots,k_{n-1} \rangle$ in which $k_0 + k_1 + \dots + k_{n-1} = k$ represents one possible ‘combination’. Thus, there are as many ‘combinations’ as there are solutions to the equation $k_0 + k_1 + \dots + k_{n-1} = k$ in non-negative integers. This is a standard problem; the answer is ${{n+k-1} \choose k}$. The discussions here and here may be useful.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.