Combinatorics-Partitions of Natural Numbers

0

$begingroup$

Let $R(r,k)$ denote the number of partitions of the natural number $r$ into $k$ parts.

1. Show that $R(r,k)=R(r-1,k-1)+R(r-k,k)$




2. Show that $R(n-r,1)+R(n-r,2)+R(n-r,3)+...R(n-r,r)=R(n,r)$

combinatorics integer-partitions

share|cite|improve this question

edited Jan 18 at 8:30

idriskameni

685319

asked Jan 18 at 7:12

SaeeSaee

387

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Isn't $R(r-1,k-1)$ also the number of partitions of $r$ into $k$ parts where in addition the least part must be $1$?
  $endgroup$
  – Lord Shark the Unknown
  Jan 18 at 8:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It must be $R(r,k-1)+R(r-k,k)$.
  $endgroup$
  – Takahiro Waki
  Jan 18 at 8:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  R(r-1,k-1) is also the number of partitions of r into k parts where the least part must be 1. Even I think this is true 👆
  $endgroup$
  – Saee
  Jan 18 at 9:42
  

  
  
  
  

add a comment | 

0

$begingroup$

Let $R(r,k)$ denote the number of partitions of the natural number $r$ into $k$ parts.

1. Show that $R(r,k)=R(r-1,k-1)+R(r-k,k)$




2. Show that $R(n-r,1)+R(n-r,2)+R(n-r,3)+...R(n-r,r)=R(n,r)$

combinatorics integer-partitions

share|cite|improve this question

edited Jan 18 at 8:30

idriskameni

685319

asked Jan 18 at 7:12

SaeeSaee

387

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Isn't $R(r-1,k-1)$ also the number of partitions of $r$ into $k$ parts where in addition the least part must be $1$?
  $endgroup$
  – Lord Shark the Unknown
  Jan 18 at 8:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It must be $R(r,k-1)+R(r-k,k)$.
  $endgroup$
  – Takahiro Waki
  Jan 18 at 8:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  R(r-1,k-1) is also the number of partitions of r into k parts where the least part must be 1. Even I think this is true 👆
  $endgroup$
  – Saee
  Jan 18 at 9:42
  

  
  
  
  

add a comment | 

0

0

0

1

$begingroup$

Let $R(r,k)$ denote the number of partitions of the natural number $r$ into $k$ parts.

1. Show that $R(r,k)=R(r-1,k-1)+R(r-k,k)$




2. Show that $R(n-r,1)+R(n-r,2)+R(n-r,3)+...R(n-r,r)=R(n,r)$

combinatorics integer-partitions

share|cite|improve this question

edited Jan 18 at 8:30

idriskameni

685319

asked Jan 18 at 7:12

SaeeSaee

387

$endgroup$

Let $R(r,k)$ denote the number of partitions of the natural number $r$ into $k$ parts.

1. Show that $R(r,k)=R(r-1,k-1)+R(r-k,k)$




2. Show that $R(n-r,1)+R(n-r,2)+R(n-r,3)+...R(n-r,r)=R(n,r)$

combinatorics integer-partitions

combinatorics integer-partitions

share|cite|improve this question

edited Jan 18 at 8:30

idriskameni

685319

asked Jan 18 at 7:12

SaeeSaee

387

share|cite|improve this question

edited Jan 18 at 8:30

idriskameni

685319

asked Jan 18 at 7:12

SaeeSaee

387

share|cite|improve this question

share|cite|improve this question

edited Jan 18 at 8:30

idriskameni

685319

edited Jan 18 at 8:30

idriskameni

685319

edited Jan 18 at 8:30

idriskameni

685319

685319

asked Jan 18 at 7:12

SaeeSaee

387

asked Jan 18 at 7:12

SaeeSaee

387

asked Jan 18 at 7:12

SaeeSaee

387

