This tag is for basic questions about the study of finite or countable discrete structures — specifically 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. ...

learn more… | top users | synonyms (4)

1
vote
3answers
32 views

Number of ways of walking up stairs and Recurrence relation

Suppose you want to walk up a staircase of $6$ steps, and can take $1, 2$ or $3$ steps at a time. How many ways are there to walk the $6$ steps? It seems hard to count the number of ways of walking ...
2
votes
0answers
26 views

Ehrhart polynomial of lattice tetrahedrons in $\Bbb{R}^4$

Let $\lbrace v_1 , v_2, v_3 , v_4 \rbrace \subset \Bbb{Z}^4$ be linearly independent, and denote by $P$ the convex hull of this set. Now, $P$ is a 3-polytope residing in four-dimensional space. What's ...
1
vote
3answers
52 views

Question regarding permutations and combinations?

Hi, I was just wondering on how you are supposed to approach this question. I keep getting 114 as an answer, but the answers say it is 174. How would anyone do this question, because I feel like I'm ...
1
vote
1answer
134 views

What is the count of the strict partitions of n in k parts not exceeding m?

Lets say we had a $k,m,n \in \mathbb{N}$ where $k < m \le n$. How many different sets $X_1,..,X_m$ with $|X_i|=k$ for $i=1,..,m$, where the sets do not include duplicates, for which the sum of ...
15
votes
1answer
2k views

Why are there only a few known Ramsey numbers?

Can someone explain in a simple way, why there are so few known exact Ramsey Numbers? I guess it's because there are no efficient algorithms for this task, but are there so many combinations to test? ...
9
votes
1answer
95 views

Blocking lines of length $5$ in a $7 \times 8$ matrix; how can we know the solutions have a specific form?

