Dgdrxrt

My ex-girlfriend uses my Apple ID to login to her iPad, do I have to give her my Apple ID password to reset it?

Can someone clarify Hamming's notion of important problems in relation to modern academia?

What is required to make GPS signals available indoors?

files created then deleted at every second in tmp directory

What are the G forces leaving Earth orbit?

Why was the shrink from 8″ made only to 5.25″ and not smaller (4″ or less)

Getting extremely large arrows with tikzcd

How to install cross-compiler on Ubuntu 18.04?

Sums of two squares in arithmetic progressions

What is an equivalently powerful replacement spell for Yuan-Ti's Suggestion spell?

Do creatures with a speed 0ft., fly 30ft. (hover) ever touch the ground?

How dangerous is XSS

Why didn't Boeing produce its own regional jet?

Did 'Cinema Songs' exist during Hiranyakshipu's time?

Bullying boss launched a smear campaign and made me unemployable

How to coordinate airplane tickets?

Send out email when Apex Queueable fails and test it

Why is it a bad idea to hire a hitman to eliminate most corrupt politicians?

How can a day be of 24 hours?

What is the fastest integer factorization to break RSA?

Is it a bad idea to plug the other end of ESD strap to wall ground?

Finding the reason behind the value of the integral.

What is a Samsaran Word™?

How to compactly explain secondary and tertiary characters without resorting to stereotypes?

Sum of non-negative integers less than a given integer?

Determine the number of ordered triple $(x, y, z)$ of integer numbers (negatives and positives) satisfying $|x| + |y| + |z| le 6$For an $f:omega_1 to omega_1$, how to prove $alpha = f(alpha)$ for uncountably many $alpha$?All roots of a polynomial lie on a circle.Differential Equation involving Polynomial DiscriminantsFinding cardinality of a set which sum of its elements equal to an integerNumber of ways of writing an integer as a sum of other integersCountability of truth-valued functionsProve that if $A$ is any infinite set, the set of all finite subsets of $A$ has the same cardinality as $A$Bound for a Sum containing a multinomial coefficientAnother proof for impossibility of covering $mathbbR^n$ with a set of varieties of cardinality less than $2^aleph_0$Cardinality of all non-increasing functions from $mathbbN$ to $mathbbN$

0

$begingroup$

Let $N in mathbbZ_geq 0$ and let $alpha = (a_1,...,a_n) in mathbbZ_geq 0^n$.

I am interested in the cardinality of the set $alpha$, where $|alpha| = a_1 + a_2 + ... + a_n$.

Does anyone know how to prove this? I assume there is some sort of combinatorial argument but I'm stuck? Any hints would be appreciated.

combinatorics elementary-set-theory polynomials

share|cite|improve this question

edited Mar 28 at 14:57

the man

asked Mar 28 at 14:48

the manthe man

831716

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @RossMillikan It was supposed to be non-negative integers, thank you.
  $endgroup$
  – the man
  Mar 28 at 14:57
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You might be able to adapt the approach from this answer.
  $endgroup$
  – robjohn♦
  Mar 28 at 15:25
  

  
  
  
  

add a comment | 

0

$begingroup$

Let $N in mathbbZ_geq 0$ and let $alpha = (a_1,...,a_n) in mathbbZ_geq 0^n$.

I am interested in the cardinality of the set $alpha$, where $|alpha| = a_1 + a_2 + ... + a_n$.

Does anyone know how to prove this? I assume there is some sort of combinatorial argument but I'm stuck? Any hints would be appreciated.

combinatorics elementary-set-theory polynomials

share|cite|improve this question

edited Mar 28 at 14:57

the man

asked Mar 28 at 14:48

the manthe man

831716

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @RossMillikan It was supposed to be non-negative integers, thank you.
  $endgroup$
  – the man
  Mar 28 at 14:57
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You might be able to adapt the approach from this answer.
  $endgroup$
  – robjohn♦
  Mar 28 at 15:25
  

  
  
  
  

add a comment | 

$begingroup$

Let $N in mathbbZ_geq 0$ and let $alpha = (a_1,...,a_n) in mathbbZ_geq 0^n$.

I am interested in the cardinality of the set $alpha$, where $|alpha| = a_1 + a_2 + ... + a_n$.

