Factorials, handshake problem, help

[abertram28]

im dealing with a problem that isn't that hard, but its messing me up.

its been a long time since i took high school and college math, but I am very smart.

im trying to write an equation for the general description of a problem like this: you have a tile with x squares on it. you have a box with y number of crayons. you are going to color the tile. how many unique tiles can you make with your crayons if the exact position of each color doesn't matter.
like, if you have x=4, y=4, abcd for colors.
we would only count abcd once, instead of counting abcd and acbd as unique. ok?

so i figured out for one square there is a simple equation... 1,2,3,4,...
i also figured out how the equations are related.
my calc is too fuzzy and my factorials education is non-existant.

i know that the equation for the two boxes is the sum of the terms from the first equation. i also remember that handshake problem is (n)(n+1)(1/2) or (n^2+n)/2

i also know that the equation for the three box equation equals the sum of the sums, or the sum of the terms from the two box equation, which is the sum from n->1 of n... for n=4, i know the third equations should give me something like... for 4 crayons;
since 1 box is 1,2,3,4; y=4. the second is 1,1+2,1+2+3,1+2+3+4, y=10
so the third is [(1)+(1+2)+(1+2+3)+(1+2+3+4)]=20 and i know its right.

the fourth should be then (1)+[(1)+(1+2)]+[(1)+(1+2)+(1+2+3)]+[1+1+2+1+2+3+1+2+3+4]=

should i start by factoring out a 1, then putting a plus, then factoring out a 2, then a plus, then factor 3...?

i want to put this in an equation in general terms of n=number of crayons with x=boxes on the tile, and y=total number of possiblities.

im really smart but i just can't see how to formulate the general equation, though i have no trouble calculating the specific answers for lower numbers.
HELP!

 

[uart]

You haven't done a real good job of explaining the problem but here are some solutions.

If every "square" on the tile has to be a different color (and has to be some color) then the number of possible combinations is, C(y,x) = y! / ( x! (y-x)! )

If every square need not be a different color (but must be some color) then the number of possible combinations is, C(y,1) + C(y,2) + ... C(y,x)

 

[AKG]

Let y represent the number of possible colourings
Let n represent the number of squares
Let c represent the number of colours

y = \sum _{k=1} ^{\min \{n,c\}} {c\choose k} P(n,k)

where P(n,k) is the Constrained Partition Function [scroll down to equation (46)].

 

[abertram28]

well, i guess i didnt explain it well.
every square on the box need not be a different color, but various arrangements of the same color combination are not different. like, Red, Red, Blue, Blue is the same as Red, Blue, Red, Blue.

if x is the squares to be colored, y the colors with which to color, and p the total number of possible different combinations...
i think p=(x+y-1)!/(y!*(x-1)!)

but i can't get from the format of N(x,y) = sum N(x-1,y)+N(x,y-i) for (i=0...y) with
N(x,0)=1 to the "well known binomial" format using C(n,m)

can anyone explain these last few steps for me?

 

[AKG]

well, i guess i didnt explain it well.
every square on the box need not be a different color, but various arrangements of the same color combination are not different. like, Red, Red, Blue, Blue is the same as Red, Blue, Red, Blue.

if x is the squares to be colored, y the colors with which to color, and p the total number of possible different combinations...
i think p=(x+y-1)!/(y!*(x-1)!)

What's your reasoning? I'm pretty sure this is wrong.

Try 7 squares, 5 colours. P = 93 using my formula, and 462 using yours.

My formula is based on the idea that the total number of colourings is the sum of the number of colourings using 1 colour, plus the number of colourings using 2 colours, plus..., the number of colourings using min{c,n} colours. Why "min{c,n}"? Because you don't want to count colourings for more than the number of colours you have, i.e. there's no sense seeing how many ways you can colour fifty tiles with 12 colours if you only have 10 colours in your hand. However, you also don't want to count colourings for more than the number of squares that you have, i.e. if you have 6 squares and 7 colours, there's no way you can 7-colour the tile, so there's no point going past k=6. Now, there are P(n,k) ways to divide n tiles into k groups. With k groups, you can k-colour the tile. However, for each of the P(n,k) ways to group the squares, you can choose the colours in {n\choose k} ways. Actually, now that I look at this, this isn't right, because order will matter sometimes. For example, if n=6, and you group it into 2,2,2, then order of colour won't matter, but if you group it 1,2,3, then order matters, because if you choose blue,red,green, you'll have 1 blue, 2 red, 3 green, but if you choose red,blue,green, you'll have 1 red, 2 blue, 3 green. So maybe your way works, but it would be good for there to be some reasoning.

