FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » Combinatorics
number of functions
Post new topic   Reply to topic Page 1 of 1 [9 Posts] View previous topic :: View next topic
Author Message
crooks_dwayne@yahoo.com
science forum beginner


Joined: 19 Oct 2005
Posts: 4

PostPosted: Sun Oct 23, 2005 2:56 am    Post subject: Re: number of functions Reply with quote

Thank you very much for all the helpful information.
Back to top
Matthew Roozee
science forum beginner


Joined: 22 Oct 2005
Posts: 7

PostPosted: Sat Oct 22, 2005 10:58 pm    Post subject: Re: number of functions Reply with quote

crooks_dwayne@yahoo.com wrote:
Quote:
Here's my solution: (plz tell me if this reasoning is flawed in any
way)

Now,
f(1) + f(2) + ... + f(1999) = a*2000 + b*2001 + c*2002 + d*2003
...(1)
and
a + b + c + d = 1999
...(2)

where a,b,c,d are non-negative integers representing the number of
times the
function maps to 2000,2001,2002 and 2003 respectively.

Also, the following constraints are realized if (1) must have an odd
sum:
- the terms a*2000 and c*2002 are always even regardless a or c is even
or odd
- the terms b*2001 and d*2003 is even when b, d is even and odd when b,
d is odd

Hence the only way (1) can be odd is if we have:
Case 1: even + odd + even + even = odd
or
Case 2: even + even + odd + even = odd

I think you mean Case 2: even + even + even + odd = odd

Quote:
Case 1: corresponds to the following,

- a is even or odd, b is odd, c is even or odd and d is even

If a is even and c is even then in (2) we have
2p + (2q+1) + 2r + 2s = 1999 where p,q,r,s >= 0
i.e. p + q + r + s = 999

The no. of solutions is C(999+4-1,4-1) = C(1002,3)

If a is odd and c is odd then in (2) we have

(2p+1) + (2q+1) + (2r+1) + 2s = 1999 where p,q,r,s >= 0
i.e. p + q + r + s = 998

The no. of solutions is C(998+4-1,4-1) = C(1001,3)

This is where the real problem lies. What you have written describes
dropping identical balls into numbered boxes... you are treating any two
mappings to the same value as equivalent. That is, a function
f(1)=2000, f(2)=2001 is considered the same as f(1)=2001, f(2)=2000 by
your method. The problem as stated requires numbered balls dropped into
numbered boxes to use this approach.

Quote:
The other two possibilities, namely:
- if a is even and c is odd or
- if a is odd and c is even
are not possible given the constraints and hence they give no solutions

Hence in case 1 we get C(1002,3)+C(1001,3) solutions.

Since case 2 is symmetric to case 1 we get the same no. of solutions.

Hence the total no. of solutions is N = 2*(C(1002,3)+C(1001,3))
which is equal to the total number of solutions to the original
problems.

Note: A different assignment to the values a,b,c,d means a different
function is being used and since the two problems are in a 1-1
correspondence with each other i believe my approach gives the right
answer. Plz correct me if I'm wrong.

- Matt
Back to top
crooks_dwayne@yahoo.com
science forum beginner


Joined: 19 Oct 2005
Posts: 4

PostPosted: Sat Oct 22, 2005 4:11 pm    Post subject: Re: number of functions Reply with quote

Here's my solution: (plz tell me if this reasoning is flawed in any
way)

Now,
f(1) + f(2) + ... + f(1999) = a*2000 + b*2001 + c*2002 + d*2003
....(1)
and
a + b + c + d = 1999
....(2)

where a,b,c,d are non-negative integers representing the number of
times the
function maps to 2000,2001,2002 and 2003 respectively.

Also, the following constraints are realized if (1) must have an odd
sum:
- the terms a*2000 and c*2002 are always even regardless a or c is even
or odd
- the terms b*2001 and d*2003 is even when b, d is even and odd when b,
d is odd

Hence the only way (1) can be odd is if we have:
Case 1: even + odd + even + even = odd
or
Case 2: even + even + odd + even = odd

Case 1: corresponds to the following,

- a is even or odd, b is odd, c is even or odd and d is even

If a is even and c is even then in (2) we have
2p + (2q+1) + 2r + 2s = 1999 where p,q,r,s >= 0
i.e. p + q + r + s = 999

The no. of solutions is C(999+4-1,4-1) = C(1002,3)

