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
1answer
16 views

How does $\mathcal{A}\cup \mathcal{B}$ indicates that there is at least one augmenting path on $\mathcal{A}$?

I had an exam and there was the following question: $\mathcal{A}$ and $\mathcal{B}$ are matchings in a graph $G$, with $|\mathcal{A}|< |\mathcal{B}|$, study the graph formed with the edges of ...
3
votes
0answers
156 views

Number of spanning arborescences

I am trying to prove the following result from my book: Let $G$ be a directed graph with vertices $x_1,x_2,\cdots x_n$ for which a directed Eulerian circuit exists. A spanning arborescence with root ...
1
vote
1answer
25 views

How do i equaly distribute certain weights if i know how many times they appear

So i have those number groups 0, 273073 5, 222768 7, 43000 3, 24000 10, 12000 15, 12000 20, 12000 50, 1000 100, 100 500, 50 1000, 5 5000, 2 15000, 1 40000, 1 The first is the "weight"(which doesnt ...
12
votes
9answers
2k views

How many ways can seven people sit around a circular table?

How many ways seven people can sit around a circular table? For first, I thought it was $7!$ (the number of ways of sitting in seven chairs), but the answer is $(7-1)!$. I don't understand how ...
2
votes
2answers
57 views

Find all $a,b,c$ such that $\binom{a}{b} \binom{b}{c}=2\binom{a}{c}$

Find all $a,b,c \in \Bbb N $ such that $$\binom{a}{b} \binom{b}{c}=2\binom{a}{c}$$ $(c\leq b \leq a)$
0
votes
2answers
60 views

Probability that n people collectively occupy all 365 birthdays

The problem is quite simple to formulate. If you have a large group of people (n > 365), and their birthdays are uniformly distributed over the year (365 days), what's the probability that every day ...
3
votes
1answer
13k views

How many possible combinations in 8 character password?

I need to calculate the possible combinations for 8 characters password. The password must contain at least one of the following: (lower case letters, upper case letters, digits, punctuations, special ...
0
votes
2answers
42 views

Method of inclusion/exclusion [on hold]

Having a hard time with this, please help. Given $5$ pairs of gloves, in how many ways can $5$ people chose $2$ gloves with no one getting a matching pair?
1
vote
1answer
33 views

Counting the number of unicyclic graphs

Could you help me giving me the number of unicyclic graphs with k vertices and k edges ? I remind that a unicyclic graph with k vertices and k edges is a tree with k vertices and k-1 edges to wich we ...
0
votes
3answers
52 views

Let $A=\{0,1\}$. How many strings of length $5$ are in $A^*$ where at least two $1$ are next to each other?

Let $A=\{0,1\}$. How many strings of length $5$ where at least two $1$ next to each other are there in $A^*$?
3
votes
3answers
123 views

Prove the following relation:

I must prove the relation $$\sum_{k=0}^{n+1}\binom{n+k+1}{k}\frac1{2^k}=2\sum_{k=0}^n\binom{n+k}{k}\frac1{2^k}.$$ I got this far before I got stuck: $\begin{eqnarray*} ...
1
vote
2answers
38 views

8th positive odd integer that is an ODD Catalan number? [on hold]

The $n^{\text{th}}$ Catalan number is given by the formula $C_n = \frac 1{n+1}\binom{2n}n$. It also satisfies the recurence \begin{align*}C_n &=\sum_{k=0}^{n-1}C_kC_{n-1-k}\\ &= ...
3
votes
0answers
51 views

Probability of $m$ out of $n$ rolls of a die being among the numbers $1,2,\ldots,m-1$, for some $m$.

Suppose I have a $k$ sided die with the numbers $1,2,\ldots,k$ on each side, and that I roll it $n$ times ($n<k$). What is the probability that there exists an $m\leq n$, so that $m$ of the $n$ ...
2
votes
1answer
35 views

At least 2 girls between every pair of boys distribution question?

Three boys and eight girls are seated randomly in a row of 11 chairs. All orders are equally probable. What is the probability that there are at least 2 girls between every pair of boys? What is ...
1
vote
2answers
23 views

Number of monotonic set functions from all the subsets of some finite set to 0 or 1

Let $N=\{1,2,\ldots n\}$ be some finite set. Let $f:P(N)\rightarrow\{0,1\}$ be a function such that $A\subset B\rightarrow f(A)\leq f(B)$ I'm trying to find an upper bound to the number of such ...
0
votes
1answer
33 views

Unfair coin probability (P) that results in 0.5% chance of getting x tails out of y tosses?

For an unfair coin toss that produces heads with probability P, what is the value of P that will result in 0.5% (i.e. 0.005) chance of getting exactly x tails out of y tosses? i.e. is there a general ...
4
votes
2answers
568 views

Card Shuffling [SPOJ]

The original question is posted on SPOJ, and included below: Here is an algorithm for shuffling N cards: 1) The cards are divided into K equal piles, where K is a factor of N. 2) The ...
1
vote
0answers
99 views

