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)

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
49 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
58 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 ...
1
vote
0answers
22 views

Faces of the Permutahedron

We define the Permutahedron as the convex hull of all permutations of the vector $(1,2,\dots,n)\in\mathbb R^n$. I am having trouble seeing why the number of $n-k$ dimensional faces of this polytope is ...
2
votes
1answer
113 views

Why do probabilists have a preoccupation with urns? [closed]

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 ...
1
vote
0answers
48 views

Sum of product of binomial coefficients and exponential function

I would like to know how to obtain (if it exists) a closed form expression of the sum $$S=\sum^{n}_{k=0}2^k{{n+1}\choose k}{{r-n-2}\choose {n-k}}$$ So far, I have tried to use the method of ...
0
votes
3answers
80 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
0answers
25 views

How to calculate the number of combinations of getting a pair in a deck of 52 cards?

I am confused over calculating the number of ways in which I can select a pair out of a deck of 52 cards, this is how I go about solving the problem, following the definition of a pair in card games, ...
1
vote
0answers
26 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 ...
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?
3
votes
0answers
71 views

Combinatorical interpretation of $\binom{15}{5} = \binom{14}{6}$

I was reading up on Sigmaster's conjecture on repeated binomial coefficiencts and I read that $$\binom{15}{5} = \binom{14}{6}$$ Sure, it's possible to prove it non-combinatorically: ...
4
votes
1answer
42 views

All $k$-regular subgraphs of $K_{n,n}$ have a perfect matching: a proof without Hall's Marriage Theorem?

There are several ways of describing this result: Theorem: For $k \in \{1,2,\ldots,n\}$, any $k$-regular subgraph of $K_{n,n}$ has a perfect matching (also known as a $1$-factor). I tend to ...
1
vote
2answers
56 views

Semi-Ambiguous Combinatorics Problem

I'm having trouble fully understanding this introductory combinatorics problem; this is all that's provided, so it's most likely me not fully comprehending the question. Any help is appreciated. The ...
1
vote
2answers
19 views

Counting Problem using Permutations

The Question was: In how many ways can the letters of the English alphabet be arranged so that there are exactly 10 letters between a and z? My approach was the following: In between a and z, there ...
0
votes
1answer
96 views

Big Mathematics Challenge on Set and Summation? [closed]

please be aware that this is not homework. it's past PHD entrance Exam on 2011. Suppose: $$B=\{(A_1,A_2,A_3) \mid \forall i; 1\le i \le 3; A_i \subseteq \{1,\ldots,20\}\}$$ if we have: ...
0
votes
1answer
15 views

Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
1
vote
1answer
39 views

Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
0
votes
3answers
29 views

Problematic Permutation Problem

