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.
59,231
questions
-4
votes
1
answer
35
views
Venn diagram 4 set
Could someone post how to solve a Venn diagram?
For example:
The students studied:
$20$ English
$20$ Math
$15$ History
$12$ French
$2$ Math and english
$2$ Math and history
$2$ Math, history and ...
3
votes
0
answers
32
views
What is the formula for $P_{n}^{k} (a_{1}, a_{2}, ...)$, defined by Peter Luschny?
Recently, I was reading a blog called The P-transform by Peter Luschny (https://oeis.org/wiki/User:Peter_Luschny/P-Transform#.E2.99.A6.C2.A0P-polynomials), where the following formulas are given
The ...
- 91
1
vote
1
answer
47
views
box office problem generalization
When doing combinatorics, I found the box office problem very interesting:
Assume that the box office has no changes initially, with $n$ customers having 5-dollar bills and $n$ customers having 10-...
- 13
-2
votes
0
answers
47
views
Combinatorics with Cards
We have standard 52-card deck, How many ways can arrange 21 cards in a row, where exactly 7 of them are hearts, 5 of them are diamonds, 5 of them are clubs, and 4 of them are spades?
My solution (I ...
- 1
4
votes
0
answers
33
views
What is the current best algorithm to find if a simply connected region is uniquely tileable with dominoes?
I was reading both Thurston's and Fournier's papers on algorithms which detect whether or not a simply connected region is tileable using dominoes (1 by 2 rectangles) when I came across the section in ...
- 415
2
votes
0
answers
33
views
Realized graph of majority of permutations
For any collection of permutations of $\{1,2,\dots,n\}$, we say that it realizes a directed multigraph with $1,2,\dots,n$ as vertices, such that there is an edge from $i$ to $j$ if $i$ appears before $...
- 2,369
0
votes
0
answers
33
views
Change order of summation
I need to change the summation order in the sum:
$$
\sum\limits_{n=0}^{\infty} \sum\limits_{k=0}^{ n m } F(k, n - mk)
$$
In Srivastava's book, I came across a similar formula
\begin{array}{c}
\sum\...
- 8,194
0
votes
0
answers
12
views
Number of 2-connected components in an almost 2-regular 3-uniform hypergraph
Notation: $[n]:=\{1,\ldots, n\}$, and $\binom{[n]}{k} := \{A \in 2^{[n]}\mid |A| = k\}$ for $k \in [n]$.
Let $M$ be a perfect matching on an even number of vertices $n$, and let $\mathbb{S}_n$ be the ...
- 479
-3
votes
0
answers
36
views
Drawing tickets without replacment until same number appears twice [closed]
8 tickets are in a box. Two are marked 1, two are marked 2, two are marked 3, and two are marked 4. Tickets are drawn randomly from the box without replacement until a number appears twice. What will ...
2
votes
1
answer
69
views
Understanding of Ramsey theorem
Ramsey’s Theorem:
Example: Take a set $S$ of $n$ elements. Construct all $3$-tuples.
Color each $3$-tuple with one of $4$ colors (blue, green, red, orange)
$S = \{1,...
- 123
-1
votes
0
answers
16
views
How can one stack a set of crosswords vertically to get the maximum number of valid words? [closed]
A set of m crosswords (mxm) are to be stacked vertically. It's possible that the letters of the crossword solutions in xy plane, shall align along the z-axis to form new words.
Suggest an algorithm to ...
0
votes
0
answers
28
views
What is the number of integer sequences of length $T$ with fixed endpoints?
Let $T, n_1, n_2 \in \mathbb{Z}$ s.t. $T \geq 1$ be fixed. Consider the set
$$\mathcal{P}(0, T - 1, n_1, n_2) = \Big\{x:\{0, 1, \dots, T - 1\} \to \mathbb{Z} \space \Big| \space \big(x(0) = n_1\big) \...
- 429
3
votes
0
answers
113
views
Counting words that agree at some place with each of their cyclic permutations
Let $a(m,n)$ be the number of words $W$ of length $m$ in an alphabet of $n$ letters, which have the property that each cyclic permutation of $W,$ has the same letter as $W$ in some place.
For example, ...
- 261
0
votes
0
answers
33
views
Ordered 4-tuples with sum less than $k$
Consider the sum
$$
\begin{align}
S=\sum_{i=0}^\infty\sum_{j=0}^\infty\sum_{n=0}^\infty\sum_{k=n+i+j}^\infty\:C(i,j,n,k)\cdot\epsilon^k
\end{align}
$$
with some generic, non-symmetric coefficients $C(...
- 165
1
vote
0
answers
60
views
Finding formula for $a+b+c=n$ where $(a,b,c)$ are positive integers.
I'm currently studying a book by Paul Zeitz and currently stuck on exercise 6.2.23, below is the problem:
Find a formula for the number of different ordered triples $(a,b,c)$ of positive integers ...
- 157