Questions tagged [combinatorics]
For questions about the study of finite or countable discrete structures, especially how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.
6,903
questions
0
votes
1
answer
880
views
Number of compositions of $n$ into $k$ parts with each part at most $1$
I am trying to figure out a formula for the number of compositions of $n$ into $k$ parts with each part at most $1$.
I know that the number of compositions of $n$ into $k$ parts is $\binom{n+k-1}{k-1}...
0
votes
1
answer
1k
views
Finding number of subarrays not including certain pairs
How many contiguous subarrays of an array exist such that they do not contain certain pairs of positions of the array?
For eg. if array ={11,22,33,45}
and if we do not want to include say position ...
- 133
0
votes
2
answers
168
views
Binomial probability with selective reflipping
What is the probability of having exactly k successes from n coins if all n coins are flipped and there are x successes, then n - x coins are re-flipped to give the additional k - x successes?
...
- 146
0
votes
1
answer
47
views
PMF of random variable|Expectation|A.Hayter 4th edition
my question is as follows->
A consultant has six appointment times that are open, three on Monday and three on Tuesday. Suppose that when making an appointment a client randomly chooses one of the ...
- 145
0
votes
1
answer
170
views
Number of elements in cartesian power with a maximum constraint
Problem: I would like to know the number of elements in the cartesian power $X^n$ (cartesian product of one set $X$ by itself, $n$ times) with a maximum constraint: how many elements in $X^n$ have ...
- 139
0
votes
2
answers
370
views
Deduce formula for $\sum_{j=0}^m {m \choose j}(-1)^j j^{m+1}$
I am working on the following problem:
For each $m$ we have found the values of
$$\sum_{j=0}^m {m \choose j}(-1)^j p(j)$$
for polynomials of degree at most m.
Use a combinatorial story to ...
- 1,207
0
votes
1
answer
76
views
Distribution of number of drawings to empty the box of balls?
Say I start with a box of $n$ balls. At each step, I remove some $k$ balls, where $k$ is from the discrete uniform distribution ${\mathcal {U}}\{1,b\} $ where $b$ is the number of balls present in the ...
- 517
0
votes
2
answers
1k
views
Is there an equation for permutations with different numbers of element available?
For example, if we are to arrange the four letters A , B , C and D, by permutation we know that there are 4! = 4 * 3 * 2 * 1 = 24 ways available. But if we have 2 of each letters and are still to ...
- 35
0
votes
1
answer
423
views
Complete Directed Graph Indegree and Outdegree summations
Let the indegree of a vertex $v$ be $i(v)$ and the outdegree be $o(v)$. Consider a single tournament (a directed graph obtained by assigning a direction for each edge in an undirected complete graph) ...
0
votes
1
answer
1k
views
$h_n=3h_{n-1} -2,\ (n\geq{1}); \ h_0=1$
Solve the nonhomogeneous recurrence relation.
$h_n=3h_{n-1} -2,\ (n\geq{1}); \ h_0=1$
so, $h_n-3h_{n-1}=-2$
I'm doing this by generating functions
$$g(x) = h_0+h_1x+h_2x^2+h_3x^3+...$$
$$-3x\ g(x)= ...
- 317
0
votes
2
answers
301
views
the limit of infinite product $(1+y)(1+y^2)(1+y^3)(1+y^4)\cdots $
I wonder if the function $(1+y)(1+y^2)(1+y^3)(1+y^4)\cdots, 0< y<1$, converges to some well-known function.
If we let $ (1+y)(1+y^2)(1+y^3)(1+y^4)\cdots = \prod_{i=1}^\infty (1+y^i) =
\sum_{i=...
- 20.1k
0
votes
0
answers
95
views
How to prove an approximation of a combinatorics identity
How to prove that $$\sum_{k\ge 0} \binom{n}{rk} =\frac{1}{r}\sum_{j=0}^{r-1}(1+w^j)^n$$ can be approximated as $\frac{2^n}{r}$, where $n\ge 0$, $r\ge 0$, $n>r$, $w^r=1$.
For example, $$(1 + 1)^n + ...
- 361
0
votes
4
answers
12k
views
In how many possible ways can we write $3240$ as a product of $3$ positive integers $a$, $b$ and $c$?
In how many possible ways can we write $3240$ as a product of $3$ positive integers $a$, $b$ and $c$?
This is the question where I've been stuck. The answer is $450$, but I don't know why. I've ...
- 31
0
votes
0
answers
66
views
Generate all Non-Covered Boolean Matrices with N rows
I am attempting to generate all non-covered (or irreducible) boolean (or binary, zero-one, etc.) matrices for a given $n$ columns.
For instance, given $n$ = 2, the possible non-covered boolean ...
- 103
0
votes
4
answers
222
views
Proving that for finite sets $m(A \cup B)=m(A)+m(b)-m(a \cap B)$; what is a good level of rigor?
I saw this exercise in Herstein's Abstract Algebra. I can do two proofs:
Non-rigorous "proof" with words:
To find $m(A \cup B)$, we can try adding $m(A)$ and $m(B)$. But any element which is in $A \...
- 23.9k