387

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Isn't $R(r-1,k-1)$ also the number of partitions of $r$ into $k$ parts where in addition the least part must be $1$?
  $endgroup$
  – Lord Shark the Unknown
  Jan 18 at 8:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It must be $R(r,k-1)+R(r-k,k)$.
  $endgroup$
  – Takahiro Waki
  Jan 18 at 8:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  R(r-1,k-1) is also the number of partitions of r into k parts where the least part must be 1. Even I think this is true 👆
  $endgroup$
  – Saee
  Jan 18 at 9:42
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Isn't $R(r-1,k-1)$ also the number of partitions of $r$ into $k$ parts where in addition the least part must be $1$?
  $endgroup$
  – Lord Shark the Unknown
  Jan 18 at 8:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It must be $R(r,k-1)+R(r-k,k)$.
  $endgroup$
  – Takahiro Waki
  Jan 18 at 8:20
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  R(r-1,k-1) is also the number of partitions of r into k parts where the least part must be 1. Even I think this is true 👆
  $endgroup$
  – Saee
  Jan 18 at 9:42
  

  
  
  
  

$begingroup$
Isn't $R(r-1,k-1)$ also the number of partitions of $r$ into $k$ parts where in addition the least part must be $1$?
$endgroup$
– Lord Shark the Unknown
Jan 18 at 8:00

$begingroup$
Isn't $R(r-1,k-1)$ also the number of partitions of $r$ into $k$ parts where in addition the least part must be $1$?
$endgroup$
– Lord Shark the Unknown
Jan 18 at 8:00

$begingroup$
It must be $R(r,k-1)+R(r-k,k)$.
$endgroup$
– Takahiro Waki
Jan 18 at 8:20

$begingroup$
It must be $R(r,k-1)+R(r-k,k)$.
$endgroup$
– Takahiro Waki
Jan 18 at 8:20

$begingroup$
R(r-1,k-1) is also the number of partitions of r into k parts where the least part must be 1. Even I think this is true 👆
$endgroup$
– Saee
Jan 18 at 9:42

$begingroup$
R(r-1,k-1) is also the number of partitions of r into k parts where the least part must be 1. Even I think this is true 👆
$endgroup$
– Saee
Jan 18 at 9:42

add a comment | 

2 Answers
2

active

oldest

votes

2

$begingroup$

1. If the smallest part of a partition of $r$ into $k$ parts is $1$, then removing the smallest part leaves a partition of $r-1$ into $k-1$ parts. If the smallest part is more than $1$, the reducing each part by $1$ leaves a partition of $r-k$ into $k$ parts.




2. Take a partition of $n$ into $r$ parts, and reduce the size of each part by $1$. What remains is a partition of $n-r$ into $m$ parts, for some number $m$ between $1$ and $r$.

share|cite|improve this answer

answered Jan 18 at 19:59

Mike EarnestMike Earnest

23.9k12051

$endgroup$

add a comment | 

1

$begingroup$

I would say that you can prove that using generating functions.

Let $R(n,k)=p_k(n)$ be the function you have mentioned above. Then it can be expressed as:

$$sum_{ngeq0} p_k(n)cdot x^n = x^kcdot prod_{k=1}^n frac{1}{1-x^i}$$

Then, if you see that this identities have the same generating function, you are done.

share|cite|improve this answer

answered Jan 18 at 8:06

idriskameniidriskameni

685319

$endgroup$

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

Thanks for contributing an answer to Mathematics Stack Exchange!

• Please be sure to answer the question. Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.


• Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3077922%2fcombinatorics-partitions-of-natural-numbers%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

2

$begingroup$

1. If the smallest part of a partition of $r$ into $k$ parts is $1$, then removing the smallest part leaves a partition of $r-1$ into $k-1$ parts. If the smallest part is more than $1$, the reducing each part by $1$ leaves a partition of $r-k$ into $k$ parts.




2. Take a partition of $n$ into $r$ parts, and reduce the size of each part by $1$. What remains is a partition of $n-r$ into $m$ parts, for some number $m$ between $1$ and $r$.

share|cite|improve this answer

answered Jan 18 at 19:59

Mike EarnestMike Earnest

23.9k12051

$endgroup$

add a comment | 

2

$begingroup$

1. If the smallest part of a partition of $r$ into $k$ parts is $1$, then removing the smallest part leaves a partition of $r-1$ into $k-1$ parts. If the smallest part is more than $1$, the reducing each part by $1$ leaves a partition of $r-k$ into $k$ parts.




2. Take a partition of $n$ into $r$ parts, and reduce the size of each part by $1$. What remains is a partition of $n-r$ into $m$ parts, for some number $m$ between $1$ and $r$.

share|cite|improve this answer

answered Jan 18 at 19:59

Mike EarnestMike Earnest

