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
7 views

What is the probability of choosing r objects from c different groups when there are m groups of n objects?

Suppose I have m groups of n objects each for a total of nm objects. I am going to choose r of these nm objects. I want to know what the probability is that my r objects come from c different ...
2
votes
4answers
243 views

Is it possible to permute an unknown binary sequence so that two particular bits are equal?

A blind mathematician is give a $2015$ bit sequence. The mathematician can take any two bits and switch them (so the bit in position $A$ goes to position $B$ and vice-versa). He knows at what position ...
2
votes
0answers
55 views

A curious identity of weighted sums over multi-set permutations.

Suppose we have $n$ balls which are the same except colors, denote $S$ to be the set of all different permutations of the balls.(i.e. the swap of two balls with the same color will be the same ...
1
vote
0answers
68 views

Evaluation of a finite sum

I am having trouble evaluating the following finite sum: $$ \sum_{l=0}^{r}\binom{r}{l}(r-l)^{k},\qquad k\in\mathbb{N}_{0}. $$ Can you shed light on it?
1
vote
1answer
25 views

Questions concerning assumptions to conclude that $\operatorname{P}=\operatorname{NP}$

Suppose you find a reduction from the $k$-vertex-cut problem to the hamiltonian-path problem. In particular, you find an algorithm $A$ that, given the graph $G$ and the number $k$, outputs a ...
0
votes
0answers
16 views

Determine if the following family of hash functions is universal

Let $H = \{h_1,h_2,h_3\}$ be the family of hash functions defined below, each mapping $\{a,b,c,d,e\}$ to $\{0,1,2\}$. Is $H$ universal? A family of hash functions is universal if $\forall ...
0
votes
1answer
27 views

Finding number of relations using counting

Consider $A$ = {$w, x, y, z$}. Determine: (a) the number of possible relations on A, i.e., subsets of A×A (b) the number of relations on A that are reflexive and symmetric. (c) the number of ...
0
votes
2answers
41 views

Stars and bars with minimum number of categories

I've been trying to figure out a closed form solution to this problem, but I haven't been able to find one yet. How many ways are there to pick $n$ items from $k$ categories, such that at least ...
0
votes
1answer
21 views

9-digit ternary sequences with no three consecutive digits that are the same

How many nine-digit sequences with exactly three 0s, three 1s, and three 2s can be created if there are never three consecutive numbers that are the same? Can someone please show a step-by-step ...
2
votes
1answer
31 views

Number of Dyck paths from $(0,0)$ to $(2n,k_1)$ if allowed to go below the $x$ axis

What is the number of (general?) Dyck paths from $(0,0)$ to $(2n,k_1)$, where $k_1\geq0$, allowing the path to go below the $x$ axis and touch the negative horizontal line at $k_2\leq0$ an arbitrary ...
2
votes
0answers
32 views

Distinguishable balls in distinguishable boxes?

Suppose I have $n$ distinguishable balls and $N$ distinguishable boxes. A particular configuration of this 'system' is such that there are $k$ particles in a box, b, where $1\lt b \lt N$ (i.e. the ...
8
votes
1answer
54 views

probability that no two spiders end up at the same vertex?

Eight spiders are located on the eight vertices of a cube. When a bell rings, each spider moves (at random, independent of the others) to an adjacent vertex. What is the probability that no two ...
1
vote
1answer
33 views

Proof of the fact that the set of (p,q) shuffles is a cross section of the subgroup $S_p\times S_q$

Definition Let $G$ be a group and $H$ its subgroup. We name a subset $K$ of $G$ a cross section if it has exactly one element from each left coset of $G/H$. Definition Let $n=p+q$ for some ...
1
vote
1answer
25 views

Combinations - no repetition for mirrors?

My question is, if there is a simple explanation as to why mirrors aren't counted twice with binomials such as it is in the case it's not a mirror? Here is an example: Consider the elements {1, 4}. ...
0
votes
0answers
22 views

Transforming Exponential to Ordinary Generating Functions

I am looking for a particular ordinary generating function, if it exists for the Associated Stirling Numbers of the second kind $$b(1;n,j)=b(n,j)=\sum_{k=0}^j(-1)^k\binom{n}{k}S(n-k,j-k)$$ Where ...
7
votes
0answers
72 views

An example where $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is the number of ways of counting something?

Prove that for all non-negative integers $m,n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ is an integer. There is a answer given here to this question here. I've seen how it can be proven using recurrence ...
1
vote
1answer
31 views

Distribution problem where |a|, |b|, |c|, and |d| are at most 10. Check my work?

How many ways can a+b+c+d=18, where a,b,c,d are integers such that $|a|,\ |b|,\ |c|,\ |d|$ are each at most 10? This is what I have so far. If all four numbers have the restriction -10 =< a, b, ...
3
votes
1answer
14 views

Interpreting the Möbius function of a poset

I have just learned about incidence algebras and Möbius inversion. I know that the Möbius function is the inverse of the zeta function, and that it appears in the important Möbius inversion formula. ...
0
votes
1answer
17 views

Finding nth permutation in dictionary order with repeats

Given a set of symbols (e.g. $(A, A, B, B, B, C, D, D)$), calculate the nth permutation sorted in alphabetical order. I know how to do this with a set of symbols containing no repeats, but I can't ...
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 ...
0
votes
1answer
21 views

Combinatorial arrangements notation

I have a program that executes 2 kinds of operation with bytes and bits sets: BYTE OPERATION related to BIT POSITION and BIT OPERATION related to BIT POSITION The first operation provides a kind of ...
4
votes
2answers
49 views

Simplifying $\sum_{j=k}^{n}\binom{j}{k}/(2^{k-1})$

While doing an exercise (computing an expected value), I encountered an expression that looks like this. Is there a simpler formula? $$ \sum_{j=k}^{n}\frac{\binom{j}{k}}{2^{k-1}} $$ If it wasn't ...
0
votes
1answer
22 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 ...
4
votes
0answers
38 views

Max flow min cut from duality

I have been having some trouble deriving the max flow min cut theorem from duality, which I was told is possible. To begin with, I need to cast the problem into the form "maximize $\langle c, ...
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?
0
votes
2answers
59 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 ...
0
votes
3answers
50 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^*$?
1
vote
2answers
37 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}\\ &= ...
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 ...
5
votes
0answers
86 views

Set with distinct subset sums

The problem is as follows : Given a set A with distinct positive integer elements, prove that there always exists another set B consisting of positive integers, s.t., The size of B is less than or ...
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 ...
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 ...
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
5answers
75 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 ...
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 ...
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 ...
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 ...
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)$
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 ...
3
votes
0answers
50 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$ ...
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 ...
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?
10
votes
1answer
115 views

No sum of three numbers equals another number in set

Consider the set $S=\{1,2,\ldots,1000\}$. What is the maximum size of a subset $S'$ such that for any distinct $a,b,c,d\in S'$, we have $a+b+c\neq d$? We can choose $S'=\{333,334,335,\ldots,1000\}$, ...
0
votes
1answer
51 views

Circular arrangement and inclusion-exclusion principle

$4$ 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 $4$ chairs. So each person has exactly two neighboring chairs, one ...
-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) + ...
2
votes
0answers
40 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 ...
4
votes
1answer
80 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 ...
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 ...