but i can't get from the format of N(x,y) = sum N(x-1,y)+N(x,y-i) for (i=0...y) with N(x,0)=1 to the "well known binomial" format using C(n,m)

Not exactly sure what yo're talking about. You haven't really explained what this N function is, nor the C function.

 

[AKG]

Okay, I think this should work:

Let y represent the number of possible colourings
Let n represent the number of squares
Let c represent the number of colours

y = \sum _{k=1} ^{\min \{n,c\}} {{n-1}\choose {k-1}} {c\choose k}

This is what I originally was going to put, but then thought I had to revise it because it would have repeat groupings, like 1,2,3 and 1,3,2, but I realize that these repeat groupings are counterbalanced by the fact that order does matter sometimes when you choose colours, as I suggested in my previous post. If n = 9 (nine squares), then 3,3,3 would not be repeated, and in this case, order of colour doesn't matter. However, when 2,3,4 is counted 6 times in the additional forms 3,2,4 AND 3,4,2 AND 2,4,3 AND 4,2,3 AND 4,3,2, it's actually good because the order of colour should matter in this case. And what is the signficance of {{n-1}\choose {k-1}}. Well, think of n like this:

1 | 2 | 3 | 4 | ... | n

Finding how many ways to partition n into k groups is like selecting k-1 of the n-1 vertical bars.

 

[abertram28]

well, it doesn't matter. that was part of my original constraints.
i don't want to count R,G,B as something different from R,B,G.
thats not something i can change.

 

[AKG]

well, it doesn't matter. that was part of my original constraints.
i don't want to count R,G,B as something different from R,B,G.
thats not something i can change.

I'm note exactly sure who you're replying to. If you're confused about my formula or think it's wrong, please ask, although I'm pretty certain it's right.

 

[abertram28]

93 is way to few colorings for a 7 box and 5 colors. youd have 6 combinations for each 2 colors. with 5 colors that's 10 different two color pairs, with 6 each. just the two color combinations plus the single combinations must be 65. if you use the explination and graph i did, you can easily see youll reach 84 combinations with just 3 boxes and 7 colors. and 120 for 7 colors with 4 boxes. and that's not even counting the different order ones twice. I am not sure if you are misunderstanding the problem because i can't word it right, or if you arent able to graph a few out to test your hypothesis. i, however, actually wrote out all possible combinations and crossed out redundant ones to check my math. my formula works, what I am looking for is an explination really.

if you table the numers up with the left most column being the boxes, and the top most row the number of colors, it makes a pretty square. if we substitute the boundry condition for the number of boxes = 0, we have all ones. then we have a pyrimid.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...
did anyone notice that? the square is on its side of course...
so it looks like
1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8
1 3 6 1015 21 28 36
1 4 10 20 35

im looking for how the sums of these rows can be represented in a way that allows me to plug in the numbers and get the desired place on the number pyramid, and to give me the value at that position.

 

[AKG]

93 is way to few colorings for a 7 box and 5 colors. youd have 6 combinations for each 2 colors. with 5 colors that's 10 different two color pairs, with 6 each. just the two color combinations plus the single combinations must be 65. if you use the explination and graph i did, you can easily see youll reach 84 combinations with just 3 boxes and 7 colors. and 120 for 7 colors with 4 boxes. and that's not even counting the different order ones twice. I am not sure if you are misunderstanding the problem because i can't word it right, or if you arent able to graph a few out to test your hypothesis. i, however, actually wrote out all possible combinations and crossed out redundant ones to check my math. my formula works, what I am looking for is an explination really.

I'll check your formula, although I'm pretty sure mine works. It seems you've missed my last 3 posts or so. With my new formula, the answer would be 320.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

This is the very famous Pascal's triangle.

