Number of combinations

dairymilk · 2011-05-19 03:37:37

Hi everyone , so I have this problem.

I have a 10 digit number ZTABCDEFGH (each letter represents a digit 1 to 9, or 0).

Now, what information is given about this number is that

5 of the digits have to be an odd numbers/digits, the other five - even numbers,
Z, T cannot be 0 (zero),
Z cannot be equal to T,
A, C, E, G cannot be 5, 6, 7, 8, 9, 0

pairs AB, CD, EF, GH cannot be equal (eg. if CD is 12, EF or any other pair mentioned cannot be 12).

What I need to find is the number of different combinations/permutations possible

Any help is appreciated

bobbym · 2011-05-19 03:49:44

Hi;

5 of the digits have to be an odd numbers/digits, the other five - even numbers,

This condition bothers me. If each letter had to be a different number then this condition would apply automatically. Are you saying then that 2 different letters can represent the same number?

dairymilk · 2011-05-19 04:01:53

Yes, that is correct, except for Z and T (Z ≠ T ≠ 0) and AB ≠ CD ≠ EF ≠ GH.

bobbym · 2011-05-19 04:10:04

Hi dairymilk;

So it I understand C and D could both be 2?

What kind of answer are you looking for? Just a number or ?

dairymilk · 2011-05-19 04:16:17

Yes, thats right. I would like to know the number of combinations possible (and a formula to find that number). Thanks

bobbym · 2011-05-19 04:17:56

Hi dairymilk;

Where does the problem come from. A book? If so may I have the title and author please?

dairymilk · 2011-05-19 04:35:02

I've been given a programing assignment to find every such number by my teacher, not sure where he got it from, he might have just made it up

And apart from generating vast amounts of numbers and then checking them for given parameters I am having troule finding a way to do it.

John E. Franklin · 2011-05-19 05:15:35

What programming language are you learning in this course?
When is the answer due, just wondering?

gAr · 2011-05-20 00:23:14

Hi dairymilk,

Did your teacher really ask you to find every such number?
That would be huge.

I tried to find an analytical solution, but it was so confusing!

But trying a code directly would take a long time considering all the loops.
We observe that Z and T can be filled in 9*8 = 72 ways. (Z,T different and non-zero)
And obviously, they are one odd and one even.

The problem now reduces to finding ABCDEFGH, using the given conditions. They must be 4 odd and 4 even.

Here is a python snippet:

count=0
odd=0
for a in range(1,5):
   for b in range(10):
       for c in range(1,5):
           for d in range(10):
               for e in range(1,5):
                   for f in range(10):
                       for g in range(1,5):
                           for h in range(10):
                               odd=0
                               if a%2 == 1:
                                   odd+=1
                               if b%2 == 1:
                                   odd+=1
                               if c%2 == 1:
                                   odd+=1
                               if d%2 == 1:
                                   odd+=1
                               if e%2 == 1:
                                   odd+=1
                               if f%2 == 1:
                                   odd+=1
                               if g%2 == 1:
                                   odd+=1
                               if h%2 == 1:
                                   odd+=1
                               if odd == 4:
                                   if not(10*a+b == 10*c+d or 10*a+b == 10*e+f or 10*a+b == 10*g+h or 10*c+d == 10*e+f or 10*c+d == 10*g+h or 10*e+f == 10*g+h):
                                       count+=1

The value for count is 620880
Hence, total number of combination of digits = 72*620880 = 44703360 ways.

Can anybody verify it?

bobbym · 2011-05-20 00:51:19

Hi gAr;

I am working on this too. I had a little bit of difficulty getting any analytical answer. I am programming it also but am not done yet.

gAr · 2011-05-20 00:58:16

Hi bobbym,

Okay, thanks.

bobbym · 2011-05-22 04:08:36

Hi gAr;

Sorry for the big delay but I just got caught up.

I am getting 28 084 800. I did it like this. The ZT we do using combinatorics.

ZT = ( 9 * 8 ) = 72 ways.

1) When Z and T are both even: There are 12 * 489600 = 5 875 200 ways.

2) When Z and T are one odd and one even: There are 20 * 620 880 = 12 417 600 ways.

3) When Z and T are both odd: There are 20 * 489 600 = 9 792 000 ways.

5 875 200 + 12 417 600 + 9 792 000 = 28 084 800 ways

