in Combinatory retagged by
4,826 views
5 votes
5 votes

How many 4-permutations of the positive integers not exceeding 100 contain three consecutive integers k, k + 1, k + 2, in the correct order

a) where these consecutive integers can perhaps be separated by other integers in the permutation?

b) where they are in consecutive positions in the permutation?

in Combinatory retagged by
4.8k views

1 comment

@Vivek sharma @Arjun @anuragpandyan in part a,he has asked 4-permutation and we choose k,k+1,k+2 and other number from 97 choices and not to not mentioned on relative ordering btw consecutive numbers should be mainted,so i felt 4! must be used instead of 4 in"98*4*97" to be replaced with "98*4!*97"

0
0

1 Answer

10 votes
10 votes
Best answer
a) In this part the permutation 5,6,32,7, for example, is to be counted. since it contains the consecutive
numbers 5, 6, and 7 in their correct order (even though separated by the 32). In order to specify such a
4-permutation, we first need to choose the 3 consecutive integers. They can be anything from {I, 2, 3} to
{98, 99, 100}; thus there are 98 possibilities. Next we need to decide which slot is to contain a number not
in this set; there are 4 possibilities. Finally, we need to decide which of the 97 other positive integers not
exceeding 100 is to fill this slot, and there are of course 97 choices. Thus our first attempt at an answer gives
us, by the product rule, 98· 4 . 97.
Unfortunately, this answer is not correct, because we have counted some 4-permutations more than once.
Consider the 4-permutation 4. 5. 6. 7, for example. We cannot tell whether it arose from choosing 4, 5, and 6
as the consecutive numbers, or from choosing 5, 6, and 7. (These are the only two ways it could have arisen.)
In fact, every 4-permutation consisting of 4 consecutive numbers. in order, has been double counted. Therefore
to correct our count, we need to subtract the number of such 4-permutations. Clearly there are 97 of them
(they can begin with any number from 1 to 97). Further thought shows that every other 4-permutation in our
collection arises in a unique way (in other words, there is a unique subsequence of three consecutive integers).
Thus our final answer is 98·4·97 - 97 = 37.927.
b) In this part we are insisting that the consecutive numbers be consecutive in the 4-permutation as well.
The analysis in part (a) works here, except that there are only 2 places to put the fourth number-in slot 1
or in slot 4. Therefore the answer is 98·2·97 - 97 = 18,915.
selected by

4 Comments

What is the logic of "double counted" here?
0
0

Every 4-permutation consisting of 4 consecutive numbers. in order, has been double counted.


Examples of 4-permutations consisting of 4 consecutive numbers. in order:

{1, 2, 3, 4}, {2, 3, 4, 5}, {3, 4, 5, 6}, {4, 5, 6, 7}, .... , {97, 98, 99, 100}.


How they have been double counted?

suppose a 4 permutation {2, 3, 4, 5}

Once we counted it while counting all the permutations of type {2, 3, 4, x} where x can be any element of the set {1, 5, 6, 7, ... ,99 , 100}, when x = 5,

Second time we counted it while counting all the permutations of type {y, 3, 4, 5} where y can be any element of the set {1, 2, 6, ... ,99 , 100},when y = 2.

Thus we counted {2, 3, 4, 5} twice(although in different manners).

Similarly for each of the 97, four permutations consisting of 4 consecutive numbers.

1
1
Bro you just copied ans from kenneth rosen….
0
0
lol
0
0
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true