23.9k12051

$endgroup$

add a comment | 

2

2

2

$begingroup$

1. If the smallest part of a partition of $r$ into $k$ parts is $1$, then removing the smallest part leaves a partition of $r-1$ into $k-1$ parts. If the smallest part is more than $1$, the reducing each part by $1$ leaves a partition of $r-k$ into $k$ parts.




2. Take a partition of $n$ into $r$ parts, and reduce the size of each part by $1$. What remains is a partition of $n-r$ into $m$ parts, for some number $m$ between $1$ and $r$.

share|cite|improve this answer

answered Jan 18 at 19:59

Mike EarnestMike Earnest

23.9k12051

$endgroup$

1. If the smallest part of a partition of $r$ into $k$ parts is $1$, then removing the smallest part leaves a partition of $r-1$ into $k-1$ parts. If the smallest part is more than $1$, the reducing each part by $1$ leaves a partition of $r-k$ into $k$ parts.




2. Take a partition of $n$ into $r$ parts, and reduce the size of each part by $1$. What remains is a partition of $n-r$ into $m$ parts, for some number $m$ between $1$ and $r$.

share|cite|improve this answer

answered Jan 18 at 19:59

Mike EarnestMike Earnest

23.9k12051

share|cite|improve this answer

share|cite|improve this answer

answered Jan 18 at 19:59

Mike EarnestMike Earnest

23.9k12051

answered Jan 18 at 19:59

Mike EarnestMike Earnest

23.9k12051

answered Jan 18 at 19:59

Mike EarnestMike Earnest

23.9k12051

23.9k12051

add a comment | 

add a comment | 

1

$begingroup$

I would say that you can prove that using generating functions.

Let $R(n,k)=p_k(n)$ be the function you have mentioned above. Then it can be expressed as:

$$sum_{ngeq0} p_k(n)cdot x^n = x^kcdot prod_{k=1}^n frac{1}{1-x^i}$$

Then, if you see that this identities have the same generating function, you are done.

share|cite|improve this answer

answered Jan 18 at 8:06

idriskameniidriskameni

685319

$endgroup$

add a comment | 

1

$begingroup$

I would say that you can prove that using generating functions.

Let $R(n,k)=p_k(n)$ be the function you have mentioned above. Then it can be expressed as:

$$sum_{ngeq0} p_k(n)cdot x^n = x^kcdot prod_{k=1}^n frac{1}{1-x^i}$$

Then, if you see that this identities have the same generating function, you are done.

share|cite|improve this answer

answered Jan 18 at 8:06

idriskameniidriskameni

685319

$endgroup$

add a comment | 

1

1

1

$begingroup$

I would say that you can prove that using generating functions.

Let $R(n,k)=p_k(n)$ be the function you have mentioned above. Then it can be expressed as:

$$sum_{ngeq0} p_k(n)cdot x^n = x^kcdot prod_{k=1}^n frac{1}{1-x^i}$$

Then, if you see that this identities have the same generating function, you are done.

share|cite|improve this answer

answered Jan 18 at 8:06

idriskameniidriskameni

685319

$endgroup$

I would say that you can prove that using generating functions.

Let $R(n,k)=p_k(n)$ be the function you have mentioned above. Then it can be expressed as:

$$sum_{ngeq0} p_k(n)cdot x^n = x^kcdot prod_{k=1}^n frac{1}{1-x^i}$$

Then, if you see that this identities have the same generating function, you are done.

share|cite|improve this answer

answered Jan 18 at 8:06

idriskameniidriskameni

685319

share|cite|improve this answer

share|cite|improve this answer

answered Jan 18 at 8:06

idriskameniidriskameni

685319

answered Jan 18 at 8:06

idriskameniidriskameni

685319

answered Jan 18 at 8:06

idriskameniidriskameni

685319

685319

add a comment | 

add a comment | 

Thanks for contributing an answer to Mathematics Stack Exchange!

• Please be sure to answer the question. Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.


• Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Thanks for contributing an answer to Mathematics Stack Exchange!

• Please be sure to answer the question. Provide details and share your research!

But avoid …

• Asking for help, clarification, or responding to other answers.


• Making statements based on opinion; back them up with references or personal experience.

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3077922%2fcombinatorics-partitions-of-natural-numbers%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

This page is only for reference, If you need detailed information, please check here