Is there a way to do this without brute force ?

[Jamin2112]

Is there a way to do this without "brute force"?

Homework Statement

A number is chosen at random from among all 5-digit numbers containing exactly one of each of the digits 1, 2, 3, 4, 5. Find the probability that no two adjacent digits in the number are consecutive integers?

Homework Equations

n choose k
n factorial

The Attempt at a Solution

So I know there are 5!=120 different combos. I need to figure out how many have the property that there are no two adjacent consecutive numbers (i.e. 13524 would work but 12534 wouldn't). Should I break it off into cases where 1 is the first digit, 2 is the second, etc.? That would be a brute force approach. Is there an easier way to think about this?

 

[tiny-tim]

Hi Jamin2112!

Hint: call the first digit "a" …

what is the probability that the second digit is not adjacent ?

 

[Jamin2112]

Hi Jamin2112!

Hint: call the first digit "a" …

what is the probability that the second digit is not adjacent ?

Depends. If a is 1 or 5, then the probability is 3/4. If a is 2, 3, or 4, then the probability is 1/2.

 

[I like Serena]

I'd suggest a "smart" brute force approach.
There are not that many combinations allowed but too many exceptions to easily generalize.
With "smart" I mean for instance that after you've done the numbers starting with 1, you already know that there are just as many numbers starting with 5.

 

[Dick]

I'd suggest a "smart" brute force approach.
There are not that many combinations allowed but too many exceptions to easily generalize.
With "smart" I mean for instance that after you've done the numbers starting with 1, you already know that there are just as many numbers starting with 5.

Unfortunately that's not true. There are fewer arrangements starting with 1 than with 5.

I would suggest starting with the N=3 case. So the digits are 1,2,3. Call F(N) the number of allowed sequences. Then F(3) is easy. It's just 3, [1,3,2], [2,1,3] and [3,1,2]. Let's also call F(N,k) the number of sequences of N digits starting with digit k. Now try to count the N=4 case. If the first digit is 1, then the rest are 2,3,4. Those are sequential so you can arrange them in F(3)=3 ways, but you can't allow the one starting with 2 so there are 2. So F(4,1)=2. So that's F(3)-1. But if you start with 4 then any arrangement of 1,2,3 is allowed after that. So F(4,4)=F(3)=3. Now if you can count F(4,2) and F(4,3) then you've wrapped up F(4).

Think inductively.

 

[I like Serena]

Unfortunately that's not true. There are fewer arrangements starting with 1 than with 5.

Huh?

I was wondering whether the digits had to be ascending or not.
But that was clarified indirectly in post #3.

 

[Dick]

Huh?

I was wondering whether the digits had to be ascending or not.
But that was clarified indirectly in post #3.

I was assuming you just have to avoid sequential pairs. Work it out. I spelled the difference out for the N=4 case.

 

[Bacle2]

How about inclusion/exclusion? first with consecutive pairs, then with triples,

etc.

Still, sorry to tell you, Jamin, you cannot get any arrangement with the numbers

in your name (Sorry, I'm too tired for a quality joke)

 

[Dick]

How about inclusion/exclusion? first with consecutive pairs, then with triples,

etc.

Still, sorry to tell you, Jamin, you cannot get any arrangement with the numbers

in your name (Sorry, I'm too tired for a quality joke)

Yeah, joke's little poor. Did you manage to work it out that way? I do know that the number of admissible orderings depends on the starting number. If it's 1 then it's less than all of the other possibilities. It's not that symmetric. The rest of the leading digits have the same number of orderings. That is a little counterintuitive. And you can figure out those numbers from the N-1 case. This seems a little elaborate. If you've got a simpler way I'd love to hear about it.

 

[haruspex]

I was assuming you just have to avoid sequential pairs. Work it out. I spelled the difference out for the N=4 case.

The way I read the question, 54... is not allowed, so number starting with 5 equals number starting with 1. Likewise 2 and 4.
Not sure if inclusion/exclusion is quicker, but I think you can be more confident of getting it right that way. Maybe do both.

 

[Dick]

The way I read the question, 54... is not allowed, so number starting with 5 equals number starting with 1. Likewise 2 and 4.
Not sure if inclusion/exclusion is quicker, but I think you can be more confident of getting it right that way. Maybe do both.

Oh, heck. I was so obsessed with what I doing I failed to read it correctly. It's "adjacent", not "sequential". If anybody wants the solution to a different harder problem. I've got it. Sorry all! In that case the number of orderings is small enough you can simply write them all out. That make "brute force" not that hard.

 

[Jamin2112]

"Brute force" gave me an answer of 7/60. That correct?

 

[Bacle2]

You're right; you have only 120 possible arrangements to make it worthwhile , but

it may be worthwhile for a general solution to the same problem for {1,2,...,n}.

Sorry, I will be gone for a while now.

 

[Dick]

"Brute force" gave me an answer of 7/60. That correct?

Yeah, there's only 14 orderings. If you misread it like I did (so "45" is disallowed but "54" is allowed) then the are 53. Which is getting large enough to make "by hand" counting a little iffy, at least if I'm the one doing it.

 

[Jamin2112]

Yeah, there's only 14 orderings. If you misread it like I did (so "45" is disallowed but "54" is allowed) then the are 53. Which is getting large enough to make "by hand" counting a little iffy, at least if I'm the one doing it.

I read it the way where the only possibilities would be

13524
14253
24513
24135
25314
31524
31425
35124
35241
41352
42513
42531
53142
52413,

which is 14 out the possible 120.

 

[Dick]

I read it the way where the only possibilities would be

13524
14253
24513
24135
25314
31524
31425
35124
35241
41352
42513
42531
53142
52413,

which is 14 out the possible 120.

I agree.

 

[Bacle2]

O.K, I have this idea that may be simpler than brute force:

We set up a graph G with vertices 1 thru n , and we draw an edge between

i,j iff. |i-j|>1 . Then we do the adjacency matrix M_G for G, i.e., the (i,j)-entry is

1 iff. there is an edge joining i with j, and is 0 otherwise.

I first tried to use the fact that the (i,j)-entry of (M_G)^n is the number of paths of

length n between vertex i and vertex j , BUT , the problem is that some of these paths

may contain a cycle, i.e., some numbers are repeated, e.g., for n=5, 1,3,5,1,3,5 is a path

of length 5 in the graph G for {1,2,..,5}. So what I now think is the

answer is counting the number of spanning trees in the graph. There is a method for this,

but I don't have much time now to try it, but I'll try it later.

 

[awkward]

See http://oeis.org/search?q=a002464&language=english&go=Search

(OEIS A002464)