LFM Stats And Pure > Permutations & Arrangements

There is a staircase of 10 steps which we are to climb. We can go up one step at a time or two steps at a time, but we have to use each method at least once.
(1) Suppose we can go up two steps at a time twice or more in a row. (i) If we climb the staircase going up two steps at a time just 3 times, we will go up one step at a time just $\mathbf{P}$ times, and there are $\mathbf{QR}$ different ways of climbing the staircase. (ii) If we can go up two steps at a time twice or more in a row, there are altogether $\mathbf{ST}$ different ways of climbing the staircase.
(2) Suppose we cannot go up two steps at a time twice or more in a row. (i) If we climb the staircase going up two steps at a time just twice, we will go up one step at a time just $\mathbf{U}$ times, and there are $\mathbf{VW}$ different ways of climbing the staircase. (ii) If we cannot go up two steps at a time twice or more in a row, there are altogether $\mathbf{XY}$ different ways of climbing the staircase.

mat 2003 Q2 Factorial and Combinatorial Expression Simplification

2. Let $k$ and $n$ be positive integers such that $n \geq 2 k$ and
$$\frac { ( n - 2 ) ! } { ( n - 2 k ) ! } = k ! 2 ^ { k - 1 }$$
(Recall that, for $r \geq 1 , r !$ is the product $r \cdot ( r - 1 ) \cdot ( r - 2 ) \ldots 2.1$ and that $0 !$ is defined to equal 1.)
(i) Suppose that $k = 1$. What are the possible values of $n$ ?
(ii) Suppose that $k = 2$. Show that $( n - 2 ) ( n - 3 ) = 4$. What are the possible values of $n$ ?
(iii) Suppose that $k = 3$. Show that it is impossible that $n \geq 7$.
(iv) Suppose that $k \geq 4$. Show that there are no possible values of $n$.

mat 2013 Q5 Forming Numbers with Digit Constraints

5. For ALL APPLICANTS.

We define the digit sum of a non-negative integer to be the sum of its digits. For example, the digit sum of 123 is $1 + 2 + 3 = 6$.
(i) How many positive integers less than 100 have digit sum equal to 8 ?
Let $n$ be a positive integer with $n < 10$.
(ii) How many positive integers less than 100 have digit sum equal to $n$ ?
(iii) How many positive integers less than 1000 have digit sum equal to $n$ ?
(iv) How many positive integers between 500 and 999 have digit sum equal to 8 ?
(v) How many positive integers less than 1000 have digit sum equal to 8 , and one digit at least 5 ?
(vi) What is the total of the digit sums of the integers from 0 to 999 inclusive?

mat 2014 Q5 Combinatorial Proof or Identity Derivation

5. For ALL APPLICANTS.

Poets use rhyme schemes to describe which lines of a poem rhyme. Each line is denoted by a letter of the alphabet, with the same letter given to two lines that rhyme. To say that a poem has the rhyming scheme ABABCDED , indicates that the first and third lines rhyme, the second and fourth lines rhyme, and the sixth and eighth lines rhyme, but no others.
More precisely, the first line of the poem is given the letter A . If a subsequent line rhymes with an earlier line, it is given the same letter; otherwise, it is given the first unused letter. (For the purposes of this question, you can assume that we have an infinite supply of "letters", not just the 26 letters of the alphabet.)
The purpose of this question is to investigate how many different rhyme schemes there are for poems of $n$ lines. We write $r _ { n }$ for this number.
(i) There are five different rhyming schemes for poems of three lines (so $r _ { 3 } = 5$ ). List them.
Let $c _ { n , k }$ denote the number of rhyme schemes for poems with lines $n$ that use exactly $k$ different letters. For example $c _ { 3,2 } = 3$ corresponding to the rhyming schemes AAB , ABA and ABB .
(ii) What is $c _ { n , 1 }$ for $n \geqslant 1$ ?
What is $c _ { n , n }$ ? Explain your answers.
(iii) Suppose that $1 < k < n$. By considering the final letter of a rhyming scheme, explain why
$$c _ { n , k } = k c _ { n - 1 , k } + c _ { n - 1 , k - 1 }$$
(iv) Write down an equation showing how to calculate $r _ { n }$ in terms of the $c _ { n , k }$. Hence calculate $r _ { 4 }$.
(v) Give a formula for $c _ { n , 2 }$ in terms of $n$ (for $n \geqslant 2$ ). Justify your answer.