Does anyone know how to prove this? I assume there is some sort of combinatorial argument but I'm stuck? Any hints would be appreciated.

combinatorics elementary-set-theory polynomials

share|cite|improve this question

edited Mar 28 at 14:57

the man

asked Mar 28 at 14:48

the manthe man

831716

$endgroup$

share|cite|improve this question

edited Mar 28 at 14:57

the man

asked Mar 28 at 14:48

the manthe man

831716

share|cite|improve this question

edited Mar 28 at 14:57

the man

asked Mar 28 at 14:48

the manthe man

831716

asked Mar 28 at 14:48

the manthe man

831716

asked Mar 28 at 14:48

the manthe man

831716

3 Answers
3

active

oldest

votes

1

$begingroup$

Let $A(n, N)$ be your number. Define $A_r(n, N)$ to be the cardinality of the set
$$
alpha
$$
Clearly, we have
$$
A(n, N) = sum_r = 0^N A_r(n, N)
$$
Also, note that by simply removing the last element of $alpha$, we have
$$
A_r(n, r) = A(n-1, N-r)
$$
which is to say
$$
A(n, N) = sum_r = 0^N A(n-1, N-r)
$$
Comparing the sum for $A(n, N)$ and the sum for $A(n, N-1)$, we get
$$
A(n, N) = A(n-1, N) + A(n, N-1)
$$
and we see that these are just relabelled binomial cefficients:
$$
A(n, N) = binomn+NN
$$

share|cite|improve this answer

edited Mar 28 at 15:46

answered Mar 28 at 15:07

ArthurArthur

121k7122208

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  By the stars and bars method, the number of non-negative $n$-tuples which sum to $N$ is $binomN+n -1N$? This is the number you've worked out for the cardinality of my set? But the cardinality of my set must be bigger than this right?
  $endgroup$
  – the man
  Mar 28 at 15:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It must? Have you checked? For $n = 1$ or $n = 2$ it should be a simple thing to count by hand and compare.
  $endgroup$
  – Arthur
  Mar 28 at 15:28
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  My set includes the case where the non-negative $n$-typles sum to $N$. But it also includes the non-negative $n$-tuples which sum to $0,1,...,N-1$.
  $endgroup$
  – the man
  Mar 28 at 15:29
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @theman You're right. I'm off by 1 somewhere. Let me just recheck my calculations.
  $endgroup$
  – Arthur
  Mar 28 at 15:34
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @theman There we go. I had the wrong base case ($n = 0$ is valid, and $A(0,N) = 1$), and also I hadn't looked thoroughly enough at my sums. Now it should be correct.
  $endgroup$
  – Arthur
  Mar 28 at 15:47
  

  
  
  
  

 | 
show 1 more comment

1

$begingroup$

Hint: for $alpha = N$ you are looking for weak compositions of $N$ into $n$ parts. You can solve that with the usual stars and bars argument. Now just sum the number of compositions of $k$ from $0$ to $N$

share|cite|improve this answer

answered Mar 28 at 14:55

Ross MillikanRoss Millikan

301k24200375

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So, the answer is the value of the sum $sum_k=0^N binomk+n-1n-1$?
  $endgroup$
  – the man
  Mar 28 at 15:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, that is correct
  $endgroup$
  – Ross Millikan
  Mar 28 at 15:43
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That sum is $binomN+nn$, which matches Arthur's answer.
  $endgroup$
  – robjohn♦
  Mar 28 at 18:20
  

  
  
  
  

add a comment | 

0

$begingroup$

Think of this as putting $N$ items into $n+1$ bins, where $a_1,dots,a_n$ are the contents of the first $n$ bins. Using stars and bars, this gives $binomN+nn$.

share|cite|improve this answer

answered Mar 28 at 18:34

robjohn♦robjohn

270k27312640

$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
);



);

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%2f3165978%2fsum-of-non-negative-integers-less-than-a-given-integer%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

$begingroup$