A friend shared with me the following puzzle he encountered in a Chinese math competition: In a $7 \times 8$ matrix, we place tokens so that any straight line of length $5$ (horizontal, vertical, ...
7
votes
1answer
81 views

The rows continue to be different to each other

In each position of an $n \times n$ matrix there is a number. We know that all the rows of the matrix are different from each other. Show that we can delete a column so that the rows of the matrix ...
2
votes
1answer
93 views

Tough combinatorics problem

We have an urn containing $n_a$ tiles labelled "A", $n_b$ ones labelled "B", and $n_c$ tiles labelled "C". We also have a string of letters consisting of $s_a$ occurrences of the letter "A", $s_b$ ...
3
votes
1answer
71 views

Counting possible combinations to open a lock( 2006 ACM ICPC)

I was working on a problem in a coding competition and I began to wonder about the analytical (mathematical) solution to this problem. I am not even sure how to go about counting this. Any ideas will ...
1
vote
1answer
40 views

How many combinations can be made with these rules? (game of Dobble) [duplicate]

The game called Dobble consists of a deck of cards; each card contains 8 symbols from a set of 50. The deck is made so that any two cards have exactly one symbol in common. (The idea of the game is ...
0
votes
2answers
76 views

please help me ( probabilities )

please let me know if my answer true or false Three numbers are chosen at random without replacement from the set {0, 1, 2, 3, ... , 10}. Calculate the probabilities that for the three numbers drawn ...
0
votes
1answer
26 views

Linear Constraints Solution Existence

how can one decide if $$A*t\ge b$$ $A$ is a Matrix with integer Entries and $t$ is a Vector with integer Entries, $b$ is a fixed Vector with integer Entries exists?
1
vote
2answers
35 views

Counting exercises - Solution verification.

i'm studying some combinatorics and i came up in the following exercises. Suppose we are given a set $U$ of $n$ elements. Suppose $A \subset U$ has $k$ elements. Determine the number of subsets ...
0
votes
1answer
26 views

Finite sum equaling Kronecker Delta

could anyone help understand how $$\sum_{j=0}^{n-r}\binom{n-r}{j}*(-1)^{j} = [1 + (-1)]^{n-r}$$ I see that if $j=0$, i get $1=1^{n-r}$, and if $j=n-r$, i get $(-1)^{n-r},$ but what about the rest of ...
0
votes
1answer
74 views

How to find out the number of ways to solve Instant Insanity

Problem : We are given 4 cubes. The 6 faces of every cube are variously colored - Blue, Green, Red or White. Stack the cubes on top of another in such a way that no color appears twice on any of the ...
0
votes
1answer
27 views

Small remarkable matroids

I'm working on a problem involving matroids $M=(E,\mathfrak{C})$ (here $E$ is the ground set, $\mathfrak{C}$ the set of circuits) with a "small" ground set $E,$ in the sense that $\sharp(E)\leq7$ I ...
3
votes
0answers
31 views

Does there exist Latin square critical sets for which deleting any entry results in arbitrarily many completions?

For those familiar with Latin squares terminology, I'll get straight to the point: Q: For all $N \geq 2$, does there exists a critical set $C$ (for a Latin square of any finite order) such that ...
5
votes
2answers
54 views

Putting objects in a line.

I'm working on a project outside of school, and I've run into a bit a problem. I thought, maybe there are some problem solvers on the internet who would enjoy this. I have 8 balls, 3 red cubes, and ...
2
votes
2answers
55 views

The Weyl group of A_3

Could someone please list all elements of the Weyl group of the root system $A_3$ in terms of simple reflections. In this case the Weyl group is $S_4$. Its strange that GAP failed to list all elements ...
0
votes
0answers
30 views

Inversion and permutations

Let call two arrays A and B with length n almost equal if for every i (1 <= i <= n) CA(A[i]) = CB(B[i]). CX[x] equal to number of index j (1 <=j <= n) such that X[j] < x. For two ...
1
vote
1answer
41 views

Examples of Matroids

Preparing an exam, I'm looking for examples of matroids and maybe hints or references on proves that they are. (what I already know are representable matroids and graphic matroids)
4
votes
1answer
38 views

Chromatic number of generalized hypercube

It's clear that the chromatic number of $Q_n$ is $2$. But what about the graph $G$ with vertex set ${n}^{(r)}$ where two vertices are adjacent if and only if their coordiantes differ by one? Can't ...
-1
votes
2answers
28 views

common multiple polynominal time

Given $n$ rational numbers. Is there a polynominal time algorithm to compute a common denominator? My idea was for each number search for $k_i$ so that $k_i \cdot n_i$ is integer. Then the solution ...
1
vote
1answer
73 views

Expected value over many trials

I am a poker player and was talking to my friend about expected value. He claimed that if you play far enough above your bankroll, expected value can be negative, even if you have a skill edge. I ...
0
votes
1answer
30 views

combinatorics for buying a new car

Question: Mindy is buying a new car. for the car she has selected the following options are available: power windows, a sunroof, and leather interior. if she must select one or more of these options, ...
0
votes
1answer
33 views

Counting Problems with n-Bit Strings

I'm a little confused with problems regarding n-bit strings- for instance if we are considering the number of n-bit strings of size n with a 1001 pattern, why is it alright to consider only adding ...
0
votes
0answers
57 views

Showing that two sums are equivalent

given \begin{gather} U_d(x,y,q\mid i_1,\ldots,i_k)=\sum\limits_{n,m\geq0}x^ny^m\sum\limits_{\sigma = i_1\ldots i_k\sigma_{k+1}\ldots\sigma_m\in C_{[d]}(n,m)}q^{v(\sigma)}. \end{gather} show ...
0
votes
1answer
30 views

Probability of their's constituting a triangle? [duplicate]

We have a line segments with length $l$ then you choose two random points and cut it from these points so that we have three piece of line segments. What is the probability that these piece ...
2
votes
4answers
77 views

How to approach this type of combinatorics problems

Say we have a $16$ letter long word consisting only of $\{a,b,c\}$. How many possible words are there in which the letter $c$ appears $4$ times but there are no $2$ $c$'s next to one another? For ...
-1
votes
1answer
44 views

Probability of 1 at both end of string

Given a string S having N characters long and consists of only 1s and 0s. Now given an integer K, let us pick two indexes i and j at random between 1 and N, both inclusive. What's the probability ...
0
votes
0answers
39 views

The sum of palindromes from 100 to 900

I'm working with palindromes from $100-999$. I'm having trouble with the step highlighted in red. Can someone explain the algebra to me? Taken from: Discrete and Combinatorial Mathematics: An ...
4
votes
0answers
131 views

Select 100 integers from 1,2,…,200

Prove that if 100 integers are chosen from 1,2,...,200, and one of the integers chosen is less than 16, then there are two chosen numbers such that one of them is divisible by the other. Thanks in ...
2
votes
2answers
50 views

Fair Coin Flips

Michele flips a fair coin nonstop. Two students, Thomas and George, decide to make a bet about whose sequence of flips will occur first from the moment they begin observing the results of ...
1
vote
1answer
39 views

Points in a triangle: Pigeon-hole Principle

There are five points inside an equilateral triangle of side length 1. Show that at least two of the points are within 1/2 unit distance from each other. I understand that you can break this triangle ...
2
votes
3answers
188 views

Wheel of Fortune Problem

The Summation formula is $$\sum_{i=1}^ni =\frac{n(n+1)}2$$ How is it that we know the integers $1,2,...36$ appear exactly $3$ times. And why do we multiply the sum by $3$ in the last part of the ...
0
votes
0answers
49 views

How to determine if a convex polytope is contained in a union of convex polytopes?

Given that we are in a Euclidean space of dimension d, that we have a bounded convex H-defined polytope P, and N possibly unbounded convex H-defined polytopes, I am looking for an "efficient" ...
2
votes
1answer
58 views

Count 1-bit in binary integers

Given an integer range [A,B], (1) What’s the probability to get a 1-bit if we first randomly choose a number x in the range and then randomly choose a bit from x? (2) What’s the expected number of ...
1
vote
1answer
83 views

How can I divide 30 people into 6 different groups of 5 people in 6 ways so that no two groups share two people?

I have a group of 30 people that I need to divide into 6 groups of 5 people in 6 different ways, however I do not want the same people to be together twice. I already have 5 ways written down, but I ...
2
votes
2answers
18 views

Probability distribution of selecting combinations of green and yellow balls from a set of green/yellow/red

Let's say I have G green balls, Y yellow balls and R red balls. I'm interested in ...
2
votes
1answer
31 views

What is Vandermonde's formula with multisets?

I need Vandermonde's formula in multi-set form. I modified the original formula but I get a mess with too many letters everywhere, is there a nice representation? Here's the original: $$ ...
-1
votes
0answers
58 views

Sum of possible permutations

Lets call two arrays A and B with length n almost equal if for every i (1 <= i <= n) CA(A[i]) = CB(B[i]). CX[x] equal to number of index j (1 <=j <= n) such that X[j] < x. For two ...
6
votes
1answer
47 views

Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs?

Following on from this question: Q: Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs? or equivalently Q: Does there exist a $15 \times 15$ matrix ...
5
votes
2answers
127 views

How to count different card combinations with isomorphism?

Let's consider a standard deck of cards and say that two sets of cards are isomorphic if there exists permutation of colors that makes one set into another. For example: ...
0
votes
0answers
39 views

How many Euler diagrams with $n$ sets exist?

Does anyone have any thoughts on this? I have been struggling with it and I'm not sure if it's a hard problem, or easy and I'm just not getting it? For $n=2$ sets (say $A$ and $B$), it's obviously 4: ...
2
votes
1answer
57 views

How many elements of order 4 does $S_6$ have?

I am trying to count the number of elements of order 4 in $S_6,$ but my answer is not matching the one in the back of the book. Here's my attempt: Such elements are either of the form $(6543)(21)$ ...
0
votes
1answer
27 views

Basic graph theory matching question — I don't understand the answer to this

We generalize the idea of matching in Example 1 to arbitrary graphs by defining a matching to be a pairing off of adjacent vertices in a graph. For example, one possible matching in Figure 1.1 is a-b, ...
7
votes
0answers
122 views

Infinite sum involving $q$-adic representations of whole numbers and $q$-factorial numbers

Let $q \in \mathbb{N}_{\geq 2}$. For $n \in \mathbb{N}_0$, let $$\mathrm{fac}_q(n) := \prod_{i=1}^n (1+q+\dots+q^{i-1}) = \prod_{i=1}^n \frac{q^i-1}{q-1}$$ be the $q$-factorial of $n$. In particular, ...
0
votes
1answer
28 views

asymptotic notation rearrangment

I'm having a look at this paper http://arxiv-web3.library.cornell.edu/pdf/0903.3048v1.pdf namely Theorem 5 and why it implies Theorem 2 immediately. Basically, I'm hoping somebody could explain to ...
4
votes
4answers
406 views

Probablity that 3 husbands sit next to their wives round a circular table

There are 3 couples sitting randomly round a 6-seater circular table. What is the probability that all the husbands and wives sit next to each other? My attempt: First wife, say, takes any of the ...
-1
votes
1answer
57 views

Quick Truth Table in Logic Problem

Suppose We Have: How can quickly detect how many "1" are in the truth table of above formula? (without drawing Truth Table). i think by using some inference. any idea? we know there are 11 "1"s ...