i see a problem without any definition. would you please help me? i want to calculate the number of permutations of 1,2,...,1392 that 696 numbers be in the natural positions (from all numbers, 696 ...
0
votes
2answers
35 views

Perfect matching for graph with exactly $k$ edges for every node

Consider two disjoint sets $A$ and $B$, each of size $n$. Some (undirected) edges connect nodes in $A$ with nodes in $B$. Suppose that each node (in $A$ or $B$) is adjacent to exactly $k$ of those ...
4
votes
1answer
40 views

Derive a procedure to select one of the 2 options with equal probability when we are not using a fair coin.

Derive a procedure to select one of the 2 options with equal probability when we are not using a fair coin. $P(\text{H}) = p$. $P(\text{T}) = 1 - p = q$. I came up with the following two-roll ...
2
votes
1answer
34 views

Perfect matching for graph with two edges for every node

Consider two disjoint sets $A$ and $B$, each of size $n$. Some (undirected) edges connect nodes in $A$ with nodes in $B$. Suppose that each node (in $A$ or $B$) is adjacent to at least two edges. Is ...
0
votes
1answer
56 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 ...
1
vote
2answers
41 views

Combinations with replacement

In a factory there are 40 employees. A union of 5 people is being chosen. How many combinations are there for a union, if the union contains of 5 different roles, and each employee can hold more than ...
1
vote
3answers
73 views

Counting valid tickets

I think my question is very easy but I need to understand. The problem is, I have a ticket with 2 numbers from 1 to 10. The first number cannot be greather than the second number. How many valid ...
0
votes
3answers
32 views

Basic Combinatorics Choices Question

I'm having some trouble with the question below: I believe the student to have 9 x 8 x 7 x 6 = 3024 choices overall. However I am unsure how to calculate part (a) and (b) of the question. Any help ...
0
votes
0answers
34 views

show by using leibniz formula

There are given $ r, s,n \in\mathbb N$ and $r+s=n$. It also given $A \in M_{r,K} $, $B \in M_{r\times s,K} $ and $C \in M_{s,K} $. Let $M$ be the matrix $\begin{bmatrix}A & B\\0 & ...
1
vote
0answers
82 views

Arranging numbers in a grid

I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$. I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the ...
1
vote
2answers
100 views

How many patterns?

You probably have seen #patterns# in android devices witch working like passwords. My question is how many patterns can we draw in a 3*3 net and then how many in a m*n? assumptions: -a pattern ...
5
votes
1answer
49 views

Closed form for sequence A145271

I would like to know if there is a simple formula or method of expanding the expression given by $\left[g(x) \frac{d}{dx}\right]^n g(x)$ where $n$ is a positive integer, without having to resort to ...
0
votes
0answers
28 views

Counting question about a rectangular block

Consider the 12 face diagonals of a rectangular block. How many pairs of them are skew lines? (Two lines in space are skew if they do not intersect AND they are not parallel.) Basically I got that ...
5
votes
2answers
195 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
3answers
36 views

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subests of A cannot all be distinct [closed]

let A be a set of 6 distinct postive integers each <= 12, show that the sum of non empty subsets of A cannot all be distinct. for when does this not continue to hold up ( ie instead of 12 , its ...
0
votes
0answers
6 views

densities in sumsets is the product of the desities

Suppose $A,B,X,Y$ are finite subsets of $\mathbb Z$ with $X\subset A$ and $Y\subset B$. By $A+B$ and $X+Y$ we mean $\{a+b:a\in A,b\in B\}$ and $\{x+y:x\in X,y\in Y\}$ respectively. Suppose ...
0
votes
1answer
151 views

Find sum of all permutations

We call two arrays A and B with length n almost equal if for every i (1 <= i <= n) ...
1
vote
1answer
43 views

Permutations, Combinations, and Counting

A group of 63 people are camping together. They have two 6-person tents, three 4-person tents, five 3-person tents, and three 2 person tents. 18 people will sleep outside of the tents under a tarp. ...
2
votes
1answer
49 views

How many answers can be created using the elementary arithmetic operators?

If I gave you an amount of $n$ numbers, how many anwswer will you be able to create using the elementary arithmetic operators ($+, -, \times, /$)? These are the rules: All numbers ...
0
votes
1answer
31 views

Selecting 6 people from a group of 10 people with special conditions

Sorry for a misleading or such title, but i didn't know how to make it short enough. Anyways, if we have 10 people in a group such that 8 people eat apples, 1 eats pears and one eats watermelons, ...
0
votes
1answer
53 views

Counting the arrangements of 8 people around a square table?

I am trying to solve this problem of counting the number of arrangements of 8 people around a square table, as shown in the figure below, To solve this problem you can consider arrangements obtained ...
3
votes
0answers
38 views

an elementary problem on wreath product groups with combinatorial flavor

Embarrassingly, I got stuck in solving the following elementary exercise. Let $G=H\wr \Gamma$ be a wreath product groups, $H,\Gamma$ are countable discrete groups, when $\xi\in\oplus_{\Gamma}H$, then ...
0
votes
3answers
37 views

Counting Number of even and distinct digits

The Question was: The number of even four-digit decimal numbers with no digit repeated. So the first digit cannot be 0 so there are 9 ways to choose a digit. Then for the 3rd, 2nd and 1st digits ...
2
votes
2answers
50 views

Alternating sum of a simple product of binomial coefficients

I would like to evaluate the following alternating sum of products of binomial coefficients: $$\sum_{k=0}^{m} (-1)^k \binom m k \binom n k .$$ I had the idea to use Pascal recursion to re-express ...
3
votes
2answers
29 views

Find value of $n$ with given conditions

The 4-digit positive number $n$'s digit sum is $20$. The sum of the first two digits is $11$, the sum of the first and the last digit as well. The first digit is the last digit $+3$. What is the ...
0
votes
3answers
50 views

If there are $N$ people on the positive $x$-axis and one man can send a message to another one only if the distance between them is $\leq k $.

The question is how to determine a function which would decide if a pair of persons can communicate with each other, where communication is possible only if the distance between two individuals are ...
3
votes
1answer
33 views

Another formula for number of onto function.

Let A and B be two sets. $A=\{1,2,\dots m\}$ $B=\{1,2,\dots n\}$ We have to find the number of onto functions from A to B In the following link , the approach of the answer was applying Inclusion ...