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)

3
votes
0answers
104 views

Maximum subset of [1,899] that contains no two disjoint length 3 arithmetic progressions with same gap length

Let X be a subset of [1,899]. What is the maximum size $X$ can have if $X$ contains no two disjoint arithmetic progressions of length 3 and same gap between members? For example: 1,3,5 and 2,4,6 are ...
1
vote
1answer
52 views

Days that cashier will work [duplicate]

A cashier wants to work five days a week, but he wants to have at least one of Saturday and Sunday off. How many ways can he choose the days he will work?
-1
votes
2answers
97 views

Sophomore + Junior + Senior

A class is attended by $n$ sophomores, $n$ juniors and $n$ seniors. In how many ways can these students form $n$ groups of three people each if each group is to contain a sophomore, a junior, and a ...
2
votes
1answer
348 views

Ways to place n non-attacking rooks on an $n^2$ square board.

How many ways are there that we can place n number of non-attacking rooks on an $n \times n$ chess board?
1
vote
1answer
81 views

Possibility difference between pattern and PIN

Recently I have seen many people using a pattern on a ten digit keypad to unlock their mobile device. This got me thinking about the effectiveness of such a security measure. My first instinct was ...
3
votes
4answers
892 views

$\sum_{k=0}^{n/2} {n\choose{2k}}=\sum_{k=1}^{n/2} {n\choose{2k-1}}$, Combinatorial Proof:

How am I supposed to prove combinatorially: $$\sum_{k=0}^{n/2} {n\choose{2k}}=\sum_{k=1}^{n/2} {n\choose{2k-1}}$$ ...
5
votes
2answers
184 views

Combinatorial Proof of ${n\choose{m}}=\frac{n}{m}{{n-1}\choose{m-1}}$

How do prove the following identity combinatorially? $${n\choose{m}}=\frac{n}{m}{{n-1}\choose{m-1}}$$ Any help or hints would be great!
0
votes
1answer
35 views

Selection of three children from six children

