user
The set of combinations with repetitions is computed from a set, 

S
{\displaystyle {\displaystyle S}}
 (of cardinality 

n
{\displaystyle {\displaystyle n}}
), and a size of resulting selection, 

k
{\displaystyle {\displaystyle k}}
, by reporting the sets of cardinality 

k
{\displaystyle {\displaystyle k}}
 where each member of those sets is chosen from 

S
{\displaystyle {\displaystyle S}}
.
In the real world, it is about choosing sets where there is a “large” supply of each type of element and where the order of choice does not matter.
For example:

:   Q: How many ways can a person choose two doughnuts from a store selling three types of doughnut: iced, jam, and plain? (i.e., 

    S
    {\displaystyle {\displaystyle S}}
     is 

    {

    i
    c
    e
    d
    ,

    j
    a
    m
    ,

    p
    l
    a
    i
    n
    }
    {\displaystyle {\displaystyle \{\mathrm {iced} ,\mathrm {jam} ,\mathrm {plain} \}}}
    , 

    |
    S

    |
    =
    3
    {\displaystyle {\displaystyle |S|=3}}
    , and 

    k
    =
    2
    {\displaystyle {\displaystyle k=2}}
    .)

:   A: 6: {iced, iced}; {iced, jam}; {iced, plain}; {jam, jam}; {jam, plain}; {plain, plain}.

Note that both the order of items within a pair, and the order of the pairs given in the answer is not significant; the pairs represent multisets.
  
Also note that *doughnut* can also be spelled *donut*.

Task

* Write a function/program/routine/.. to generate all the combinations with repetitions of 

  n
  {\displaystyle {\displaystyle n}}
   types of things taken 

  k
  {\displaystyle {\displaystyle k}}
   at a time and use it to *show* an answer to the doughnut example above.
* For extra credit, use the function to compute and show *just the number of ways* of choosing three doughnuts from a choice of ten types of doughnut. Do not show the individual choices for this part.

References

* k-combination with repetitions

See also

:   :   :   :   The number of samples of size k from n objects.
                  
                  
                With   combinations and permutations   generation tasks.

                |  | Order Unimportant | Order Important |
                | --- | --- | --- |
                | Without replacement | (  n k  )  =  n  C  k =    n ( n − 1 ) … ( n − k + 1 )  k ( k − 1 ) … 1 {\displaystyle {\displaystyle {\binom {n}{k}}=^{n}\operatorname {C} \_{k}={\frac {n(n-1)\ldots (n-k+1)}{k(k-1)\dots 1}}}} | n  P  k = n ⋅ ( n − 1 ) ⋅ ( n − 2 ) ⋯ ( n − k + 1 ) {\displaystyle {\displaystyle ^{n}\operatorname {P} \_{k}=n\cdot (n-1)\cdot (n-2)\cdots (n-k+1)}} |
                | Task: Combinations | Task: Permutations |
                | With replacement | (   n + k − 1 k  )  =  n + k − 1  C  k =    ( n + k − 1 ) !  ( n − 1 ) ! k ! {\displaystyle {\displaystyle {\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} \_{k}={(n+k-1)! \over (n-1)!k!}}} | n  k {\displaystyle {\displaystyle n^{k}}} |
                | Task: Combinations with repetitions | Task: Permutations with repetitions |
assistant
(formerly Perl 6)

One could simply generate all permutations, and then remove "duplicates":

**Works with**: Rakudo version 2016.07

```
my @S = <iced jam plain>;
my $k = 2;

.put for [X](@S xx $k).unique(as => *.sort.cache, with => &[eqv])

```

Output:

```
iced iced
iced jam
iced plain
jam jam
jam plain
plain plain

```

Alternatively, a recursive solution:

**Translation of**: Haskell

```
proto combs_with_rep (UInt, @) {*}
 
multi combs_with_rep (0,  @)  { () }
multi combs_with_rep (1,  @a)  { map { $_, }, @a }
multi combs_with_rep ($,  []) { () }
multi combs_with_rep ($n, [$head, *@tail]) {
    |combs_with_rep($n - 1, ($head, |@tail)).map({ $head, |@_ }),
    |combs_with_rep($n, @tail);
}
 
.say for combs_with_rep( 2, [< iced jam plain >] );
 
# Extra credit:
sub postfix:<!> { [*] 1..$^n }
sub combs_with_rep_count ($k, $n) { ($n + $k - 1)! / $k! / ($n - 1)! }
 
say combs_with_rep_count( 3, 10 );

```

Output:

```
(iced iced)
(iced jam)
(iced plain)
(jam jam)
(jam plain)
(plain plain)
220
```