Questions tagged [integer-partitions]
Use this tag for questions related to ways of writing a positive integer as a sum of positive integers.
196
questions
0
votes
1
answer
196
views
Different flag signal questions
How many different signals can be created by lining up 9 flags in a vertical column in 3 flags are white, 2 are red, and 4 are blue? Is it 9 choose 3 * 6 choose 2 * 4 choose 4?
- 241
0
votes
2
answers
490
views
How many different ways are there to make n dollars with 1, 5, 10, 25, and 50 cent coins. [closed]
I am trying to figure out a formula for how many different ways you can make n American dollars with pennies, nickels, dimes, quarters, and half dollars. There has to be a formula for this, right? I ...
0
votes
0
answers
77
views
Factoring an integer $N$ using its random partition of length $3$
While working on this MSE question that I had posted, I wondered what would be a minimal base of numbers that we could work with the algorithm described in that question.
I conjectured that a ...
- 3,341
0
votes
1
answer
1k
views
Partitions of $n$ into $k$ blocks, without single blocks.
So I'm trying to come up with a recursive formula $f(n)$ which counts the number of all partitions of $[n]$ into $k$ identical blocks, where the number of elements in each box is more than 1.
What i'...
- 2,718
0
votes
0
answers
612
views
Number of ways to divide a stick of integer length $N$, take 2
This is a follow up and motivated by this question, Number of ways to divide a stick of integer length $N$,
Suppose we have a stick of integer length $N$. I'm looking for (preferably closed-form) ...
0
votes
3
answers
735
views
Partition an integer $n$ by limitation on size of the partition
According to my previous question, is there any idea about how I can count those decompositions with exactly $i$ members? for example there are $\lfloor \frac{n}{2} \rfloor$ for decompositions of $n$ ...
- 197
0
votes
5
answers
4k
views
0
votes
2
answers
198
views
Natural Boundary of Euler's Partition Generating Function
Let $\mathbb{D}=\{z\in\mathbb{C}:|z|<1\}$. Let's consider the analytic function $f:\mathbb{D}\to\mathbb{C}$ given by, for all $z\in\mathbb{D}$,
$$f(z)=\prod_{n=1}^\infty (1-z^n)^{-1}.$$
For each ...
user180579
0
votes
1
answer
260
views
Number of integer $k$-tuples with sum $n$? [duplicate]
I wish to know how many elements are there in the set
$$
S_{n,k} = \left\{(n_1,\ldots, n_k): \forall i,n_i \in \mathbb Z, n_i \geq 0, \sum_i n_i = n\right\}.
$$
It appears to me that we have a simple ...
- 7,544
0
votes
2
answers
681
views
Partition function and Fibonacci n-th number upperbound
i need to proof this upperbound:
"Call $p(n)$ the number of partitions of n (integer) and $F_n$ the $n-th$ Fibonacci number. Show that
$p(n)\leq p(n-1) + p(n-2)$ and that $p(n)\leq F_n$ for $n\...
- 11
0
votes
1
answer
176
views
Partition Proof Using One-to-One Correspondences
Let $g(n,k)$ be the number of partitions of $n$ into exactly $k$ parts, in which no part is a $1$. Show that
$$g(n,k) = g(n-2,k-1) + g(n-k,k).$$
I know that the solution involves a one-to-one ...
user359548
0
votes
0
answers
224
views
Expected number of parts of a uniformly selected partition of $n$
I have a very basic question on partition theory, which I feel should be very well known. Suppose that you fix a natural number $n$ and select a random partition $P$ of $n$ by choosing uniformly from ...
- 469
0
votes
0
answers
53
views
Clarification of the proof of Euler's identity regarding the generating function for partitions.
In reference to this question which I asked here couple of days back but didn't get any answer I am posting this question to clarify whether we can able to extend Euler's identity regarding the ...
- 2,013
0
votes
2
answers
870
views
Partitions of a number with greatest product
For $n\in\mathbb{N}$ choose $k_1,\dots,k_l\in\mathbb{N}$ so that $\sum_{i=1}^{l}k_i = n$. Set $k = \prod_{i=1}^{l}k_i$.
What is the largest $k$ that one can get? Is there an explicit formula?
What ...
- 71
0
votes
1
answer
416
views
Counting functions and stirling numbers
Let S= { f | f: A $\rightarrow$ B, |Image(f)|=k}.
|A|=m, |B|=n.
where k $ \le n, k \le m $
|S|=$ {n \choose k} $ S(m,k) k!.
where S(m,k) are the striling numbers of the second kind.
What I can't ...
- 469