If I have $m$ $k$-tuples, how many combinations of a single element from the $k$-tuple are possible?

Concrete example:

If I have 6 2-tuples of the form $(a_1, b_1),(a_2, b_2), ... ,(a_6, b_6) $, and the stipulation that I can only draw one element from each tuple (so if I select $a_1$ I can no longer select $b_1$), how many combinations of $a_i$ and $b_i$ are possible?

Edit: You must select an element from each tuple.


1 Answer 1


Let $(a_{1,j},a_{2,j},\ldots, a_{k,j})$ be the $j$'th $k$-tuple. From each $k$-tuple, you can either choose one of the $k$ elements, or choose none. This means you have $k+1$ choices for each tuple, implying you have $(k+1)^m$ choices in total.

  • $\begingroup$ Just to be clear - there is no option to select none, you must select one. So you only have $k$ choices, so you have $(k)^m$ choices in total? For the concrete example, 64 choices? $\endgroup$
    – Jared
    Commented Dec 5, 2016 at 20:54
  • $\begingroup$ @Jared, Oh, yeah, if you can't pick none it's just $k^m$. $\endgroup$
    – Marcus M
    Commented Dec 5, 2016 at 23:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .