All Questions
Tagged with integer-partitions recurrence-relations
20
questions
0
votes
0
answers
58
views
How to define initial values for recurrence relation
I was given the following problem : let $f(n,k)$ be the number of possible partitions of $n$ into $k$ different non-negative integers. Find a recurrence relation and initial values for $f(n,k)$.
So I ...
6
votes
3
answers
148
views
The number of partitions of $\{1, \ldots, n+1\}$ into subsets of nonconsecutive integers
For each integer $n$, let $a_n$ be the number of partitions of $\{1, \ldots, n+1\}$ into subsets of nonconsecutive integers.
I found (by listing) that $ a_1, a_2, a_3, a_4$ are $1, 2, 5, 15$ ...
- 721
3
votes
2
answers
94
views
Homogeneous and inhomogeneous recurrences for a sequence
Some integer sequences have both homogeneous and inhomogeneous recurrence relations. If you know one, are there techniques for figuring out the other? (Or seeing if the other exists?) Below is an ...
- 2,322
0
votes
1
answer
40
views
Unable to understand the base cases for this recurrence relation: DPn = DPn-1 + DPn-3 + DPn-4
I read the following here
Sub-problem: DPn be the number of ways to write N as the sum of 1, 3, and 4.
Finding recurrence: Consider one possible solution, n = x1 + x2 + ... xn. If the last number is 1,...
0
votes
1
answer
83
views
Recurrence relation for partitions of n into parts of size either 1 or 2
Let $p_n$ be the number of partitions of n into size either 1 or 2, and by definition take $p_0=1$. For example, one such partition of 5 is $5=2+2+1$. I have been given that the generating function ...
- 359
0
votes
1
answer
93
views
Prove combinatorially the recurrence $p_n(k) = p_n(k−n) + p_{n−1}(k−1)$ for all $0<n≤k$.
Recall that $p_n(k)$ counts the number of partitions of $k$ into exactly $n$ positive parts (or, alternatively, into any number of parts the largest of which has size $n$).
- 31
0
votes
1
answer
129
views
Let g_n equal the number of lists of any length taken from {1,3,4} having elements that sum to n.
For example, g_3 = 2 because the lists are (3) abd (1,1,1). Also g_4 = 4 because the lsits are (4), (3,1), (1,3), and (1,1,1,1). Define g_0 = 1.
(a) Find g_1, g_2, and g_5 by complete enumeration.
(b) ...
- 61
-2
votes
2
answers
80
views
How many ways can you express an integer as the sum of positive integers and each sum does not include any 2s? [closed]
I came up across this question while self-studying combinatorics. I am supposed to derive a recurrence relation, however I am not sure how to approach or even start this problem. The order matters.
2
votes
0
answers
126
views
Show that the Stirling numbers of the second kind satisfy the recurrence:
I need help satisfying this recurrence. Thanks in advance!
Show that the Stirling numbers of the second kind satisfy the recurrence:
$$ S(k,n) = \sum_{i=1}^k S(k-i, n-1) {k-1 \choose i-1} $$
I think a ...
- 39
0
votes
1
answer
199
views
Recurrence relation related to integer partition
I have to prove a recurrence relation which is given by:
$p_{(n,S)} = \displaystyle\sum_{t=0}^{\lfloor \frac{n}{s} \rfloor}$${p_{(n − st , S-\{s\})}}$
assuming that $\{s\}$ is an arbitrary fixed ...
- 997
13
votes
2
answers
2k
views
Number of ways to represent any N as sum of odd numbers? [duplicate]
I was solving some basic Math Coding Problem and found that For any number $N$, the number of ways to express $N$ as sum of Odd Numbers is $Fib[N]$ where $Fib$ is Fibonnaci , I don't have a valid ...
- 512
4
votes
1
answer
197
views
How many trees with height $h$ are there?
Given $n, h\in\Bbb{N}$, let $f(n, h)$ be the number of rooted trees with $n$ vertices and height $h$. How can we compute $f$?
Let's denote by $r$ the root of a tree. Here, the height of a tree is the ...
- 3,871
0
votes
1
answer
250
views
Generating Function of Integer Partitions
Let $p_{k}(n)$ be a number of partitions of $n$ that into parts not greater than $k$.
$p_{k}(n)=p_{k-1}(n)+p_{k}(n-k)$
i will prove this partition recurrence bu using Generating Functions of ...
- 421
0
votes
1
answer
2k
views
Number of all compositions of a odd number into j(odd number) of odd parts.
Given m,j are odd positive integers. Find a closed form formula for the number of all compositions of m into j odd parts?
Attempt: If m=2+x, then x is odd and we have to find x into odd parts.
If m $\...
- 860
14
votes
3
answers
20k
views
Integer partition of n into k parts recurrence
I was learning integer partition of a number n into k parts(with minimum 1 in each part) and came across this recurrence :
part(n,k) = part(n-1,k-1) + part(n-k,k)
...
- 175