Counting and Combinatorics

Help Questions

GRE Quantitative Reasoning › Counting and Combinatorics

Questions 1 - 7
1

A bookstore will create a display by arranging 5 different books in a row on a shelf. Two particular books, $A$ and $B$, must not be adjacent. How many arrangements are possible?

24

48

72

96

120

Explanation

This question tests counting with a restriction on adjacency. Order matters since we're arranging books, so we use permutations. Total arrangements without restriction: 5! = 120. To find arrangements where A and B are not adjacent, we subtract arrangements where they are adjacent. When A and B are adjacent, treat them as a single unit: we have 4 units to arrange in 4! = 24 ways, and A and B can be ordered within their unit in 2! = 2 ways, giving 24×2 = 48 arrangements with A and B adjacent. Therefore, arrangements where A and B are not adjacent: 120 - 48 = 72. A common error is forgetting to multiply by 2 when A and B are treated as a unit, giving the incorrect answer of 96.

2

How many distinct 6-letter strings can be formed using the letters in the word $\text{BANANA}$ if each string uses all 6 letters?

30

60

90

120

720

Explanation

This question tests permutations with repeated elements. Order matters since we're arranging letters to form strings, but we must account for identical letters. BANANA has 6 letters: B(1), A(3), N(2). If all letters were distinct, we'd have 6! = 720 arrangements. However, we must divide by the factorial of each letter's frequency to avoid overcounting identical arrangements. The number of distinct arrangements is 6!/(1!×3!×2!) = 720/(1×6×2) = 720/12 = 60. A common mistake is forgetting to divide by the factorials of repeated letters, leading to the incorrect answer of 720.

3

A store sells 4 types of fruit: apples, bananas, oranges, and pears. A customer buys exactly 6 pieces of fruit, and at least 1 piece of each type. How many different purchases are possible (where order does not matter)?

6

10

12

15

20

Explanation

This question tests counting with the stars and bars method combined with constraints. Order doesn't matter for fruit purchases, making this a combinations problem. We need exactly 6 pieces total with at least 1 of each type. First, we allocate 1 piece to each of the 4 types, using 4 pieces. This leaves 2 pieces to distribute freely among the 4 types. Using stars and bars, distributing 2 identical items into 4 distinct categories gives us C(2+4-1, 4-1) = C(5,3) = 10 ways. The constraint of at least one of each type is handled by the initial allocation. A common mistake would be trying to use C(6+4-1, 4-1) = C(9,3) = 84, which doesn't account for the minimum requirement.

4

A company is assigning 4 distinct tasks to 4 distinct employees. Employee $X$ cannot be assigned to Task 1 or Task 2. All other assignments are allowed. How many valid assignments are possible?

8

10

12

16

24

Explanation

This question tests permutations with assignment restrictions. Order matters since tasks are distinct and assigned to specific employees. Without restrictions: 4! = 24 ways to assign 4 tasks to 4 employees. With the restriction that Employee X cannot do Task 1 or Task 2, X has only 2 choices (Task 3 or Task 4). Once X is assigned, the remaining 3 employees can be assigned to the remaining 3 tasks in 3! = 6 ways. Total valid assignments: 2 × 6 = 12. Choice C correctly identifies this count. Choice E (24) represents the unrestricted case, failing to account for X's limitations.

5

A teacher must assign 5 different students to 5 different seats in a row. Two of the students, X and Y, must not sit next to each other. How many different seating arrangements are possible?

24

48

72

96

120

Explanation

This question tests counting permutations with a restriction on adjacency. Order matters since we're arranging students in specific seats. We can use complementary counting: find the total arrangements without restrictions, then subtract arrangements where X and Y sit together. Total arrangements of 5 students is 5! = 120. To count arrangements where X and Y are adjacent, treat them as a single unit that can be arranged in 2 ways (XY or YX), and this unit plus the 3 other students gives us 4 units to arrange in 4! ways. So there are 2 × 4! = 2 × 24 = 48 arrangements where X and Y are adjacent. Therefore, arrangements where they're not adjacent is 120 - 48 = 72. A common error is forgetting to account for the two ways X and Y can be ordered within their adjacent pair.

6

How many different 8-character strings can be formed using only the letters A, B, and C if the string contains at least one A and at least one B?

$3^8$ - 2\cdot $2^7$ + 1

$3^8$ - $2^8$

$2^8$ - 1

$3^8$ - 2\cdot $2^8$

$3^8$ - 2\cdot $2^8$ + 1

Explanation

This question tests counting with inclusion-exclusion principle. Order matters for strings, and we can use any of 3 letters in each of 8 positions. We want strings with at least one A and at least one B, which we can find using inclusion-exclusion: total strings minus those missing A or B. Total 8-character strings using {A,B,C} is $3^8$. Strings without A use only {B,C}, giving $2^8$ possibilities. Strings without B also give $2^8$ possibilities. Strings without both A and B use only C, giving $1^8$ = 1 possibility. By inclusion-exclusion: $3^8$ - $2×2^8$ + 1. The +1 corrects for double-subtracting strings with only C. A common error is forgetting this correction term or applying inclusion-exclusion incorrectly.

7

A password consists of 3 distinct letters followed by 2 distinct digits. Letters are chosen from the 26 English letters and digits from 0–9. How many different passwords are possible?

$(26\cdot25\cdot24)\cdot\binom{10}{2}=780,000$

$\binom{26}{3}\binom{10}{2}=32,500$

$\binom{26}{3}\cdot(10\cdot9)=234,000$

$26^3\cdot 10^2=1,757,600$

$26\cdot25\cdot24\cdot10\cdot9=1,404,000$

Explanation

This question tests counting with order and distinctness constraints. Order matters for passwords, and we need distinct characters within each category. For 3 distinct letters from 26: first letter has 26 choices, second has 25, third has 24, giving 26×25×24 = 15,600 ways. For 2 distinct digits from 10: first digit has 10 choices, second has 9, giving 10×9 = 90 ways. Total passwords = 15,600 × 90 = 1,404,000. The key insight is recognizing this as a permutation problem (order matters) with no repetition allowed. A common error is using combinations instead of permutations, as in answer B, which incorrectly treats the password as an unordered selection.