number of integer partittions into distinct parts

Art of Problem Solving

AoPS Online

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

High School Math Grades 9-12, Ages 13-18

Grades 9-12, Ages 13-18

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

number of integer partittions into distinct parts

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

887 posts

#1 h Sep 7, 2017, 7:01 PM • 2 Y

Y by Adventure10, Mango247

How many positive integer solutions of the equation $\;$ $a+b+c+d=100$ $\;$ where $\;$ $a< b< c< d$ ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2458 posts

#3 h Sep 7, 2017, 7:29 PM • 2 Y

Y by Adventure10, Mango247

Casework bash (partial)

This post has been edited 1 time. Last edited by mathdragon2000, Sep 7, 2017, 7:30 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2399 posts

#4 h Sep 7, 2017, 7:42 PM • 2 Y

Y by Adventure10, Mango247

Check me on this

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#5 h Sep 7, 2017, 7:58 PM • 2 Y

Y by Adventure10, Mango247

@brainiac1

This post has been edited 2 times. Last edited by Strategos, Sep 7, 2017, 8:18 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

14 posts

#6 h Sep 7, 2017, 8:17 PM • 5 Y

Y by laegolas, brainiac1, durkaa03, thedoge, Adventure10

solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2399 posts

#7 h Sep 7, 2017, 8:29 PM • 1 Y

Y by Adventure10

Strategos wrote:

@brainiac1

Ok, thanks. I though something weird happened when I tried small cases.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

863 posts

#8 h Sep 7, 2017, 11:18 PM • 1 Y

Y by Adventure10

$4a'+3b'+2c'+d'=90$

$\frac{1}{(1-x^4)(1-x^3)(1-x^2)(1-x)}=\frac{1}{(1-x^{12})^4}(\sum_{k=0}^2 x^{4k})(\sum_{k=0}^3 x^{3k})(\sum_{k=0}^5 x^{2k})(\sum_{k=0}^{11} x^k)=(\sum_{k=0}^2 x^{4k})(\sum_{k=0}^3 x^{3k})(\sum_{k=0}^5 x^{2k})(\sum_{k=0}^{11} x^k)\sum_{k=0}^{\infty} \binom{k+3}{3} x^{12k}$

expand the four limited summations,it has degree up to 38

$90=12\times 7+6=12\times 6+18=12\times 5+30$

coefficients of $x^6,x^{18},x^{30}$ are 9,48,15 respectively

the number of solution is $9\binom{7+3}{3}+48\binom{6+3}{3}+15\binom{5+3}{3}=5952$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

887 posts

#9 h Sep 8, 2017, 10:32 AM • 2 Y

Y by fungarwai, Adventure10

$a+b+c+d=100$ where $0< a< b< c< d$
let ${a}'=a-1 , {b}'=b-2 ,{c}'=c-3, {d}'=d-4 \Rightarrow {a}'+{b}'+{c}'+{d}'=90$ where $0\leq {a}'\leq {b}'\leq {c}'\leq {d}'$
Due to symmetry we will use Burnside's Lemma as follows:
we know that any group of permutations of 4 objects has 1 identity element, six 2-cycles, eight 3-cycles, six 4-cycles, and 3 pairs of 2-cycles so we need to consider 5 cases :
case1: the number of solutions of the equation ${a}'+{b}'+{c}'+{d}'=90$ with no restriction
$=\binom{4+90-1}{90}=\binom{93}{3}$
case2: if two variable are equal say ${b}'={a}'\Rightarrow 2{a}'+{c}'+{d}'=90\Rightarrow {c}'+{d}'$ is even
if both ${c}'$ and ${d}$ are even $\Rightarrow {c}'=2{c}''$ and ${d}'=2{d}''$
$2{a}'+2{c}''+2{d}''=90\Rightarrow {a}'+{c}''+{d}''=45$ so the number of solutions $=\binom{45+3-1}{45}=\binom{47}{2}$
if both ${c}'$ and ${d}$ are odd $\Rightarrow {c}'=2{c}''+1,{d}'=2{d}''+1\Rightarrow 2{a}'+\left (2{c}''+1 \right )+\left (2{d}''+1 \right )=90\Rightarrow {a}'+{c}''+{d}''=44$ so the number of solutions $=\binom{44+3-1}{44}=\binom{46}{2}$
Thus the total number of solutions in this case $=6 \left [\binom{47}{2}+\binom{46}{2} \right ]$
where 6 is the number 2-cycles.
case3: if three variable are equal say ${b}'={c}'={a}'\Rightarrow 3{a}'+{d}'=90\Rightarrow {d}'$ is a multiple of 3 $\Rightarrow {d}'=3{d}'' \Rightarrow 3{a}'+3{d}''=90\Rightarrow {a}'+{d}''=30$
so the number of solutions of the equation $=\binom{30+2-1}{30}=\binom{31}{1}$
therefore the total number of solutions in this case $=8\binom{31}{1}$ where 8 is the number of
3-cycles.
case4: if four variables are equal say ${d}'={c}'={b}'={a}' \to \Rightarrow 4{a}'=90$ so the number of solutions of the equations $=0$ thus the total number of solutions in this case $=6\times 0=0$ where 6 is the number of 4-cycles.
case5: if two variable are equal and the other two variables are equal say ${b}'={a}' ,{d}'={c}'\Rightarrow 2{a}'+2{c}'=90\Rightarrow {a}'+{c}'=45$ so the number of solutions in this case $=\binom{45+2-1}{45}=\binom{46}{1}$ thus the total number of solutions in this case $=3\binom{46}{1}$
By Burnside's Lemma the total number of solutions
$=\frac{1}{24} \left \{\binom{93}{3}+6\left [\binom{47}{2}+\binom{46}{2} \right ]+8\binom{31}{1}+6\times 0+3\binom{46}{1} \right \} =5952$
where $24$ is the total number of all cycles.

