# Permutations or Combinations with less objects than spots

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)

-
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

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.