Probability of unbalanced distribution of number of K elements in n sets

I have $n$ sets and $k$ elements with $k\gt n$. Each elements has the same probability $\left(\frac1n\right)$ to be inserted in a set. All the elements have to be inserted in one single set. I need ...
2
votes
0answers
33 views

Sizes of Hamming balls on the discrete torus

Consider the discrete torus $\mathbb Z^2_k $, with $k$ even, i.e. the graph with vertex set $\{0,1,\dots, k-1\} \times \{0,1,\dots, k-1\}$ and edges between any pair of vertices which differ in ...
0
votes
1answer
30 views

Counting permutations of up to k elements

Given a set of $n$ elements, I want to count all permutations with repetition, from $1$ to $k$ elements ($k>2$). In other words, $n^k+n^{k-1}+…+n^1$. What's the term/notation for this operation? ...
3
votes
1answer
21 views

How many subgraphs of $K_{m,n}$ are there that contain m + n vertices?

In this problem, a subgraph of $G = (V,E)$ is given by $G' = (V', E')$ where $V' \subset V$ and $E'$ is subset of edges of $E$ that connect two vertices in $V'$. How many subgraphs of $K_{m,n}$ are ...
3
votes
5answers
76 views

There are $n$ persons sitting around a table…

There are $n$ persons sitting around a circular table. Then, in how many different ways 3 persons can be selected if none of them are neighbours. My approach:- Let us pretend that we have already ...
0
votes
4answers
32 views

Counting candies in boxes

There are $5$ boxes containing $80$ candies. After taking $\frac{1}{5}$ of the candies in the first box and putting them in the seconf one, we take $\frac{1}{5}$ of the candies in the second box and ...
3
votes
0answers
17 views

Building a 3D matrix of positive integers

I'm trying to build a 3D matrix made up of positive integers that has very specific properties. The matrix dimensions are $N \times N \times (N+1)$ where $N$ is a positive integer. The matrix has two ...
1
vote
1answer
10 views

Looking for a recurrence relation ot combinatorial way to calculate initial number

A flock of birds migrating south flies above seven lakes. Half of the birds in the flock, plus half a bird(I'm guessing the initial flock contained an odd number of birds, say 5, so in the first lake ...
-5
votes
0answers
24 views

circular derangement related to round table [duplicate]

N people are invited to a dinner party and they are sitting on a round table. Each person is sitting on a chair there are exactly N chairs. So each person has exactly two neighboring chairs, one on ...
0
votes
1answer
32 views

Finding the total number of members in a club with multiple committees [on hold]

In ISI club each member is on two committees and any two committees have exactly one member in common. There are five committees. How many members does ISI club have?
1
vote
1answer
261 views

Probability of a slot having exactly $K$ elements

From this question asked in an interview: Consider a hash table with $M$ slots. Suppose hash value is uniformly distributed between $1$ to $M$. Suppose we put $N$ keys into this $M$-slotted ...
25
votes
0answers
601 views

Making Friends around a Circular Table

I have $n$ people seated around a circular table, initially in random order. At each step, I choose two people and switch their seats. What is the minimum number of steps required such that every ...
1
vote
2answers
102 views

How prove this identity$\sum_{k=0}^{n}\binom{2k}{k}\binom{n+k}{2k}(s-t)^{n-k}t^k=\sum_{k=0}^{n}\binom{n}{k}^2s^{n-k}t^k$

Today I see a paper,and this author say it is easy to have this identity.But I take sometimes to prove it,and I can't prove it. show this following identity holds for any real $s$ and $t$ and any ...
4
votes
1answer
82 views

Average time to fill boxes with balls

Let's have n users with each having a ball and m boxes. The users put their ball in a random box. It takes exactly 10 seconds for all balls to be put in a random box (independently to the number of ...
-2
votes
1answer
44 views

Show that $x\cdot x(k) = x(k+1) + k\cdot x(k)$ [on hold]

Show that $x\cdot x(k) = x(k+1) + k\cdot x(k)$ where $x(n)$ is the falling factorial. $$x(n) = x(x-1)(x-2) \cdots (x-n+1)$$ $$x(k+1)+kx(k) = (x)(x-1)(x-2)\cdots(x-k+2) + ...
1
vote
2answers
66 views

Combinatorics in a Party.

There are 12 persons in a dinner party, they are to be arranged on two sides of a rectangular table. Supposing that the master and the mistress of the house have are always facing each other, and ...
1
vote
2answers
44 views

Permutation and combination theory

The number of ways of distributing 12 identical oranges among 4 children so that every child gets atleast 1 and no child more than 4 is
0
votes
1answer
53 views

Marriage theorem. Proof. [on hold]

I am asking for advice: Let G be the bipartite graph $(V_1, E, V_2)$ with each vertex in $V$, of degree at least $d (> 0)$ and each vertex in $V_2$ of degree $d$ or less. Show that if each vertex ...
4
votes
1answer
83 views

The Island in the Miracle Sea. (Christmas edition)

To all of you who love math like me, I have this puzzling riddle that I hope you find interesting : On Christmas Eve just after midnight, Santa was riding his sleigh over the Miracle Sea when ...
2
votes
0answers
41 views

Edges of a permutohedron

Consider a permutohedron $P_n$ (this is a polytope which is a convex hull of $n!$ points, which are obtained from $(1,2,...,n)$ by all possible permutations of coordinates). I have to prove the ...
0
votes
2answers
569 views

Permutation and combination problem - word arrangement

This is a question of permutation and combination. Q. How many words can be formed from the word "LUCKNOW" when i) No restriction is there ii) L is the first letter of the word iii) All the ...
1
vote
4answers
107 views