Let $A(n, N)$ be your number. Define $A_r(n, N)$ to be the cardinality of the set
$$
alpha
$$
Clearly, we have
$$
A(n, N) = sum_r = 0^N A_r(n, N)
$$
Also, note that by simply removing the last element of $alpha$, we have
$$
A_r(n, r) = A(n-1, N-r)
$$
which is to say
$$
A(n, N) = sum_r = 0^N A(n-1, N-r)
$$
Comparing the sum for $A(n, N)$ and the sum for $A(n, N-1)$, we get
$$
A(n, N) = A(n-1, N) + A(n, N-1)
$$
and we see that these are just relabelled binomial cefficients:
$$
A(n, N) = binomn+NN
$$

share|cite|improve this answer

edited Mar 28 at 15:46

answered Mar 28 at 15:07

ArthurArthur

121k7122208

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  By the stars and bars method, the number of non-negative $n$-tuples which sum to $N$ is $binomN+n -1N$? This is the number you've worked out for the cardinality of my set? But the cardinality of my set must be bigger than this right?
  $endgroup$
  – the man
  Mar 28 at 15:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It must? Have you checked? For $n = 1$ or $n = 2$ it should be a simple thing to count by hand and compare.
  $endgroup$
  – Arthur
  Mar 28 at 15:28
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  My set includes the case where the non-negative $n$-typles sum to $N$. But it also includes the non-negative $n$-tuples which sum to $0,1,...,N-1$.
  $endgroup$
  – the man
  Mar 28 at 15:29
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @theman You're right. I'm off by 1 somewhere. Let me just recheck my calculations.
  $endgroup$
  – Arthur
  Mar 28 at 15:34
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @theman There we go. I had the wrong base case ($n = 0$ is valid, and $A(0,N) = 1$), and also I hadn't looked thoroughly enough at my sums. Now it should be correct.
  $endgroup$
  – Arthur
  Mar 28 at 15:47
  

  
  
  
  

 | 
show 1 more comment

1

$begingroup$

Let $A(n, N)$ be your number. Define $A_r(n, N)$ to be the cardinality of the set
$$
alpha
$$
Clearly, we have
$$
A(n, N) = sum_r = 0^N A_r(n, N)
$$
Also, note that by simply removing the last element of $alpha$, we have
$$
A_r(n, r) = A(n-1, N-r)
$$
which is to say
$$
A(n, N) = sum_r = 0^N A(n-1, N-r)
$$
Comparing the sum for $A(n, N)$ and the sum for $A(n, N-1)$, we get
$$
A(n, N) = A(n-1, N) + A(n, N-1)
$$
and we see that these are just relabelled binomial cefficients:
$$
A(n, N) = binomn+NN
$$

share|cite|improve this answer

edited Mar 28 at 15:46

answered Mar 28 at 15:07

ArthurArthur

121k7122208

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  By the stars and bars method, the number of non-negative $n$-tuples which sum to $N$ is $binomN+n -1N$? This is the number you've worked out for the cardinality of my set? But the cardinality of my set must be bigger than this right?
  $endgroup$
  – the man
  Mar 28 at 15:26
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  It must? Have you checked? For $n = 1$ or $n = 2$ it should be a simple thing to count by hand and compare.
  $endgroup$
  – Arthur
  Mar 28 at 15:28
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  My set includes the case where the non-negative $n$-typles sum to $N$. But it also includes the non-negative $n$-tuples which sum to $0,1,...,N-1$.
  $endgroup$
  – the man
  Mar 28 at 15:29
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  @theman You're right. I'm off by 1 somewhere. Let me just recheck my calculations.
  $endgroup$
  – Arthur
  Mar 28 at 15:34
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  @theman There we go. I had the wrong base case ($n = 0$ is valid, and $A(0,N) = 1$), and also I hadn't looked thoroughly enough at my sums. Now it should be correct.
  $endgroup$
  – Arthur
  Mar 28 at 15:47
  

  
  
  
  

 | 
show 1 more comment

$begingroup$

Let $A(n, N)$ be your number. Define $A_r(n, N)$ to be the cardinality of the set
$$
alpha
$$
Clearly, we have
$$
A(n, N) = sum_r = 0^N A_r(n, N)
$$
Also, note that by simply removing the last element of $alpha$, we have
$$
A_r(n, r) = A(n-1, N-r)
$$
which is to say
$$
A(n, N) = sum_r = 0^N A(n-1, N-r)
$$
Comparing the sum for $A(n, N)$ and the sum for $A(n, N-1)$, we get
$$
A(n, N) = A(n-1, N) + A(n, N-1)
$$
and we see that these are just relabelled binomial cefficients:
$$
A(n, N) = binomn+NN
$$

