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)

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
28 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
29 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
27 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
48 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
82 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
404 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 ...
1
vote
1answer
34 views

Twelve Fold Way Method of Counting

25 students audition for 10 parts in a play. How many possible casts? From having done multiple counting problems of this sort, I understand that the solution to this problem is 25!/(25-10)!. For ...
1
vote
0answers
67 views

Research Topics Needed

This coming academic year a professor has asked me to find some topics that I wish to pursue to write about. The problem/topic that will be discussed doesn't have to be open, but my trouble is that I ...
1
vote
1answer
44 views

Working with Multi-base Numbers

I wouldn't be surprised if there is an official term for what I am talking about, but I have never come across it. When I say Multi-base numbers, I mean a number ...
4
votes
1answer
263 views

The fewest questions should be prepared for a exam

$N$ students will do a test paper with $M$ question and for a consideration of cheat, every paper will be different, but not totally. There are at most $K$ questions same in any two papers. Given the ...
3
votes
0answers
141 views

Derangement bijection

This is a generalization of this question. An $(n,k)$ partial permutation is an injection from $[k]$ to $[n]$. It can be thought of as word of length $k$ in symbols in $[n]$ without duplications. ...
5
votes
2answers
92 views

Does $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs?

Q: Does the complete bipartite graph $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs, where $I$ is a $1$-factor (i.e., a perfect matching)? The obvious necessary conditions work: $K_{12,12}$ ...
3
votes
1answer
33 views

100 students in two classrooms.

Given 100 distinct students and two classrooms: A and B, of 60 and 45 seats respectively. In how many ways can a professor split the students into the two classrooms with respect to their ...
2
votes
1answer
28 views

Number of Orbits of symmetric group acting on $(\mathbb{Z}/n)^{l}$

I have encountered a problem that I suspect has been thoroughly studied but I have not been able to find references. Can anyone point me to a published reference dealing with this or a closely related ...
3
votes
0answers
50 views

Conjectured Value of Ramsey Number $R(3,10)$

It is known that the value of the Ramsey number $R(3,10)$ is either 40, 41, or 42. Have any experts in the field offered a conjecture as to which it might be?
0
votes
1answer
62 views

Intermediate-Advanced Counting Problem

How many standard 6-sided dice do I have to roll to guarantee that some nonempty subset of them add up to a multiple of 5?
0
votes
4answers
60 views

Combinatorics elementary question

A board has a red space, a blue space, and a yellow space. A checker is situated on the red space. On each move the checker is transferred to one of the other two spaces. In how many ways can one make ...
1
vote
0answers
20 views

Enumerating certain size 15 square matrices

This is an attempt to tackle A zero sum subset of a sum-full set by complete enumeration. I am looking for an algorithm which will efficiently (i.e. within reasonable time, several hours at the most) ...
2
votes
1answer
42 views

Combinatorial Probability

Another exercise from Saeed Ghahramani's Fundamentals of Probability, paraphrased below: Consider a train with $n$ cars and $m > n$ passengers. Suppose passengers board cars randomly. What is ...
1
vote
3answers
70 views

Find the number of integers solutions

How many solutions are there to the equation $$x_1+x_2+x_3+x_4=39,$$ I) where $x_1,x_2,x_3,x_4$ are nonnegative integers, II) where $x_1,x_2,x_3,x_4$ are nonnegative integers such that $3 \leq ...