mat 2017 Q5 Permutation Properties and Enumeration (Abstract)

5. For ALL APPLICANTS.

Ten children, $c _ { 0 } , c _ { 1 } , c _ { 2 } , \ldots , c _ { 9 }$, are seated clockwise in a circle. The teacher walks clockwise behind the children with a large bag of sweets. She gives a sweet to child $c _ { 1 }$. She then skips a child and gives a sweet to the next child, $c _ { 3 }$. Next she skips two children and gives a sweet to the next child, $c _ { 6 }$. She continues in this way, at each stage skipping one more child than at the preceding stage before giving a sweet to the next child.
(i) The $k$ th sweet is given to child $c _ { i }$. Explain why $i$ is the last digit of the number
$$\frac { k ( k + 1 ) } { 2 } .$$
(ii) Let $1 \leqslant k \leqslant 18$. Explain why the $k$ th and ( $20 - k - 1$ )th sweets are given to the same child.
(iii) Explain why the $k$ th sweet is given to the same child as the $( k + 20 )$ th sweet.
(iv) Which children can never receive any sweets?
When the teacher has given out all the sweets, she has walked exactly 183 times round the circle, and given the last sweet to $c _ { 0 }$.
(v) How many sweets were there initially?
(vi) Which children received the most sweets and how many did they receive?

taiwan-gsat 2010 Q1 Counting or Combinatorial Problems on APs

1. If each term in the sequence $a_{1}, a_{2}, \ldots, a_{k}, \ldots, a_{10}$ is either 1 or $-1$, how many possible values can $a_{1} + a_{2} + \cdots + a_{k} + \cdots + a_{10}$ take?
(1) 10
(2) 11
(3) $P_{2}^{10}$
(4) $C_{2}^{10}$
(5) $2^{10}$

taiwan-gsat 2022 Q3 5 marks Selection with Adjacency or Spacing Constraints

Eight buildings are arranged in a row, numbered 1, 2, 3, 4, 5, 6, 7, 8 from left to right. A telecommunications company wants to select three of these buildings' rooftops to install telecommunications base stations. If base stations cannot be installed on two adjacent buildings to avoid signal interference, how many ways are there to select locations for the base stations if no base station is installed on building 3?
(1) 12
(2) 13
(3) 20
(4) 30
(5) 35

taiwan-gsat 2022 Q10 6 marks Distribution of Objects into Bins/Groups

A teacher requires the class monitor to distribute review sheets for Chinese, English, Mathematics, Social Studies, and Science—5 subjects in total—over Monday, Tuesday, Wednesday, and Thursday of next week. At least one subject's sheet must be distributed each day for students to take home for practice and submit the next day. Since there are Chinese and English classes on Tuesday, the Chinese teacher requires that the Chinese sheet must be distributed on Monday for review; and the English teacher, having assigned other work that day, requires that the English sheet not be distributed on Tuesday. According to these requirements, the class monitor has ways to arrange the distribution.

taiwan-gsat 2022 Q17 5 marks Linear Arrangement with Constraints

There are six students (three female and three male) who frequently interact with a teacher at school. After graduation, the teacher invites them to a gathering. After the meal, seven people stand in a row for a commemorative photo. It is known that among the students, one female and one male had an unpleasant experience and do not want to stand adjacent during the photo, while the teacher stands in the middle and the three male students do not all stand on the same side of the teacher. The total number of possible arrangements is (17--1)(17--2)(17--3).

taiwan-gsat 2025 Q3 5 marks Linear Arrangement with Constraints