Number of letters required to make three letter names

If a monster has 63 children and he wants to keep 3 letter names for each of them so that they are distinct,but with the condition that you can use the same letter more than once,how many letters at ...
-2
votes
2answers
49 views

Forming a committee

Suppose a committee must be formed from a group of 15 professors and 10 administrators. How many committees can be formed if the committee must consist of 5 professors and 5 administrators? Update 1: ...
1
vote
3answers
60 views

Why is this combinatoric solution not correct?

I'm trying to solve the following problem: Balls of the colors red, orange, yellow, green, blue, indigo, violet (7 colors, 1 ball per color) are placed into 4 different boxes A,B,C,D so that no box ...
0
votes
1answer
28 views

Extension of hypercube

I understand the notion of a hypercube as a graph with vertex set $\{0,1\}^{n}$ and an edge between two vertices if their vertices differ in one co-ordinate is there an extensive body of work on the ...
5
votes
0answers
86 views

A set of 19 numbers that are at most 93, and a set of 93 numbers that are at most 19, have equal sumsets [on hold]

If $x_1, x_2, ..., x_{19}$ are natural numbers lower or equal than 93 and $y_1, y_2, ..., y_{93}$ are natural numbers lower or equal than 19 then there is a non zero sum of some $x_i$ which is equal ...
0
votes
2answers
32 views

distribution probability question involving binary functions for certain n<2^10

For any positive integer n, let G(n) be the number of pairs of adjacent bits in the binary representation of n which are different. For example, G(10)=3 because the bits of $1010_2$ change at all ...
1
vote
4answers
121 views

How many ways can the vertices of an equilateral triangle be colored using three different colors?

Its not $3^3$ because some of the colorings are equivalent. How would I apply Burnside's theorem to this?
4
votes
1answer
415 views

Permutations of a set with a conditional subset

Using the digits 1, 2, 3, 5, 6, 8, 0 only once, how many 4-digit numbers could be constructed if the number is even? This is an exercise from an online course I'm taking. The given solution suggests ...
3
votes
3answers
277 views

Method for Counting the Divisors of a number

I need to find the number of divisors of 600. Is there any other way to solve the problem, apart from writing them down and counting??
0
votes
2answers
41 views

Algebra of Combinations.

How many solutions are there to the equation $$ x_{1} + x_{2} + x_{3} + x_{4} = 28\ {\large ?}\qquad\mbox{if}\qquad x_{1} \geq 3\,,\ x_{2} \geq 3\,,\ x_{3} \geq 5\ \mbox{and}\ x_{4} \geq 5. $$ $x_{1}, ...
1
vote
1answer
26 views

Find every possible distribution of the x elements considering a constraint on one of them

Considering a number r of triplets { a, c, i } I'd like to know which procedure / math field should I use to calculate every ...