If a is odd and c is odd then in (2) we have

(2p+1) + (2q+1) + (2r+1) + 2s = 1999 where p,q,r,s >= 0
i.e. p + q + r + s = 998

The no. of solutions is C(998+4-1,4-1) = C(1001,3)

The other two possibilities, namely:
- if a is even and c is odd or
- if a is odd and c is even
are not possible given the constraints and hence they give no solutions

Hence in case 1 we get C(1002,3)+C(1001,3) solutions.

Since case 2 is symmetric to case 1 we get the same no. of solutions.

Hence the total no. of solutions is N = 2*(C(1002,3)+C(1001,3))
which is equal to the total number of solutions to the original
problems.

Note: A different assignment to the values a,b,c,d means a different
function is being used and since the two problems are in a 1-1
correspondence with each other i believe my approach gives the right
answer. Plz correct me if I'm wrong.
Back to top
Matthew Roozee
science forum beginner


Joined: 22 Oct 2005
Posts: 7

PostPosted: Sat Oct 22, 2005 7:41 am    Post subject: Re: number of functions Reply with quote

The case of 5 target values is a harder problem...

Let S = {2000,2001,2002,2003,2004}
Let A(n) be defined as the number of functions from {1,2,...n} --> S
whose sum is odd and let B(n) be defined as the number of functions from
{1,2,...,n} --> S whose sum is even.

Then
A(n) = 3*A(n-1) + 2*B(n-1)
B(n) = 2*A(n-1) + 3*B(n-1)
with initial conditions A(1) = 2, B(1) = 3

Re-writing the first equation gives:
B(n-1) = [A(n) - 3*A(n-1)]/2 and
B(n) = [A(n+1) - 3*A(n)]/2

Substituting into the second equation and multiplying by 2 gives:
A(n+1) - 3*A(n) = 3*A(n) - 9*A(n-1) + 4*A(n-1) or
A(n+1) = 6*A(n) - 5*A(n-1)

The characteristic equation for A has roots r1 = 1 and r2 = 5.

Thus A(n) = c1 + c2*(5^n)

A(0) = 0 = c1 + c2
A(1) = 2 = c1 + c2*(5)

or c1 = -1/2 and c2 = +1/2

and A(n) = (5^n - 1)/2

so A(1999) = (5^1999-1)/2

- Matt

Proginoskes wrote:
Quote:
crooks_dwayne@yahoo.com wrote:

The problem:
Determine the number of functions
f:{1,2,...,1999}->{2000,2001,2002,2003} satisfying the condition that
f(1)+f(2)+...+f(1999) is odd.

The book i got this problem from has no solution for it. I think i have
solved it and would just like to get my answer verified. If someone can
try to solve and post there answer I would gladly post my results also.


I get 4^1998 * 2 for an answer.

The number of functions from
f:{1,2,...,1999} -> {2000,2001,2002,2003,2004} where
f(1)+f(2)+...+f(1999) is odd is a MUCH harder problem.

--- Christopher Heckman
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Sat Oct 22, 2005 7:40 am    Post subject: Re: number of functions Reply with quote

crooks_dwayne@yahoo.com wrote:
Quote:
Can you plz expand on your result and tell me how you got it because I
got something totally different.

Here's my ans: 2*[C(1002,3) + C(1001,3)]

My solution is kinda long so only if you insist I would put up my
solution.

Here's the problem:

crooks_dwa...@yahoo.com wrote:
Quote:
The problem:
Determine the number of functions
f:{1,2,...,1999}->{2000,2001,2002,2003} satisfying the condition that
f(1)+f(2)+...+f(1999) is odd.

The book i got this problem from has no solution for it. I think i have
solved it and would just like to get my answer verified. If someone can
try to solve and post there answer I would gladly post my results also.

You can choose f(1), f(2), ..., f(1998) to be any of 2000, 2001, 2002,
2003. Now, there are only two ways to choose f(1999) to make the sum
even (and two to make it odd), no matter how f(1), f(2), ..., f(1998)
are chosen. For instance, if
f(1) + f(2) + ... + f(1998) is even, then f(1999) must be 2001 or 2003.

So the total number of functions is 4^1998 * 2.

Now my other comment should be clear; if we replace
{2000,2001,2002,2003} with {2000,2001,2002,2003,2004}, the problem
becomes MUCH harder; if you try the procedure above, then you may have
2 or 3 choices for f(1999), so you just can't multiply a bunch of 5's
times a number k.

