5
votes
Accepted
The number of partitions of $\{1, \ldots, n+1\}$ into subsets of nonconsecutive integers
Write the numbers out 1-2-3-...-n-(n+1). For each "link" j-(j+1) introduce the set $A_j$ of those set partitions where ...
- 9,763
4
votes
Accepted
$(w_{1},w_{2},w_{3},\dots,w_{7})$ integers with $20\le w_{i} \le 22$ such that $\sum_{i=1}^{7}w_{i} = 148$
You have again double counted, because it's possible for two of the $p_i$ to be larger than $2$. So you need one more level of inclusion-exclusion:
There are $\binom 72 = 21$ ways to pick two indices ...
- 201k
4
votes
The number of partitions of $\{1, \ldots, n+1\}$ into subsets of nonconsecutive integers
Here, I give a bijective proof that $a_n=B_{n}$.
Let $P$ be an arbitrary partition $\{1,\dots,n\}$. We will use $P$ to produce a partition $Q$ of $\{1,\dots,n+1\}$, where every part of $Q$ is made of ...
- 78.3k
3
votes
The number of partitions of $\{1, \ldots, n+1\}$ into subsets of nonconsecutive integers
The following solution is a detailed version of ploosu2 above.
We recall the following equality for the Bell number (see the link here)
$$B_{n+1}=\sum_{l=0}^n\binom{n}{l}B_l.$$
According to the ...
2
votes
$(w_{1},w_{2},w_{3},\dots,w_{7})$ integers with $20\le w_{i} \le 22$ such that $\sum_{i=1}^{7}w_{i} = 148$
Given the small number of solutions I would find it easier to calculate the number of $(p_1,p_2,\dots, p_7)$ directly, so I offer this as an alternative approach.
There are
$\binom{7}{3}\binom{4}{0}\...
- 14.7k
2
votes
Confusion between relation of stars and bars and q-binomial coefficient
This isn't true. If we look at the case $t=3, m=2$ then the first polynomial is
$$(1+x+x^2)(1+x+x^2)=1+2x+3x^2+2x^3+x^4$$
whereas the second polynomial is
$$(1+x+x^2)(1+x^2)=1+x+2x^2+x^3+x^4$$
The ...
- 21.9k
2
votes
Generating function and currency
Thank you Gerry Myerson
I find the sequence $a_n$ for the G.f.: $$\frac{1}{(1-x)(1-x^3)(1-x^4)}$$
$1, 1, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 15, 17, 18, 20, 22, 24, 26, 28, 30, 33, 35, 37, 40, ...
- 37
2
votes
Accepted
On $(0,1)$-strings and counting
If the total number of $1$ digits is $2^k,$ then we can group the ones digits as $1+1+2+4+\dots+2^{k-1}$ in $k+1$ places, with one zero after, and $n-2^k-1$ zeros out after $1,1,2,\dots,2^{k-1}.$ This ...
- 178k
Only top scored, non community-wiki answers of a minimum length are eligible