I would like to consider the following problem (from http://vimeo.com/6790417): Here, the author says that a distribution of $3$ red shirts and $3$ green shirts among the $6$ children so that ...
2
votes
1answer
49 views

Optimize database indexes, the sequel

Background For those not familiar with databases. Indices help to speed up database searches, but they come at the cost of memory. Since you like your database to be fast, they are best cached in RAM ...
0
votes
6answers
1k views

3-digit numbers that the sum of digits are even.

How many three digit numbers are there such that the sum of the digits is even? So I guess we're taking the total number of three digit numbers, then eliminate the ones that doesn't satisfy the ...
1
vote
1answer
104 views

Detecting resource allocation conflict

Definitions We have grids of n by n cells. The columns are named A, B, C, etc. In each cell of each row the column letter could be on or off. We define two grid types - Type 0 and Type 1. Here are ...
6
votes
1answer
148 views

Probability that a random edge coloring of the complete graph is proper

Suppose we color the edges $\{1,\ldots, {n \choose 2}\}$ of the complete graph on $n$ vertices with $m$ colors each edge being assigned a color picked uniformly at random from $\{1,\ldots, m\}.$ I ...
0
votes
2answers
70 views

Concept Of Permutation To Solve A Problem

I have a problem with the concept of permutation . The problem description is as follows : Md Asad has 5 children and 8 nephews . All of them are to be seated in a row . Nephews like the last 4 ...
2
votes
2answers
113 views

Does anyone know why this inclusion exclusion calculation isn't working?

In this question, the problem is to find the amount of four-digit numbers that have the following characteristics: All digits are unique. Does not contain the digits 3 and/or 4. The number is ...
1
vote
2answers
221 views

Probability that number of heads flipped is divisible by 3

You toss a coin n times. What is the probability that the number of heads you’ll get is divisible by 3? (Find an exact formula, not involving sums of unbounded length; it may depend on the remainder ...
2
votes
3answers
200 views

$4$-digit positive integers that does not contain the digits $3$ and $4$ plus other properties

I'm just wondering, what is the total number of $4$ digit positive integers that have the following properties: All digits are unique. Does not contain the digits $3$ and/or $4.$ The number is ...
0
votes
1answer
67 views

The general probability of getting either all heads or tails in tosses?

What is the probability that I would get either all heads or tails in n coin tosses. I know, for example, in $4$ tosses, the probability is $\left(\frac12\right)^4=\frac1{16}$ to get either all heads ...
1
vote
3answers
593 views

Number of 4-digit numbers having different digits.

How many four-digit positive integers are there such that all digits are different?
0
votes
4answers
48 views

Selecting 11/5 out of 30 students.

How many ways are there to select a team consists of 11 members for baseball and other 5 members for basketball, from a class of 30 people?
2
votes
3answers
327 views

Prove that $44^n-1$ is divisible by $7$ for some $n$

How do I prove that there exists a positive integer n such that $44^n-1$ is divisible by $7$?
2
votes
1answer
31 views

Sports competition team gaming

Let $A,B,C,D,E,F$ be six teams in a sports competition, and each team will play exactly once with another team. Now we know that Team $A,B,C,D,E$ had already played $5,4,3,2,1$ games, ...
-6
votes
1answer
87 views

Coin flipping question

Bernoulli was flipping fair coins one day and wrote down a sequence of 12 results. He noticed that in his list of results he did not have two consecutive heads nor two heads with exactly one tails ...
6
votes
1answer
76 views

Bridge HCP held by the best hand at the table?

In the game of Bridge, what is the expected number of high card points held by the player holding the most high card points at the table? $A=4$, $K=3$, $Q=2$, $J=1$.
-3
votes
3answers
98 views

Combinatorics Question - thank you!

In a dresser drawer, there's a jumble of 5 red socks, 5 blue socks, 7 green socks, and 4 yellow socks. What is the minimum number of socks we have to pick up in order to guarantee that at least 4 will ...
1
vote
1answer
104 views

Number of Inequivalent Difference Sets In Elementary Abelian 2-groups

I have reason to believe that there is only one$(2^{2s+2},2^{2s+1}-2^s,2^{2s}-2^s)$- difference set (based on experimentation in GAP), up to equivalence/complementation, in any elementary 2-group of ...
1
vote
3answers
47 views

Proving the existence of a unique planar embedding

Show that there is a unique planar embedding in which each vertex has degree 4 and each face has degree 3. It is easy to just draw such a planar graph, but how to show the embedding is unique? ...
0
votes
0answers
37 views

Proving a fact about planar graphs

Let $G$ be a connected planar graph with $p$ vertices and $q$ edges and girth $k$. Show $$q\leq {k(p-2) \over k-2}$$ How should I do this? My textbook has no solution, and I seem to not recall ...
3
votes
1answer
122 views

5 cars, 4 parking places. Derangements and permutations with fixed points

I found an exercise in combinatorics: In the parking of a building, there a re five parking spots, with their owner cars assigned to them. One day only four cars arrived. In how many ways can ...
1
vote
0answers
123 views

How to divide 32 teams to 8 groups of 4 (similar to UEFA Champions League draw)?

I have 32 teams from various countries. Each country can be represented by up to 4 teams. I need to divide those 32 teams into 8 groups - each consisting of 4 teams, no two teams can be from the same ...
1
vote
1answer
39 views

Alternating cards and cycles

Let's say we have 5 cards labeled from 1-5. We deal them out in order: 1 2 3 4 5 Now we do the following shuffle. We take the top card (1), put it on the bottom, deal the second card (2), then put ...
6
votes
2answers
190 views

Proving that a “prime graph” is connected

Let the prime graph be defined as the graph of all natural numbers, with two vertices being connected if the sum of the numbers on the two vertices add up to a prime number. Prove that the prime ...
16
votes
1answer
544 views

How many different shapes can I make with this toy?

I have the following toy, perhaps some of you have seen it before. It consists of a bunch of cubes with an elastic string in the middle. You can bend it into different shapes like this: Or this: ...
0
votes
1answer
49 views

Generating functions for election results

This is from my textbook which does not give solutions to problems (i.e. not homework). Find the generating series for the number of election results involving 4 candidates with respect to the ...
0
votes
1answer
34 views

Is this the correct way to derive the generating series?

This is from my textbook, which has no solutions for any of the problems (bad). Determine the generating series for the number of 5-combinations where M, A, T, H in which M and A can appear any ...
0
votes
1answer
173 views

How many ways can b balls be distributed in c containers where each container has n labeled slots?

If each container has n unlabeled slots, the problem is same as the one "How many ways can b balls be distributed in c containers with no more than n balls in any given container?" The answer is known ...
1
vote
2answers
79 views

How to find distribution for roll of 2 dice

You roll 2 ordinary dice. Let X denote the maximum of the two numbers you get. What is the distribution of X? I did the problem as follows: $$\begin{array}\\ X &= 1: (1, 1) \\ X &= 2: ...
1
vote
1answer
420 views

The number of solutions for $x+y+z=n$ [duplicate]

How do I approach this problem? I know the formula but do not how it had come. Could you please explain to me the procedure, with examples if possible. stars and bars theorem
2
votes
1answer
185 views

Von Neumann's minimax theroem and Carathéodory's theorem

In J.F. Mertens(1986)(Paywall), there's a neat proof of a version of Von Neumann's minimax theroem. But I can't understand how Carathéodory's theorem is invoked. Suppose, in a two-person zero sum ...
1
vote
0answers
83 views

When is it appropriate to count outcomes to solve a combinatorial probability problem

I have been looking at problems on this site such as selecting cards from a deck of cards or marbles from a bag of marbles. One thing I have been struggling with is when I can solve the problem simply ...
0
votes
2answers
197 views

probability of occcuring alternative colors

according to my previous link probability calculation in dice throwing i have tried to solve following problem: A bag contains $4$ white and $3$ black balls. Four balls are successively drawn out ...
0
votes
1answer
70 views

permutation and combination problem

let us consider this problem: Chelsea has a bookshelf consisting of ten classics: four Russian novels, three British novels, two French novels, and a German novel. If she wants to make sure that the ...
-1
votes
1answer
142 views

How many Unique Combinations?

I'm trying to solve a programming problem which I have so far reduced to the following. The actual problem looks nothing like this, but on analysis, I came up with this simplified way to solve it, ...
0
votes
4answers
56 views

Please help with this question about sets…

If #$A = n$ , determine the value of $n$ for which the number of subsets of size $4$ is equal to the number of subsets of size $8$.
2
votes
1answer
90 views

Cyclic error correcting code

Notation: I denote the field with $2$ elements by $\mathbb{F}_2$. For a vector $u\in\mathbb{F}_2^m$, I write $w(u)$ for the Hamming weight of $u$ (the number of components equal to $1$ in $u$). ...
3
votes
0answers
87 views

Equivalence classes of triplets satisfying $x^2+y^2+z^2=0$ over $\mathbb{F}_p$

The affirmative answer to this question illustrates that the equation $$x^2+y^2+z^2=0$$ has $p^2-1$ nontrivial solutions over $\mathbb{F}_p$ (solutions that are not $(0,0,0)$). If $(x,y,z)$ is a ...
6
votes
0answers
142 views

Rotations of a tetrahedron

Let $P$ be a tetrahedron inside an sphere such that all of its vertices are on the surface of the sphere. Suppose that three quarters of sphere's surface is colored black. Show that there is a ...
5
votes
3answers
199 views

How Many Ways to Build a 6-Pack

There is a beverage company here that claims to have a selection of 200 different beers. They have a special deal where you can build your own six pack at a discount. They advertise that there are ...
0
votes
0answers
90 views

Solving the “Library of Babel” puzzle, but for polygons.

The Library of Babel is a story about a universe whose contents are every possible 410-page book that could possibly exist. After a conversation with someone about doing this with images, and coming ...
2
votes
0answers
126 views

Modified balls and bins

Assume that we have $n$ balls and $k$ bins. The $n$ balls are are divided into $M$ sets, $\left\{ {{m_i}} \right\}_{i = 1}^M$, where $\sum\limits_{i = 1}^M {\left| {{m_i}} \right|} = n$, $|m_i| \le ...
3
votes
2answers
91 views

A bijective mapping from $\mathbb N^k$ to $\mathbb N$?

Having $k$ numbers $N_i\in\mathbb{N}$, I'm looking for a bijective mapping $f:\mathbb{N}\times\ldots\times\mathbb{N}\rightarrow\mathbb{N}$ So that ...