A school is holding a concert with 5 piano performances, 4 violin performances, and 3 vocal performances, totaling 12 different pieces. The school wants to arrange performances of the same type together, and vocal performances must come after either piano or violin performances. How many possible arrangements of pieces are there for this concert?
(1) $5 ! \times 4 ! \times 3 !$
(2) $2 \times 5 ! \times 4 ! \times 3 !$
(3) $3 \times 5 ! \times 4 ! \times 3 !$
(4) $4 \times 5 ! \times 4 ! \times 3 !$
(5) $6 \times 5 ! \times 4 ! \times 3 !$

taiwan-gsat 2025 Q11 6 marks Distribution of Objects into Bins/Groups

A washing machine cycle must select one from 5 different fabric types (1, 2, 3, 4, 5), paired with one of 4 different modes (A, B, C, D), and there are 3 additional functions (A, B, C) that can be freely chosen to enable or disable. However, ``fabric type 1'' cannot be used simultaneously with additional function ``A''. For example, ``fabric type 2'' paired with ``mode A'', with both ``A'' and ``B'' additional functions enabled is a valid cycle; but ``fabric type 1'' paired with ``mode A'', with both ``A'' and ``B'' additional functions enabled is not a valid cycle. Based on the above, this washing machine has how many valid cycles?

tmua None Q13 Linear Arrangement with Constraints

13. Five runners competed in a race: Fred, George, Hermione, Lavender, and Ron.
Fred beat George. Hermione beat Lavender. Lavender beat George. Ron beat George.
Assuming there were no ties, how many possible finishing orders could there have been, given only this information?
A 1
B 6
C 12
D 18
E 24 F 120

tmua 2017 Q20 1 marks Permutation Properties and Enumeration (Abstract)

I have forgotten my 5-character computer password, but I know that it consists of the letters $\mathrm { a } , \mathrm { b } , \mathrm { c } , \mathrm { d } , \mathrm { e }$ in some order. When I enter a potential password into the computer, it tells me exactly how many of the letters are in the correct position.
When I enter abcde, it tells me that none of the letters are in the correct position. The same happens when I enter cdbea and eadbc.
Using the best strategy, how many further attempts must I make in order to guarantee that I can deduce the correct password?
A None: I can deduce it immediately
B One
C Two
D Three
E More than three

todai-math 2018 Q6 Distribution of Objects into Bins/Groups

There are $n$ children queuing in a line. You have $m$ candies and will begin handing out 1 or 2 candies to each child, starting from the first child in the line. You hand out the candies until reaching the end of the line or until there are no candies left. Answer the following questions. Note that $n$ and $m$ are positive integers.
I. Show the number of distribution patterns of candies if $n = m = 4$.
II. Show the number of distribution patterns of candies if $m \geq 2 n$.
III. Define $X _ { m }$ as the number of distribution patterns of candies if $n \geq m$. Show the recurrence formula satisfied by $X _ { m }$.
IV. Obtain $X _ { m }$ using the recurrence formula in Question III.
V. Consider the situation where the number of children is larger than the number of candies. Define $P ( m )$ as the ratio of the number of distribution patterns (where the distribution finishes by giving 2 candies) to the total number of distribution patterns. $P ( m )$ converges as $m$ increases. Compute the convergence value.
VI. Consider the situation where $m \geq 2 n$. The following rules are added to the way of handing out the candies: For the first child in the line, the probability of receiving 1 candy is $1 / 2$ and the probability of receiving 2 candies is $1 / 2$. If a child receives 1 candy, the probability of the next child receiving 1 candy is $1 / 2$ and the probability of receiving 2 candies is $1 / 2$. If a child receives 2 candies, the probability of the next child receiving 1 candy is $3 / 4$ and the probability of receiving 2 candies is $1 / 4$. Compute the probability that the $n$-th child in the line receives 2 candies.

turkey-yks 2010 Q12 Symmetric Group and Permutation Properties