share|cite|improve this answer

edited Mar 28 at 15:46

answered Mar 28 at 15:07

ArthurArthur

121k7122208

$endgroup$

share|cite|improve this answer

edited Mar 28 at 15:46

answered Mar 28 at 15:07

ArthurArthur

121k7122208

answered Mar 28 at 15:07

ArthurArthur

121k7122208

answered Mar 28 at 15:07

ArthurArthur

121k7122208

1

$begingroup$

Hint: for $alpha = N$ you are looking for weak compositions of $N$ into $n$ parts. You can solve that with the usual stars and bars argument. Now just sum the number of compositions of $k$ from $0$ to $N$

share|cite|improve this answer

answered Mar 28 at 14:55

Ross MillikanRoss Millikan

301k24200375

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So, the answer is the value of the sum $sum_k=0^N binomk+n-1n-1$?
  $endgroup$
  – the man
  Mar 28 at 15:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, that is correct
  $endgroup$
  – Ross Millikan
  Mar 28 at 15:43
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That sum is $binomN+nn$, which matches Arthur's answer.
  $endgroup$
  – robjohn♦
  Mar 28 at 18:20
  

  
  
  
  

add a comment | 

1

$begingroup$

Hint: for $alpha = N$ you are looking for weak compositions of $N$ into $n$ parts. You can solve that with the usual stars and bars argument. Now just sum the number of compositions of $k$ from $0$ to $N$

share|cite|improve this answer

answered Mar 28 at 14:55

Ross MillikanRoss Millikan

301k24200375

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  So, the answer is the value of the sum $sum_k=0^N binomk+n-1n-1$?
  $endgroup$
  – the man
  Mar 28 at 15:05
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Yes, that is correct
  $endgroup$
  – Ross Millikan
  Mar 28 at 15:43
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That sum is $binomN+nn$, which matches Arthur's answer.
  $endgroup$
  – robjohn♦
  Mar 28 at 18:20
  

  
  
  
  

add a comment | 

$begingroup$

Hint: for $alpha = N$ you are looking for weak compositions of $N$ into $n$ parts. You can solve that with the usual stars and bars argument. Now just sum the number of compositions of $k$ from $0$ to $N$

share|cite|improve this answer

answered Mar 28 at 14:55

Ross MillikanRoss Millikan

301k24200375

$endgroup$

share|cite|improve this answer

answered Mar 28 at 14:55

Ross MillikanRoss Millikan

301k24200375

answered Mar 28 at 14:55

Ross MillikanRoss Millikan

301k24200375

answered Mar 28 at 14:55

Ross MillikanRoss Millikan

301k24200375

0

$begingroup$

Think of this as putting $N$ items into $n+1$ bins, where $a_1,dots,a_n$ are the contents of the first $n$ bins. Using stars and bars, this gives $binomN+nn$.

share|cite|improve this answer

answered Mar 28 at 18:34

robjohn♦robjohn

270k27312640

$endgroup$

add a comment | 

0

$begingroup$

Think of this as putting $N$ items into $n+1$ bins, where $a_1,dots,a_n$ are the contents of the first $n$ bins. Using stars and bars, this gives $binomN+nn$.

share|cite|improve this answer

answered Mar 28 at 18:34

robjohn♦robjohn

270k27312640

$endgroup$

add a comment | 

$begingroup$

Think of this as putting $N$ items into $n+1$ bins, where $a_1,dots,a_n$ are the contents of the first $n$ bins. Using stars and bars, this gives $binomN+nn$.

share|cite|improve this answer

answered Mar 28 at 18:34

robjohn♦robjohn

270k27312640

$endgroup$

share|cite|improve this answer

answered Mar 28 at 18:34

robjohn♦robjohn

270k27312640

answered Mar 28 at 18:34

robjohn♦robjohn

270k27312640

answered Mar 28 at 18:34

robjohn♦robjohn

270k27312640