im looking for how the sums of these rows can be represented in a way that allows me to plug in the numbers and get the desired place on the number pyramid, and to give me the value at that position.

The sum of the i'th row of pascal's triangle is:

\sum _{k=1} ^i {{i-1}\choose {k-1}}

 

[AKG]

I'm pretty sure your formula is wrong. Try 4 squares, 3 colours. Your formula gives 20 as the answer. It's easy to show that's wrong. The answer would be 15 (you can figure out all the cases yourself easily). Checking with my formula, it works. I've also provided reasoning for my formula. I've given a reason why yours is wrong (a counter-example), but if you want me to clarify the reasoning for mine, please ask.

 

[abertram28]

i think I am with you now, thanks for that sum of pascals. that helped me see how both our works related, but 93 is still way too few for the 7 box 5 color problem. you can see that the more of the results come in the 3 color range than the two, and the two color range produces 60 individual tiles. so the 3 color would produce more, and that would be already at least 125 results. is the formula you used to get 93 the older one you had? I am not quite clear as to an x,y formula i can use to get p. is such a formula existing? if not, i can use one just for x=boxes, y=colors, p=possibile colorings, with x=4.
getting a more general equation was just a goal, not a requirement.

i can settle for the equation for the 4 boxer. does my equation work with the x and y switched for just the 4 box occasion?

 

[AKG]

i think I am with you now, thanks for that sum of pascals. that helped me see how both our works related, but 93 is still way too few for the 7 box 5 color problem. you can see that the more of the results come in the 3 color range than the two, and the two color range produces 60 individual tiles. so the 3 color would produce more, and that would be already at least 125 results. is the formula you used to get 93 the older one you had? I am not quite clear as to an x,y formula i can use to get p. is such a formula existing? if not, i can use one just for x=boxes, y=colors, p=possibile colorings, with x=4.
getting a more general equation was just a goal, not a requirement.

I thought I clarified this. 93 was using my older formula, and 320 was with the newer one. This is the correct formula:

y = \sum _{k=1} ^{\min \{n,c\}} {{n-1}\choose {k-1}} {c\choose k}

This was the older formula (that got 93):

y = \sum _{k=1} ^{\min \{n,c\}} {c\choose k} P(n,k)

 

[abertram28]

maybe you could enlighten me as to the difference between those two equations?

 

[AKG]

Oops, sorry. Check it now, it's edited with the actual original formula.

 

[abertram28]

how can you divide by zero in the first term?

 

[AKG]

how can you divide by zero in the first term?

There is no division by zero. Perhaps you're unfamiliar with the notation:

{n\choose k} = {}_nC_k = \frac{n!}{k!(n-k)!}

And 0! = 1. {n\choose k} is "n choose k", which is the number of ways you can choose k distinct objects out of n distinct objects. Note, when you choose, order doesn't matter. A related operation is the permutation function, "n arrange k" where order matters:

_nP_k = \frac{n!}{(n-r)!}

 

[abertram28]

that cleared everything up! i get it now. and that helps me see just where my original formula was wrong too! thanks, i was totally unfamiliar with that notation.

the thing i meant divide by zero was the notation on the first part of the sum though, it was like (n-1)/(k-1) and i didnt know how if k=1 that made any sense. i assume now the notation there is different too.

 

[AKG]

the thing i meant divide by zero was the notation on the first part of the sum though, it was like (n-1)/(k-1) and i didnt know how if k=1 that made any sense. i assume now the notation there is different too.

Let's look at that:

{{n-1}\choose {k-1}}

= {{n-1}\choose {1-1}}

= {{n-1}\choose 0}

= \frac{(n-1)!}{0!(n-1-0)!}

= \frac{(n-1)!}{\mathbf{0!}(n-1)!}

= \frac{(n-1)!}{\mathbf{1}(n-1)!}

= \frac{(n-1)!}{(n-1)!}

= 1

The stuff in bold is what you were probably confused with, but as I explained in the previous post: 0! = 1. I assumed that's where you were confused, which is why I wrote "0! = 1;" I suppose you just missed it.

 

[abertram28]

yeah, that's what i was seeing when i looked at the other one too. I've just never seen that notation, but i get how it applied to both those now. thanks so much.