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
0answers
9 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
63 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
20 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" ...
6
votes
2answers
169 views

Does counting make sense?

The Bertrand Russells and Alfred Whiteheads of this world have written lengthy proofs that $1+1=2$, etc. (and one should hope their purpose was to illuminate some point about mathematical logic rather ...
2
votes
1answer
25 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 ...
0
votes
0answers
42 views

How can I divide a group of 30 people into 6 different groups of 5 people?

I have a group of 30 people that I need to divide into 6 groups of 5 people, however I do not want the same people to be together twice. I already have 5 ways written down, but I just need one more. ...
2
votes
2answers
13 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 ...
0
votes
0answers
44 views

Intermediate Counting Problem [on hold]

In a classroom, 34 students are seated in 5 rows of 7 chairs. The place at the center of the grid is unoccupied. A teacher decides to reassign the seats such that each student will occupy a chair ...
1
vote
0answers
20 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: $$ ...
3
votes
1answer
112 views

Recurrence $(n+2)\text{Cat}_{n+1}=(4n+2)\text{Cat}_n$ for non-crossing matchings

The number of non-crossing matchings of sides of $2n$-gon (i.e. the number of ways to connect sides pairwise by non-intersecting paths) is $n$’th Catalan number, $\text{Cat}_n$. How to prove ...
1
vote
2answers
235 views

Probability of picking specific balls

Suppose I have $20$ red balls in one box and $20$ blue balls in another box. There $12$ red balls and $7$ blue balls have stars on them. I randomly take out one red ball and one blue ball at each ...
37
votes
2answers
2k views
+500

A zero sum subset of a sum-full set

I had seen this problem a long time back and wasn't able to solve it. For some reason I was reminded of it and thought it might be interesting to the visitors here. Apparently, this problem is from a ...
2
votes
1answer
48 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: ...
7
votes
0answers
82 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, ...
4
votes
1answer
52 views

Counting problem of unique asigments

I have to solve a counting problem but since my math skills are unfortunately low, I'm afraid I have stuck on a wall. Since the outcome could be 0 I don't know if ...
1
vote
0answers
22 views

Round robin tournament scheduling with additional constraints

I'm looking for a solution to the following problem. Given $n = a\cdot (b-1) + 1$ players, $a$ and $b$ being integers with $a \leq b$, I want to schedule a round-robin tournament where every player ...
-1
votes
0answers
34 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 ...
3
votes
0answers
27 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
90 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}$ ...
4
votes
1answer
81 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 N,M ...
0
votes
1answer
50 views

Partitions applications in physics

Is there any direct application of all developments related to partitions? I am specially interested in physics but cryptography or other mostly theoretical areas would also be a good answer. By ...
2
votes
1answer
53 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)$ ...
2
votes
0answers
57 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. ...
0
votes
0answers
31 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: ...
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, ...
2
votes
1answer
16 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 ...
1
vote
3answers
64 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 ...
4
votes
4answers
353 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 ...
0
votes
0answers
72 views

Number of ways to get 4 consecutive numbers out of 5 dice? [on hold]

Suppose 5 fair dice are rolled. Consider the dice as indistinguishable. How many different outcomes produce a sequence of 4 consecutive numbers? A. 2 B. 12 C. 96 D. 11 E. 3 How many ways are there ...
2
votes
1answer
103 views

Why do probabilists have a preoccupation with urns? [on hold]

Why is there an off-putting amount of questions from probability or combinatorics that involve an urn? Is there some historical reason? Did someone not have a box, or other container, on hand and had ...
15
votes
1answer
117 views
+250

How many pairs of nilpotent, commuting matrices are there in $M_n(\mathbb{F}_q)$?

As a follow-up to this question, I've been doing some work counting pairs of commuting, nilpotent, $n\times n$ matrices over $\mathbb{F}_q$. So far, I believe that for $n=2$, there are $q^3+q^2-q$ ...
0
votes
1answer
18 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 ...
5
votes
3answers
4k views

Proof a graph is bipartite if and only if it contains no odd cycles

How can we prove that a graph is bipartite if and only if all of its cycles have even order? Also, does this theorem have a common name? I found it in a maths Olympiad toolbox.
-1
votes
2answers
136 views

number of combinations of ordered sequences of N integers

suppose a N-tuple of N integers, such that every element in the tuple is bigger than or equal to the last one and each element in the sequence ranges from 1 to K. Is there any closed formula for the ...
-1
votes
1answer
53 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 ...
0
votes
1answer
121 views

all subsets with k elements of any uncountable set

if we take a {1, 2, 3} set as a countable set. it has subsets with 2 elements right, Those sets are : {1, 2}, {1, 3}, {2, 3}. But what about uncountable sets? if we take a (0, 9) set as subset of ...
4
votes
3answers
169 views

Does this generalisation of Latin squares have a name?

I am interested in looking at $n\times n$ tableaux (or matrices) in which (WLOG) each integer in $\{ 1, 2, \ldots, n \}$ occurs exactly $n$ times. This is a generalisation of a Latin (or even ...
0
votes
3answers
76 views

Combination Problem Understanding

How many ways can a Doctor go to the Hospital on $5$ days of January (which has $31$ days) such that no two visits are on consecutive days? I think the solution is: $\displaystyle\binom{27}{5}$ But ...
0
votes
1answer
219 views

What is the probability of picking Exactly 1 red marble and than not 1 red marble? without rep.

A urn has 3 red marbles, 2 blue marbles, 1white, 1 black 1 brown. What is the probability of getting exactly 1 red marble than not 1 red marble? What is the probability of getting at least 1 red ...
1
vote
1answer
29 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
57 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 ...
0
votes
0answers
39 views

An efficient algorithm to pair chess players in a team tournament

I found this question on a website. Your team is playing a chess tournament against a visiting team. Your opponents have arrived with a team of $M$ players, numbered $1,2,\dots,M$. You have $N$ ...
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 ...
7
votes
2answers
2k views

Permutations with identical objects

How can I find the number of $k$-permutations of $n$ objects, where there are $x$ types of objects, and $r_1, r_2, r_3, \cdots , r_x$ give the number of each type of object? Example: I have 20 ...
100
votes
3answers
12k views

Why can a Venn diagram for 4+ sets not be constructed using circles?

This page gives a few examples of Venn diagrams for 4 sets. Some examples: Thinking about it for a little, it is impossible to partition the plane into the $16$ segments required for a complete ...
0
votes
4answers
51 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 ...
2
votes
1answer
59 views

How many patterns of length 3?

I asked another question that I quess is too hard to be answerd but a want to learn so I have to change the problem: how many patterns with length three we can draw on an android device?
0
votes
1answer
43 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?
3
votes
0answers
43 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?