All Questions
Tagged with integer-partitions combinations
52
questions
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 ...
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 ...
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
6
votes
0
answers
142
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
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
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
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
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
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
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
3
votes
1
answer
1k
views
What is the count of the strict partitions of n in k parts not exceeding m?
Lets say we had a $k,m,n \in \mathbb{N}$ where $k < m \le n$. How many different sets $X_1,..,X_m$ with $|X_i|=k$ for $i=1,..,m$, where the sets do not include duplicates, for which the sum of ...
- 43
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
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
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
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