This post has been edited 2 times. Last edited by gasgous, Sep 8, 2017, 10:48 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

randomdude10807

2021 posts

randomdude10807

#10 h Sep 8, 2017, 11:09 AM • 1 Y

Y by Adventure10

Almost Correct Solution

This post has been edited 1 time. Last edited by randomdude10807, Sep 8, 2017, 11:09 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

863 posts

#11 h Sep 8, 2017, 12:09 PM • 1 Y

Y by Adventure10

$|x_1 \ne x_2 \ne x_3 \ne x_4|=|U|-\sum|x_1=x_2|+2\sum|x_1=x_2=x_3|+\sum|x_1=x_2 \cap x_3=x_4|-6|x_1=x_2=x_3=x_4|$

$|x_1 \ne x_2 \ne ... \ne x_n|=\sum (-1)^{r_1+r_2+...+r_m} r_1!r_2!...r_m!\sum_{i_1\ne i_2 \ne ... \ne i_{r_t}}|\bigcap_{t=1}^m x_{i_1}=x_{i_2}=...=x_{i_{r_t+1}}|$

I made this formula before but I don't have proof

$\frac{1}{24}(\binom{99}{3}-6(\binom{50}{2}+\binom{49}{2})+8\binom{33}{1}+3\binom{49}{1}-6\times 1)=5952$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5317 posts

#12 h Sep 8, 2017, 2:20 PM • 2 Y

Y by Adventure10, Mango247

Well what you did is basically PIE

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

887 posts

#13 h Sep 8, 2017, 7:06 PM • 1 Y

Y by Adventure10

I think the best way is to use generating function but it requires the use of partial fractions which is time consuming in order to find a certain coefficient.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

always_incorrect

4 posts

always_incorrect

#14 h Sep 8, 2017, 9:10 PM • 3 Y

Y by doitsudoitsu, Adventure10, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

809 posts

#15 h Sep 8, 2017, 9:32 PM • 2 Y

Y by Cygnet, Adventure10

Nice username?

Oh wait darn this is a troll account why...

This post has been edited 1 time. Last edited by always_correct, Sep 8, 2017, 9:34 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

269 posts

#16 h Sep 9, 2017, 3:08 AM • 2 Y

Y by Adventure10, Mango247

always_incorrect wrote:

Solution

$a<b<c<d$ , so this is incorrect, as your usename implies.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

901 posts

SS4

#17 h Sep 9, 2017, 10:52 PM • 1 Y

Y by Adventure10

I think always_incorrect has the right idea, you just have to remove the assumption that order matters ;D
What that means

This post has been edited 1 time. Last edited by SS4, Sep 9, 2017, 10:53 PM
Reason: Clarified

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a