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



S


{\displaystyle S}

 (of cardinality 



n


{\displaystyle n}

), and a size of resulting selection, 



k


{\displaystyle k}

, by reporting the sets of cardinality 



k


{\displaystyle k}

 where each member of those sets is chosen from 



S


{\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 S}

 is 



{

i
c
e
d

,

j
a
m

,

p
l
a
i
n

}


{\displaystyle \{\mathrm {iced} ,\mathrm {jam} ,\mathrm {plain} \}}

, 




|

S

|

=
3


{\displaystyle |S|=3}

, and 



k
=
2


{\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 n}

 types of things taken 



k


{\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 {\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 ^{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 {\binom {n+k-1}{k}}=^{n+k-1}\operatorname {C} _{k}={(n+k-1)! \over (n-1)!k!}}








n

k




{\displaystyle n^{k}}




Task: Combinations with repetitions

Task: Permutations with repetitions



( nextplain generates the next plaindrome in the 
  current base by adding one to a given plaindrome, 
  then replacing each trailing zero with the least
  significant non-zero digit of the number 
 
  See: https://oeis.org/search?q=plaindromes
 
       4 base put    
       -1 
       10 times 
         [ nextplain 
           dup echo sp ]
       drop 
       base release 
 
        prints "0 1 2 3 11 12 13 22 23 33" 
  i.e. decimal "0 1 2 3  5  6  7 10 11 15"
 
  Right padding the base 4 representations with
  zeros gives all the combinations with repetitions
  for selecting two doughnuts in a store selling 
  four types  of doughnut, numbered 0, 1, 2, and 3.
 
     00 01 02 03 11 12 13 22 23 33                      )
 
  [ 1+ dup 0 = if done
    0 swap 
    [ base share /mod 
      dup 0 = while
      drop dip 1+ 
      again ] 
    swap rot 1+ times 
      [ base share * over + ] 
    nip ]                      is nextplain (   n --> n )
 
  [ dup base put
    swap ** 1 - 
    [] swap -1 
    [ 2dup > while
      nextplain
      rot over join 
      unrot 
      again ] 
    base release 
    2drop ]                    is kcombnums ( n n --> [ )
 
  [ [] unrot times
     [ base share /mod 
       rot join swap ]
    drop ]                     is ndigits   ( n n --> [ )
 
  [ [] unrot
    witheach 
      [ dip dup peek 
        nested rot swap join 
        swap ]
    drop ]                     is [peek]    ( [ [ --> [ )
 
  [ dup temp put
    size dup base put
    dip dup kcombnums
    [] unrot witheach 
      [ over ndigits
        temp share swap [peek]
        nested rot swap join 
        swap ] 
    temp release
    base release
    drop ]                     is kcombs    ( n [ --> [ )
 
  2 
  $ "jam iced plain" nest$
  kcombs
  witheach 
    [ witheach 
        [ echo$ sp ] cr ] 
  cr
  3 10 kcombnums size echo