On the set $A = \{1,2,3,4,5\}$ $$f = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 3 & 1 & 5 & 2 & 4 \end{pmatrix}, \quad g = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 3 & 4 & 1 & 2 \end{pmatrix}$$ For the permutations, what is the value of $g f^{-1}(2)$?
A) 1
B) 2
C) 3
D) 4
E) 5

turkey-yks 2011 Q7 Factorial and Combinatorial Expression Simplification

For two-digit positive integers a and b
$$\frac { a ! } { b ! } = 132$$
Given this, what is the sum $\mathbf { a } + \mathbf { b }$?
A) 22
B) 23
C) 24
D) 25
E) 26

turkey-yks 2014 Q16 Counting Functions with Composition or Mapping Constraints

Let $A = \{ 1,2,3 \}$ and $f : A \rightarrow A$ be a function. How many one-to-one functions $f$ satisfy the condition
$$f ( n ) \neq n$$
for every $n \in A$?
A) 1
B) 2
C) 3
D) 4
E) 5

turkey-yks 2014 Q31 Linear Arrangement with Constraints

Three domestic automobiles of brands A, B, and C and three foreign automobiles of brands X, Y, and Z will be displayed in a single row at an exhibition according to the following conditions.

Domestic and foreign automobiles will be arranged consecutively within their own groups.
Brand A automobile will be in the first or last position among all automobiles.
Brand X automobile will be in the first or last position among foreign automobiles.

Given this, in how many different ways can the automobiles be displayed?
A) 10
B) 12
C) 14
D) 16
E) 18

turkey-yks 2016 Q4 Factorial and Combinatorial Expression Simplification

$$\frac { ( n + 1 ) ! + ( n - 1 ) ! } { n ^ { 3 } - 1 } = 24$$
Given this equality, what is n?
A) 3
B) 5
C) 6
D) 8
E) 9

turkey-yks 2016 Q11 Integer Solutions of an Inequality

$$\mathrm { A } = \left\{ \mathrm { n } ( - 1 ) ^ { \mathrm { n } } : \mathrm { n } = 1,2,3 , \ldots , \mathrm { k } \right\}$$
The difference between the largest and smallest elements of the set is 25. Accordingly, how many positive elements does set A have?
A) 4
B) 6
C) 8
D) 10
E) 12

turkey-yks 2016 Q18 Selection with Adjacency or Spacing Constraints

A table consisting of two rows and 7 cells is given in the figure.
Patterns are created by painting 4 cells of this table black.
How many different patterns are there such that each row has at least one painted cell?
A) 26
B) 28
C) 30
D) 32
E) 34

turkey-yks 2017 Q4 Factorial and Combinatorial Expression Simplification

$\frac { 6 ! + 7 ! } { ( 4 ! ) ^ { 2 } }$\ What is the result of this operation?\ A) 10\ B) 12\ C) 15\ D) 18\ E) 20

turkey-yks 2019 Q19 Circular Arrangement

Six friends named Ayça, Büşra, Ceyda, Deniz, Erdem and Furkan attending a party have a table with 6 chairs around it as shown in the figure.
Ayça and Büşra, who are on bad terms, do not want to sit in chairs that are next to each other or facing each other at this table. Accordingly, in how many different ways can these six friends sit in these chairs around the table?
A) 432
B) 384
C) 360
D) 288
E) 240

turkey-yks 2020 Q28 Linear Arrangement with Constraints

Two students from each of three different schools will participate in a chess tournament. In the first round of the tournament, each student will be paired with a student who is not from their own school.
Accordingly, in how many different ways can the pairing in the first round be done?
A) 6
B) 8
C) 9
D) 12
E) 15

turkey-yks 2024 Q14 Selection with Adjacency or Spacing Constraints

Melisa will stack 10 circular cardboards with radii $1\text{ cm}, 2\text{ cm}, 3\text{ cm}, \cdots, 10\text{ cm}$ on a table with their centers coinciding, where each has a different natural number radius.
In how many different ways can Melisa arrange them so that when viewed from above, exactly one of the circles is completely hidden?
A) 36 B) 40 C) 45 D) 48 E) 54