--- Christopher Heckman
Back to top
Matthew Roozee
science forum beginner


Joined: 22 Oct 2005
Posts: 7

PostPosted: Sat Oct 22, 2005 7:17 am    Post subject: Re: number of functions Reply with quote

I looked at this as follows:

Think of f as mapping to a two dimensional set ({E,O},{L,H}).
Here, E = Even, O = Odd, L = Low, and H = High.
Thus the four values are:
(E,L)=2000 (E,H)=2002 (O,L)=2001 (O,H)=2003

So if we think of f = (f1, f2) where f1: 1...1999 --> E,O and f2:
1...1999 --> O,H we can just multiply the number of each type of function.

There are 2^1999 possible choices for f1.
For f2 to satisfy that our sum is odd, f2 must map an odd number of
values to O. How many ways can f2 do this? There are a total of 2^1999
possible choices for f2. The total number of functions that have x odd
targets and 1999-x even targets is the same as the total number of
functions that have x even targets and 1999-x odd targets. That is,
half of our 2^1999 possible functions will satisfy our odd sum
requirement for f2.

Multiplying together, we get (2^1999)(2^1998)=(2^3997)

- Matt

crooks_dwayne@yahoo.com wrote:
Quote:
The problem:
Determine the number of functions
f:{1,2,...,1999}->{2000,2001,2002,2003} satisfying the condition that
f(1)+f(2)+...+f(1999) is odd.

The book i got this problem from has no solution for it. I think i have
solved it and would just like to get my answer verified. If someone can
try to solve and post there answer I would gladly post my results also.

Thanx:
Back to top
crooks_dwayne@yahoo.com
science forum beginner


Joined: 19 Oct 2005
Posts: 4

PostPosted: Thu Oct 20, 2005 11:52 pm    Post subject: Re: number of functions Reply with quote

Can you plz expand on your result and tell me how you got it because I
got something totally different.

Here's my ans: 2*[C(1002,3) + C(1001,3)]

My solution is kinda long so only if you insist I would put up my
solution.
Back to top
Proginoskes
science forum Guru


Joined: 29 Apr 2005
Posts: 2593

PostPosted: Thu Oct 20, 2005 11:01 am    Post subject: Re: number of functions Reply with quote

crooks_dwayne@yahoo.com wrote:
Quote:
The problem:
Determine the number of functions
f:{1,2,...,1999}->{2000,2001,2002,2003} satisfying the condition that
f(1)+f(2)+...+f(1999) is odd.

The book i got this problem from has no solution for it. I think i have
solved it and would just like to get my answer verified. If someone can
try to solve and post there answer I would gladly post my results also.

I get 4^1998 * 2 for an answer.

The number of functions from
f:{1,2,...,1999} -> {2000,2001,2002,2003,2004} where
f(1)+f(2)+...+f(1999) is odd is a MUCH harder problem.

--- Christopher Heckman
Back to top
crooks_dwayne@yahoo.com
science forum beginner


Joined: 19 Oct 2005
Posts: 4

PostPosted: Wed Oct 19, 2005 8:17 pm    Post subject: number of functions Reply with quote

The problem:
Determine the number of functions
f:{1,2,...,1999}->{2000,2001,2002,2003} satisfying the condition that
f(1)+f(2)+...+f(1999) is odd.

The book i got this problem from has no solution for it. I think i have
solved it and would just like to get my answer verified. If someone can
try to solve and post there answer I would gladly post my results also.

Thanx:>
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [9 Posts] View previous topic :: View next topic
The time now is Fri Oct 20, 2017 7:05 am | All times are GMT
Forum index » Science and Technology » Math » Combinatorics
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts how to deduce a number validation algorithm? Tim_Mac Math 1 Fri Jul 21, 2006 10:43 am
No new posts Generating function for Mathieu functions cosmicstring@gmail.com Math 1 Fri Jul 21, 2006 8:39 am
No new posts a subset of natural number levine121323@yahoo.com Math 1 Fri Jul 21, 2006 6:17 am
No new posts Entire functions, polynomial bounds david petry Math 2 Thu Jul 20, 2006 11:09 pm
No new posts Another look at triangle number factoring. Dan11 Math 2 Tue Jul 18, 2006 7:05 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0277s ][ Queries: 20 (0.0046s) ][ GZIP on - Debug on ]