Deriving a Function

[dvjustus]

Trying to come up with a function that fits

 

(0,0)

(1,1)

(2,3)

(3,7)

(4,15)

(5,31)

(6,63)...

 

If not too much trouble, help please. Thanks.

[dvjustus]

Sorry to bother. I got it...

 

f(x) = 2^x - 1

[bloodhound]

you haven't defined your source and target for the function.

 

there are infinite numbers of functions [math]f \colon \mathbb{R} \to \mathbb{R}[/math] passing through those points.

[dvjustus]

Hi bloodhound,

 

Not sure what you mean, but the domain is [0,∞), and the pattern doesn't deviate from the given function.

[dvjustus]

I don't know if this would help, but I could show where the correlations are coming from. It has to do with possible arrangements, without repeating arrangements containing the same set of units (e.g., 01 and 10 can't be repeated). If there are 0 units, there are 0 arrangements. If there is 1 unit, 1 arrangement...

 

2 units: 0 1

0

1

01

---

3 arrangements

 

3 units: 0 1 2

0

1

2

01

02

12

012

----

7 arrangements

 

and so on...

[bloodhound]

well if u take the domain to be just the non negative integers, then f(x)=2^x-1 is probably the only function passing through those points.

 

if u take the domain to be R, then you define the function to be f(x)=2^x -1 if x=0,1,2,3,...

 

and then you can let the function do anything in between the points.

 

for example f(x)=0 for [math]x \in \mathbb{R}-\{0,1,2,3,...\}[/math]

 

but in ur case it looks the domain is [math]\mathbb{N}[/math]

[bloodhound]

an alternative formula would be

 

if you have n objects,

 

then [math]f(n)=\sum_{i=1}^{n} \binom{n}{i}[/math]

 

will give u the number of arrangements as described in your previous post.

 

you can work the 2^n -1 answer from scracth. its basically to do with two choices for each object in the collection. so you either include x, or don't. so for n objects you have the term 2^n -1 possible outcomes. i cannot seem to remember where the -1 comes in . i think its due to that fact that once you get to the nth item , you cannot choose to not include it (as if u choose not to include everything , you get the empty set)

[dvjustus]

Thanks for the explanations and alternatives, bloodhound. Unfortunately I don't yet understand the symbols you are using. But I appreciate it nonetheless.

[matt grime]

I think the point is that you've not given sufficient information to uniquely determine the function. You need to state what the input set of values is.

The function f(x) = 2^x - 1 + sin(2xpi) also satisfies the constraints yo'uve given, amongst infintely many others.

[bloodhound]

i sorted it out.

 

here [math]\binom{n}{i}=\frac{n!}{i!(n-i)!}[/math]

 

and then u sum that from i = 1 to n

 

example. n = 3

 

so [math]f(3)=\sum_{i=1}^{3} \binom{3}{i}[/math]

[math]=\binom{3}{1} + \binom{3}{2} + \binom {3}{3}[/math]

[math]=\frac{3!}{1!2!} + \frac{3!}{2!1!} + \frac{3!}{3!0!}[/math]

[math]=3+3+1[/math]

[math]=7[/math]

 

here [math]n!=n(n-1)(n-2)...(2)(1)[/math] and [math]0!=1[/math]

[dvjustus]

Hi Matt,

 

I understand what you mean. I'm not familiar with the protocols, but at the outset, I should have at least given:

 

1. the set of non-negative integers as the domain

2. where the correlation was coming from

3. that only the simplest formula was needed (well, "simple" for someone who forgot a lot of Calculus).

[bloodhound]

oh yeah. i remember why its 2^n -1. the number of subsets of a finite set is 2^n, cos you have 2 option for each element ( ie to include or not to include). and the -1 is there because we do not want the empty set to be counted as well.

[dvjustus]

well, "simple" for someone who forgot a lot of Calculus

Not calculus. Factorials and summation rather.

[dvjustus]

i remember why its 2^n -1

Just curious, since you say this as though this is a common problem, is it a common problem?

[matt grime]

Yes, it's a very common problem that people do when they first do combinatorics (counting proofs) binomial coeffs have the following properties:

 

[math]\sum_{r=0}^{n}\binom{n}{r} = 2^n[/math]

 

[math] \binom{n}{r-1} + \binom{n}{r} = \binom{n+1}{r}[/math]

 

[math]\binom{p}{r}[/math] is divisible by p if p is a prime and r is between 1 and p-1.

 

they are all amongst some of the first things you might be asked to show abuot them, and there are many many more relations.