All Questions
Tagged with integer-partitions combinations
52
questions
0
votes
0
answers
19
views
Estimate the order of restricted number partitions
There are $k$ integers $m_l,1\leq l\leq k
$(maybe negetive), satisfiying $|m_l|\leq M$ and $\sum_l m_l=s$.
I want to get an order estimate of the number of solutions for $k, M$ when fixing $s$.
I came ...
- 91
0
votes
2
answers
66
views
Number of positive integral solution of $\sum_{i=1}^{10} x_i=30,\text{ where } 0 < x_i<7, \forall 1\le i\le 10$
I want to find the number of positive integer solutions of the equations given by
$$\sum_{i=1}^{10} x_i=30,\text{ where } 0 < x_i<7, \forall 1\le i\le 10.$$
I know the case that, for any pair of ...
- 2,007
7
votes
2
answers
217
views
Number of ways to distribute $n$ identical balls into $k$ identical boxes such that no box contains more than $m$ balls?
I wonder how to count the number of ways (algorithmically is fine) to distribute $n$ identical balls into $k$ identical boxes such that no box contains more than $m$ balls?
I've run into answers in ...
0
votes
1
answer
277
views
Number of possible combinations of X numbers that sum to Y where the order doesn't matters
I am looking for the number of possible outcomes given to a set of numbers X that sum to Y. This is the same issue as here. However, I would like to consider that (i) the numbers can't be repeated and ...
0
votes
2
answers
87
views
How many tuples of $(a,b,c)$ satisfies the following equation?
When $a,b,c,n\in \mathbb{Z} , a,b,c,n\geq0$ , $a+b+c\leq8n$
How many tuples of $(a,b,c)$ satisfies the following equation?
$a+2b+3c=12n$
I've tried with $n=1$ and there were 13 tuples, but I couldn't ...
user998872
4
votes
0
answers
269
views
Count the number of unique $N \times N$ binary matrices where every two rows or columns can be swapped
Suppose, two $n\times n$ binary matrices are $\it similar$ if one can be transformed to another by swapping any two rows or two columns any number of times.
My problem is: how many unique $n\times n$ ...
- 233
1
vote
1
answer
37
views
I want to obtain partition of an integer with an initial value and
I want to obtain a partition of an Integer with an initial value and
the value following it is smaller and the value following it is smaller than the previous value and no value repeats itself.
within ...
- 31
0
votes
0
answers
28
views
Number of partitions with limited cardinality [duplicate]
We are given $k$ urns labeled from $1$ to $k$. What is the number of ways to put $n$ indistinguishable balls into the $k$ (distinct) urns, given that each urn has a limited capacity equal to $c$, ...
- 149
1
vote
2
answers
1k
views
The number 3 can be written as $3$, $2+1$, $1+2$ or $1+1+1$ in four ways. In how many ways can the number $n$ be written?
Attempt
Let $x$ be any variable
$X+0=n ; X+Y=n ; X+Y+Z=n ; \dots; X+Y+Z+A+\dots=n$ (sum of n-1 terms); $1+1+1+.......+1=n$ (sum of n terms).
So total number of ways=
$$(n-1) C (1-1)+(n-1) C (2-1)+\...
- 85
0
votes
1
answer
58
views
Combination with Restriction and Repetition
I have a number $x$, let's say $5$, and I want to sort the number out into $4$ digits so that the sum of the digits is equal to $5$, but the value of each digit cannot exceed $3$. $0$ would be an ...
- 11
2
votes
1
answer
494
views
compositions of n into even parts
I have found here {https://math.stackexchange.com/questions/2167885/compositions-of-n-into-odd-parts} that the number of integer compositions of n into k odd parts would be ${\frac{n+k-1}{2} \choose k-...
- 311
3
votes
3
answers
763
views
Number of non negative integer solutions of $x+y+2z=20$
The number of non negative integer solutions of $x+y+2z=20$ is
Finding coefficient of $x^{20}$ in
$$\begin{align}
&\left(x^0+x^1+\dots+x^{20}\right)^2\left(x^0+x^1+\dots+x^{10}\right)\\
=&\...
- 8,338
0
votes
1
answer
307
views
Get combination of numbers that when added same as the given number
For a given number $n >0$ is there a way to get combination that add up to this number??
for example :
if $n=6$ then numbers that add up are $5+1,4+2,3+2+1$ so the combination is 3
if $n=4$ then ...
- 103
0
votes
1
answer
54
views
Applying boundary conditions to counting combinatorial question [duplicate]
I was trying to count the number of natural number solutions to the equation: $x_1 + x_2 + ... + x_{11} = 20$, such that $0 \leq x_i \leq 9$, for all $i \in \{1, ..., 11\}$.
I know how to apply the ...
- 2,663
2
votes
2
answers
272
views
Find a bijection between the $(n-1)$ paths and the $n$-paths which have no downramps of even length.
So here is the Question :-
A Dyck $n$-path is a lattice path of n upsteps $(x,y)$ $\rightarrow$ $(x + 1,y + 1)$ and $n$
downsteps $(x,y) \rightarrow (x + 1,y-1)$ that starts at the origin and never ...
- 314
2
votes
0
answers
63
views
Closed-form solution of sum over compositions?
I am interested in calculating a closed-form solution of the following sum over compositions $$ \sum_{\substack{n_1 + \dots + n_M = N \\ n_i \geq 1}} \dfrac{n_1^2 + \dots + n_M^2}{n_1(N-n_1)! \dots ...
3
votes
2
answers
577
views
How do you find the number of unique parts in a partition of an integer $n$ into $k$ parts?
Suppose I have an integer $n$ and I partition it into $k$ parts. The number of ways this can be done is given by $P(n,k)$, and it satisfies the recurrence relation:
$P(n,k) = P(n-1,k-1) + P(n-k,k)$
...
- 43
1
vote
1
answer
514
views
Combinatorial arguments for number of partitions of $n$ into $k$ distinct parts
Let $Q(n, k)$ be the number of partitions of $n$ into $k$ distinct, unequal parts. Prove $Q(n + {k + 1\choose 2}, k)$ is equal to the number of ways to partition $n$ into at most $k$ parts (parts can ...
user709945
1
vote
1
answer
208
views
Book Recommendations - Discrete Mathematics and Partitions of an Integer
I finished my first discrete math course this semester using mostly the excellent Kenneth Rosen (Discrete Mathematics and Applications) book that was a great help, especially in induction content and ...
- 529
0
votes
0
answers
26
views
Making a group of $p$ people with $n$ available nationalities
Making a group of p people using m out of n available nationalities can be one of these two scenarios;
$m \le p \le n$ or $m \le n \le p$.
Using p,m, and n, how to evaluate the number of ways of ...
- 5,450
0
votes
1
answer
42
views
Integer Partitions of $~n~$ with restrictions.
Provide a generic formula for the number of partitions of an even number $~n~$ where one part has even value and another part also has even value.
Is there some way to approach this problem that uses ...
- 529
2
votes
2
answers
80
views
Coefficient of Generating Function
Determine the coefficient of $~x^n~$ in:
$$(x^2 + x^4 + x^6 + ... + x^{n-1})(x + x^3 + x^5 + ... + x^{n-2})$$
Where $~n~$ is an odd number.
How to describe the possible combinations of coefficients ...
- 529
1
vote
1
answer
73
views
Number of partitions of $n$ with restrictions
Find the ordinary generating function for the number of partitions of n in which all parts are odd and none surpasses 7. My answer is:
$$\prod\limits_{i=1}^7 \frac{1}{1-x^{2i}}$$
She is correct?
- 529
0
votes
1
answer
70
views
Extraction of coefficient from Generating Function with partitions
Determine the coefficient of $~x ^ {15}~$ in:
$(1+𝑥^3+𝑥^6+𝑥^9+𝑥^{12}+𝑥^{15})(1+𝑥^6+𝑥^{12})(1+𝑥^9)$
How to use the fact that the desired coefficient is the number of partitions of 15 in parts ...
- 529
1
vote
1
answer
103
views
Partitions of an integer with polynomials
Determine the coefficients of the polynomial $$a_0 + 𝑎_1𝑥_1 + 𝑎_2𝑥_2 + 𝑎_3𝑥_3 + ⋯ + 𝑎_𝑟𝑥_𝑟$$ that has the property that $~𝑎_𝑛 = 𝑝~$ . Where $p$ is the number of partitions of $n$ composed ...
- 529
3
votes
2
answers
241
views
Ways of distributing passengers in ships
I need help with the following combinatorial problem. There are $ K $ passengers and $ K $ ships. The passengers are denoted by $ U_1, U_2, \dots, U_K $. The objective is to find in how many ways the $...
- 778
6
votes
0
answers
141
views
Faa di Bruno's formula and alternating functions
Suppose you have a function $f(x)$ such that ${\rm sgn}\Big(\frac{d^k}{dx^k}\big(f(x)\Big) = (-1)^k$ and a function $g(x)$ such that ${\rm sgn} \Big(\frac{d^k}{dx^k}g(x)\Big) = (-1)^{(k+1)}$, $\forall ...
- 251
0
votes
1
answer
126
views
What is the appropriate weight ($W_k$) (for two arbitrary partitions)?
I already asked a similar question, And from the answer I received, another question came to my mind.
A positive integer can be partitioned, for example, the number 7 can be partitioned into the ...
- 41
3
votes
1
answer
67
views
Is this true for every partitioning?
I have two categories (category1 and category2 ) and The size of both categories is equal to each other. if we partition each categories arbibtrary .Is this proposition proven? or rejected?
$n_T \...
- 41
1
vote
1
answer
125
views
How many different ways to pay $2018, using only quarters, dimes, nickels, and pennies?
I have seen solutions that show how this is done for amounts such as $1. Namely I consulted this webpage's explanation--
https://www.maa.org/frank-morgans-math-chat-293-ways-to-make-change-for-a-...
- 11
-1
votes
1
answer
69
views
Total Collections of integers that sum to constant
For a range of positive integers $1 - S$, how many collections of $N$ integers are there that their sum is a constant $S$.
Example:
Integers from $1$ to $100$
Collections of $4$ integers
Each ...
- 123
2
votes
1
answer
4k
views
Number of positive integral solutions of $a+b+c+d+e=20$ such that $a<b<c<d<e$ and $(a,b,c,d,e)$ is distinct
This is from a previous question paper for an entrance exam I am preparing for.
https://www.allen.ac.in/apps/exam-2014/jee-advanced-2014/pdf/JEE-Main-Advanced-P-I-Maths-Paper-with-solution.pdf (Link ...
- 53
0
votes
0
answers
70
views
Number of ways to partition $\{1,2,3, \dots, N\}$ into tuples where the size of no tuple exceeds $3$.
While it seems to me that the general answer is not going to be a neat formula, I really only need this for $N=4$ and $N=5$. I'm getting $61$ and $321$ respectively, but I'm not sure. Please help.
- 981
1
vote
1
answer
951
views
Coin Combinations for any given scenario.
I am trying to work out the number of scenarios I can cover with a given set of coin combinations so I can decide when I have the optimal amount of change to carry.
For the sake of the example, lets ...
- 325
6
votes
4
answers
672
views
How many times does $k$ occur in the composition of $n$?
How many times does the number $k$ occur in the composition of $n$?
Composition of Integer
In short, the difference between the partition of an integer and composition is the order of numbers. In ...
- 237
1
vote
1
answer
92
views
Integer composition in exactly $T$ parts with maximum addend constraint.
In how many ways an integer $N$ can be partitioned into exactly $T$ parts such that
$T = \lfloor N/K \rfloor + 1$
$N = A_1 + A_2 + \cdots+ A_T$ where order matters
$0 \lt A_i \leq K$
$ N \bmod K \...
- 237
2
votes
3
answers
1k
views
Number of ways of cutting a stick such that the longest portion is of length n
We are given a stick of length $L$ (say). We make cuts such that the longest piece is of length $n$ (say) at most.
What are the minimum number of pieces we will get and in how many ways this can be ...
1
vote
0
answers
157
views
Ways to arrange in a two dimensional array an increasing sequence
Given a $n\times m$ grid, which has the number 1 in the upper-left square and a positive integer $1\leq k\leq n+m-1$ in the lower right-square, I am trying to determine in how many ways can the ...
- 11
0
votes
0
answers
465
views
Restricted Composition
I am trying to find the number of compositions of a given number restricted by the numbers present in a subset.
I read that this is called A-Restricted Composition. where A is a set of numbers
...
0
votes
2
answers
240
views
Number of solutions using partitions for linear equation having restrictions
Here is a linear equation $$a+b+c+d=12$$ where $a,b,c,d$ are restricted to be greater than zero and less than or equal to 6.
How many set of positive integer solutions are possible using partitions ...
5
votes
1
answer
4k
views
How many permutations in S(n) have this particular type?
I'm working through the textbook A Course in Enumeration. In the section about permutations and Stirling numbers, I'm having trouble understanding problem 1.45. It is:
We fix $n \in \mathbb{N}$, and ...
- 468
1
vote
0
answers
52
views
Relation of relative numbers of (restricted) ways to distribute identical / distinct objects into distinct bins
If want to know if the following inequality holds for general values of $s \leq n \ll m$.
$$\frac{C_0(n,m,s)}{C_0(n,m)} \leq \frac{p(n,m,s)}{m^n}$$
$C_0(n,m) = \binom{n+m-1}{m-1}$ is the number of ...
- 63
0
votes
1
answer
82
views
Partitioning a Queue
Imaging a situation that we have n people in a queue and each people represent with number 1 and I want to partition the queue in smaller part, there are several ways to partition the queue.
For ...
- 135
3
votes
0
answers
112
views
Amount of combinations of sets summing to number
(Apologies for the confused arbitrariness here; I don't have experience in formal maths to make abstract my lay-person thoughts, but I've tried my best.)
I have $x$ identical but order-important sets ...
- 31
4
votes
1
answer
3k
views
How many ways to write a number $n$ as the product of natural numbers $\geq 2$?
I am looking for a closed form (or efficient algorithm) for $f(n)$, the number of ways in which $n$ can be written as a product of natural numbers $\geq 2$. Note that $f(n)=\sum_{i=1}^{\Omega(n)}{g(n,...
- 535
3
votes
2
answers
549
views
Integer partitioning
Suppose we have an integer $n$. I we want to partition the integer in the form of $2$ and $3$ only; i.e., $10$ can be partitioned in the form $2+2+2+2+2$ and $2+2+3+3$.
So, given an integer, how to ...
- 133
1
vote
0
answers
697
views
Counting problem of combinations of symmetric matrix.
Given, a symmetric $n*n$ matrix $G$ with 0,1 entries. Each row of has same number of 1. $G$ is arranged in a certain order using a rule. The rule is described below-
$G$ is partitioned in to two sub ...
- 499
0
votes
1
answer
78
views
Counting resticted partitions of a multiset with additional restrictions
Say I have some multiset of integers, for example $M1=\{6,6,4,4,4,2,2\}$.
I have a second multiset that consists of some set of valid sums derived from picking without replacement from $M1$, say for ...
- 255
1
vote
2
answers
177
views
A father has nine identical coins to give to his three children. How many total allocations are possible?
There's three parts to this question:
How many total allocations are possible? (This one I understand -- it's ${11 \choose 9}$ because it's unordered with replacement.)
How many allocations are ...
- 545
33
votes
5
answers
57k
views
Counting bounded integer solutions to $\sum_ia_ix_i\leqq n$
I want to find the number of nonnegative integer solutions to
$$x_1+x_2+x_3+x_4=22$$
which is also the number of combinations with replacement of $22$ items in $4$ types.
How do I apply stars and bars ...
