search
Log In

Recent questions tagged kenneth-rosen

0 votes
0 answers
1
Question $33-37$ deal with a variation of the $\textbf{Josephus problem}$ described by Graham, Knuth, and Patashnik in $[G_{r}K_{n}P_{a}94].$ This problem is based on an account by the historian Flavius Josephus, who was part of a band of $41$ ... $34,$ making use of the recurrence relation from question $35.$
asked May 2 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
2
Question $33-37$ deal with a variation of the $\textbf{Josephus problem}$ described by Graham, Knuth, and Patashnik in $[G_{r}K_{n}P_{a}94].$ This problem is based on an account by the historian Flavius Josephus, who was part of a band of $41$ Jewish rebels trapped in a cave by the Romans during the Jewish Roman ...
asked May 2 in Combinatory Lakshman Patel RJIT 6 views
0 votes
0 answers
3
Question $33-37$ deal with a variation of the $\textbf{Josephus problem}$ described by Graham, Knuth, and Patashnik in $[G_{r}K_{n}P_{a}94].$ This problem is based on an account by the historian Flavius Josephus, who was part of a band of $41$ Jewish rebels trapped in a cave by ... [Hint: Write $n = 2^{m} + k,$ where $m$ is a nonnegative integer and $k$ is a nonnegative integer less than $2m.]$
asked May 2 in Combinatory Lakshman Patel RJIT 7 views
0 votes
0 answers
4
Question $33-37$ deal with a variation of the $\textbf{Josephus problem}$ described by Graham, Knuth, and Patashnik in $[G_{r}K_{n}P_{a}94].$ This problem is based on an account by the historian Flavius Josephus, who was part of a band of $41$ Jewish rebels trapped in a cave by the ... number of the survivor by $J (n).$ Determine the value of $J (n)$ for each integer $n$ with $1 \leq n \leq 16.$
asked May 2 in Combinatory Lakshman Patel RJIT 7 views
0 votes
0 answers
5
In the Tower of Hanoi puzzle, suppose our goal is to transfer all $n$ disks from peg $1$ to peg $3,$ but we cannot move a disk directly between pegs $1$ and $3.$ Each move of a disk must be a move involving peg $2.$ As usual, we cannot place a ... that no disk is on top of a smaller disk? Show that every allowable arrangement of the n disks occurs in the solution of this variation of the puzzle.
asked May 2 in Combinatory Lakshman Patel RJIT 10 views
0 votes
0 answers
6
Use the recurrence relation developed in Example $5$ to determine $C_{5},$ the number of ways to parenthesize the product of six numbers so as to determine the order of multiplication. Check your result with the closed formula for $C_{5}$ mentioned in the solution of Example $5.$
asked May 2 in Combinatory Lakshman Patel RJIT 6 views
0 votes
0 answers
7
Write out all the ways the product $x_{0} \cdot x_{1} \cdot x_{2} \cdot x_{3} \cdot x_{4}$ can be parenthesized to determine the order of multiplication. Use the recurrence relation developed in Example $5$ to calculate $C_{4},$ the number of ways to parenthesize the product ... result in part $(B)$ by finding $C_{4},$ using the closed formula for $C_{n}$ mentioned in the solution of Example $5.$
asked May 2 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
8
Let $S(m, n)$ denote the number of onto functions from a set with m elements to a set with $n$ elements. Show that $S(m, n)$ satisfies the recurrence relation $S(m, n) = n^{m} − \sum_{k=1 }^{n−1} C(n, k)S(m, k)$ whenever $m \geq n$ and $n > 1,$ with the initial condition $S(m, 1) = 1.$
asked May 2 in Combinatory Lakshman Patel RJIT 9 views
0 votes
0 answers
9
Show that the Fibonacci numbers satisfy the recurrence relation $f_{n} = 5f_{n−4} + 3f_{n−5} \:\text{for}\: n = 5, 6, 7,\dots,$ together with the initial conditions $f_{0} = 0, f_{1} = 1, f_{2} = 1, f_{3} = 2, \:\text{and}\: f4 = 3.$ Use this recurrence relation to show that $f_{5n}$ is divisible by $5$, for $n = 1, 2, 3,\dots .$
asked May 2 in Combinatory Lakshman Patel RJIT 7 views
0 votes
0 answers
10
Find a recurrence relation for the number of ways to lay out a walkway with slate tiles if the tiles are red, green, or gray, so that no two red tiles are adjacent and tiles of the same color are considered indistinguishable. What are the initial conditions for the recurrence relation in part $(A)?$ How many ways are there to lay out a path of seven tiles as described in part $(A)?$
asked May 2 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
11
Find a recurrence relation for the number of ways to completely cover a $2 \times n$ checkerboard with $1 \times 2$ dominoes. [Hint: Consider separately the coverings where the position in the top right corner of the checkerboard is covered by a domino positioned horizontally and ... part $(A)?$ How many ways are there to completely cover a $2 \times 17$ checkerboard with $1 \times 2$ dominoes?
asked May 2 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
14
Find the recurrence relation satisfied by $S_{n},$ where $S_{n}$ is the number of regions into which three-dimensional space is divided by $n$ planes if every three of the planes meet in one point, but no four of the planes go through the same point. Find $S_{n}$ using iteration.
asked May 2 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
15
a) Find the recurrence relation satisfied by $R_{n},$ where $R_{n}$ is the number of regions into which the surface of a sphere is divided by $n$ great circles (which are the intersections of the sphere and planes passing through the center of the sphere), if no three of the great circles go through the same point. b) Find $R_{n}$ using iteration.
asked May 2 in Combinatory Lakshman Patel RJIT 11 views
0 votes
1 answer
16
Find the recurrence relation satisfied by $R_{n},$ where $R_{n}$ is the number of regions that a plane is divided into by $n$ lines, if no two of the lines are parallel and no three of the lines go through the same point. Find $R_{n}$ using iteration.
asked May 2 in Combinatory Lakshman Patel RJIT 15 views
0 votes
0 answers
17
A bus driver pays all tolls, using only nickels and dimes, by throwing one coin at a time into the mechanical toll collector. Find a recurrence relation for the number of different ways the bus driver can pay a toll of $n$ cents (where the order in which the coins are used matters). In how many different ways can the driver pay a toll of $45$ cents?
asked May 2 in Combinatory Lakshman Patel RJIT 9 views
0 votes
0 answers
18
Messages are transmitted over a communications channel using two signals. The transmittal of one signal requires $1$ microsecond, and the transmittal of the other signal requires $2$ microseconds. Find a recurrence relation for the number of different messages consisting of ... . What are the initial conditions? How many different messages can be sent in $10$ microseconds using these two signals?
asked May 2 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
19
Find a recurrence relation for the number of ternary strings of length $n$ that contain two consecutive symbols that are the same. What are the initial conditions? How many ternary strings of length six contain consecutive symbols that are the same?
asked May 2 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
20
Find a recurrence relation for the number of ternary strings of length $n$ that do not contain consecutive symbols that are the same. What are the initial conditions? How many ternary strings of length six do not contain consecutive symbols that are the same?
asked May 2 in Combinatory Lakshman Patel RJIT 6 views
0 votes
0 answers
21
Find a recurrence relation for the number of ternary strings of length $n$ that contain either two consecutive $0s$ or two consecutive $1s.$ What are the initial conditions? How many ternary strings of length six contain two consecutive $0s$ or two consecutive $1s?$
asked May 2 in Combinatory Lakshman Patel RJIT 11 views
0 votes
0 answers
22
Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive $0s$ or two consecutive $1s.$ What are the initial conditions? How many ternary strings of length six do not contain two consecutive $0s$ or two consecutive $1s?$
asked May 2 in Combinatory Lakshman Patel RJIT 11 views
0 votes
0 answers
23
Find a recurrence relation for the number of ternary strings of length n that contain two consecutive $0s.$ What are the initial conditions? How many ternary strings of length six contain two consecutive $0s?$
asked May 2 in Combinatory Lakshman Patel RJIT 10 views
0 votes
0 answers
24
A string that contains only $0s, 1s,$ and $2s$ is called a ternary string. Find a recurrence relation for the number of ternary strings of length $n$ that do not contain two consecutive $0s.$ What are the initial conditions? How many ternary strings of length six do not contain two consecutive $0s?$
asked May 2 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
25
Find a recurrence relation for the number of ways to climb $n$ stairs if the person climbing the stairs can take one, two, or three stairs at a time. What are the initial conditions? In many ways can this person climb a flight of eight stairs?
asked May 2 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
26
Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one stair or two stairs at a time. What are the initial conditions? In how many ways can this person climb a flight of eight stairs?
asked May 2 in Combinatory Lakshman Patel RJIT 9 views
1 vote
1 answer
27
Find a recurrence relation for the number of bit strings of length $n$ that contain the string $01$. What are the initial conditions? How many bit strings of length seven contain the string $01?$
asked May 1 in Combinatory Lakshman Patel RJIT 25 views
0 votes
0 answers
28
Find a recurrence relation for the number of bit strings of length n that do not contain three consecutive $0s.$ What are the initial conditions? How many bit strings of length seven do not contain three consecutive $0s?$
asked May 1 in Combinatory Lakshman Patel RJIT 12 views
0 votes
0 answers
29
Find a recurrence relation for the number of bit strings of length $n$ that contain three consecutive $0s.$ What are the initial conditions? How many bit strings of length seven contain three consecutive $0s?$
asked May 1 in Combinatory Lakshman Patel RJIT 8 views
0 votes
0 answers
30
Find a recurrence relation for the number of bit strings of length $n$ that contain a pair of consecutive $0s$. What are the initial conditions? How many bit strings of length seven contain two consecutive $0s?$
asked May 1 in Combinatory Lakshman Patel RJIT 10 views
...