gAr · 2011-05-22 04:38:21

Hi bobbym,

Thanks!
I hastily concluded that first 2 are always 1 odd and 1 even without thinking twice, silly me!

Anyway, you may need to add another 20*620880 (Z odd, T even or Z even, T odd)

Hence, the total = 40502400

Last edited by gAr (2011-05-22 04:48:43)

bobbym · 2011-05-22 06:07:08

Hi;

Hence, the total = 40502400

Talk about silly! How come I did not see that 20 + 20 + 12 ≠ 72. Yes, that is the correct and
final answer. The first time I ran the program I got that answer. When I refined the idea I just thought that I had
overcounted.

gAr · 2011-05-22 14:43:48

Hi bobbym,

Okay!
You used functional programming?
I don't know whether I can make my code run faster, other than moving to a compiled language.

bobbym · 2011-05-22 22:09:15

Hi gAr;

Yes, I did. That was the problem, I am not very familiar with how to manage memory
so I kept running out. This slowed the program to a crawl. C++ is the only way to go
for lots of loops but I wanted to try someing else.

gAr · 2011-05-22 22:49:12

Hi bobbym,

Okay, just now I tried the same implementation in C,
The python program took about 8.5 seconds to execute in my system,
The same in C took only 0.087 seconds!
I didn't expect that much difference.

bobbym · 2011-05-22 22:54:11

Hi gAr;

C is very fast. It is a compiled. Speedups are usually between 100 to 1000 times faster than interpreted code. The only thing faster is assembly language.

gAr · 2011-05-22 23:06:45

Yes, but I thought that since the instructions are repeated here, the interpreted code would be cached, and that the difference may not be that much.
I expected it to be a little faster than 10x.

bobbym · 2011-05-22 23:25:22

Hi gAr;

Actually, python did quite well. What is really needed is a math solution to the entire problem.

gAr · 2011-05-22 23:34:05

Hi bobbym,

I think there is no other way than doing it by cases.
I haven't found a math solution yet.

bobbym · 2011-05-22 23:42:08

I know it is tough. I do not have any generating function or recurrence that works.

gAr · 2011-05-22 23:49:51

The OP has mentioned it's a programming assignment, so probably it wasn't meant to be solved mathematically.
This may be a problem which we need to count by counting!

bobbym · 2011-05-22 23:59:57

Yes, but if you do not handle ZT by combinatorics you will have a programming problem of about 160 000 000 iterations.

Supposing in my thread E poses this problem and adds on a few letters then this problem is going to be very, very hard.

gAr · 2011-05-23 00:07:43

Yes, and I despise problems with so many restrictions!

Math Is Fun Forum

#1 2011-05-19 03:37:37

Number of combinations

#2 2011-05-19 03:49:44

Re: Number of combinations

#3 2011-05-19 04:01:53

Re: Number of combinations

#4 2011-05-19 04:10:04

Re: Number of combinations

#5 2011-05-19 04:16:17

Re: Number of combinations

#6 2011-05-19 04:17:56

Re: Number of combinations

#7 2011-05-19 04:35:02

Re: Number of combinations

#8 2011-05-19 05:15:35

Re: Number of combinations

#9 2011-05-20 00:23:14

Re: Number of combinations

#10 2011-05-20 00:51:19

Re: Number of combinations

#11 2011-05-20 00:58:16

Re: Number of combinations

#12 2011-05-22 04:08:36

Re: Number of combinations

#13 2011-05-22 04:38:21

Re: Number of combinations

#14 2011-05-22 06:07:08

Re: Number of combinations

#15 2011-05-22 14:43:48

Re: Number of combinations

#16 2011-05-22 22:09:15

Re: Number of combinations

#17 2011-05-22 22:49:12

Re: Number of combinations

#18 2011-05-22 22:54:11

Re: Number of combinations

#19 2011-05-22 23:06:45

Re: Number of combinations

#20 2011-05-22 23:25:22

Re: Number of combinations

#21 2011-05-22 23:34:05

Re: Number of combinations

#22 2011-05-22 23:42:08

Re: Number of combinations

#23 2011-05-22 23:49:51

Re: Number of combinations

#24 2011-05-22 23:59:57

Re: Number of combinations

#25 2011-05-23 00:07:43

Re: Number of combinations

Board footer