# Questions tagged [combinations]

Combinations are subsets of a given size of a given finite set. All questions for this tag have to directly involve combinations; if instead the question is about binomial coefficients, use that tag.

7,853 questions
Filter by
Sorted by
Tagged with
25k views

### Proof of the hockey stick/Zhu Shijie identity $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$

After reading this question, the most popular answer use the identity $$\sum_{t=0}^n \binom{t}{k} = \binom{n+1}{k+1},$$ or, what is equivalent, $$\sum_{t=k}^n \binom{t}{k} = \binom{n+1}{k+1}.$$ What's ...
• 1,620
8k views

### How many 7-note musical scales are possible within the 12-note system?

This combinatorial question has a musical motivation, which I provide below using as little musical jargon as I can. But first, I'll present a purely mathematical formulation for those not interested ...
• 9,666
2k views

### What Rubik's Twist configuration has the lowest visible surface area?

The Rubik's Twist has been a fun time sink. From the wiki page, [It] is a toy with twenty-four wedges that are right isosceles triangular prisms. The wedges are connected by spring bolts, so that ...
• 111
9k views

### The pigeonhole principle and a professor who knows $9$ jokes and tells $3$ jokes per lecture

A professor knows $9$ jokes and tells $3$ jokes per lecture. Prove that in a course of $13$ lectures there is going to be a pair of jokes that will be told together in at least $2$ lectures. I've ...
70k views

### Formula for Combinations With Replacement

I understand how combinations and permutations work (without replacement). I also see why a permutation of $n$ elements ordered $k$ at a time (with replacement) is equal to $n^{k}$. Through some ...
• 4,429
6k views

### How many lists of 100 numbers (1 to 10 only) add to 700?

Each number is from one to ten inclusive only. There are $100$ numbers in the ordered list. The total must be $700$. How many such lists? Note: if, as it happens, this is one of those math problems ...
• 1,343
57k views

### Counting bounded integer solutions to $\sum_ia_ix_i\leqq n$

I want to find the number of nonnegative integer solutions to $$x_1+x_2+x_3+x_4=22$$ which is also the number of combinations with replacement of $22$ items in $4$ types. How do I apply stars and bars ...
96k views

### Calculating the number of possible paths through some squares

I'm prepping for the GRE. Would appreciate if someone could explain the right way to solve this problem. It seems simple to me but the site where I found this problem says I'm wrong but doesn't ...
• 309
7k views

### Passwords: Two 50-characters vs one 100-characters

In this Information Security question, we discuss whether or not a $100$ character secret randomly-generated username is equivalent to a $50$ character secret randomly-generated username plus a $50$ ...
2k views

### Lottery Math (different combinations)

In my country, Brazil, we have a lottery game called "Mega-Sena". You can choose from 6 (cheapest set) to 15 (most expensive set) numbers from a total of 60. *Blue: Chosen numbers; *Green: Amount of ...
• 352
93k views

### How many triangles can be formed by the vertices of a regular polygon of $n$ sides?

How many triangles can be formed by the vertices of a regular polygon of $n$ sides? And how many if no side of the polygon is to be a side of any triangle ? I have no idea where I should start to ...
• 335
2k views

• 5,480
27k views

### Arrangements of a,a,a,b,b,b,c,c,c in which no three consecutive letters are the same

Q: How many arrangements of a,a,a,b,b,b,c,c,c are there such that $\hspace{5mm}$ (i). no three consecutive letters are the same? $\hspace{5mm}$ (ii). no two consecutive letters are the same? A:(i). ...
• 1,226
30k views

### How many subsets of set $\{1,2,\ldots,10\}$ contain at least one odd integer?

How many subsets of set $\{1,2,\ldots,10\}$ contain at least one odd integer? My Working: What I can think of is subtracting the no. of subsets that don't contain a single odd number from the ...
• 2,662
1k views

### Calculate the sum of inverse values of ${n\choose 0}, {n\choose 1}, ... {n\choose n}$

Calculate $$A={1\over {n\choose 0}}+ {1\over {n\choose 1}}+ ...+{1\over {n\choose n}}$$ and $$B={1\over {n\choose 0}}- {1\over {n\choose 1}}+ ...+{(-1)^n\over {n\choose n}}$$ My idea for $A$ is ...
• 90.1k
425 views

### The best $n$-digit password?

I suddenly thought of a question today: What is the best $n$-digit password? It is not specific so I'll write it in a better way: There is a password lock that has $n$ digits. There are $t$ choices ...
• 4,043
8k views

### Finding how many 8-bit bytes contain an even number of zeros . . .

I believe I'm overthinking this or otherwise confused but I believe that the method to solve this would be $2^n$ where n is the length of the bytes? So in this particular case it would be $2^8$ equal ...
317 views

### How to prove that $\frac{(12!)!}{12!^{11!}}$ is integer? [duplicate]

So far I have used that a combination is an integer so $\frac{n!}{m!(n-m)!}$ is integer. Now let $n=mb$ so $\frac{mb!}{m!(mb-m)!}$. What is left is to prove that $\frac{(mb)!}{m!^b}$ is integer so ...
• 401
1k views

### Is the sum of permutations of disjointed sets larger than the count of permutations in their union?

My wife and I are having a bit of a disagreement. Concerning eight-digit passwords like the kind most secure websites require, she believes you could generate more unique password combinations by ...
• 175