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

Number of ways to arrange items

Given a list of $n$ distinct items, where a smaller item behind a larger item is obscured, if you can see $x$ items from one end, and $y$ from the other, how many ways can the items be arranged? ...
0
votes
2answers
15 views

Probability of winning a rigged coin-flipping game

Betsy and Katie are playing a game with an unfair coin. The coin is rigged to come up heads with probability $\frac35$ and tails with probability $\frac25$. Betsy goes first. The two take turns. The ...
1
vote
3answers
48 views

How to find the number of possible outcomes of 10 games between 20 teams?

Hi I am looking for an equation to find possible combinations in a non repeating format with a twist. Here is the example: There are 10 games between 20 teams. I have to chose 5 winners but ...
0
votes
1answer
30 views

The number of self-avoiding paths in the plane of length $k$

The number of self-avoiding paths in the plane of length $k$ is at most $4 \cdot 3^{k-1}$ according to this. Why? My immediate thought: four options for the first move and always three choices after ...
-1
votes
4answers
41 views

How many ways are there to prepare one of 400 varieties of coffee in one of 7 ways?

I'm hoping someone can check my thinking: I have 400 distinct varieties of coffee. Each can be prepared in 7 ways (black, cream and sugar, etc.). How many possible combinations are there? I'm thinking ...
5
votes
1answer
95 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 ...
1
vote
1answer
52 views

How to solve this kind of problem?

I've just found the following problem: $\quad\quad$ $\quad\quad$ $\quad\,$ And I believe that it could be done with something in combinatorics, my feeling is that generating functions would ...
0
votes
0answers
31 views

How to start a proof ? What kind of mathematical tool I can use here? [on hold]

I have a set of $n$ points $\{A_1,A_2,...,A_n\}$. I draw every triangle formed with $3$ points $A$. What mathematical tool can I use to describe intersections between all these triangles ? I would ...
6
votes
0answers
102 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 ...
-11
votes
0answers
31 views

Showing $M(n,k,q)=\sum_{i=0}^{q}(-1)^{q+i}\binom{q}{i}\begin{pmatrix}0&n\\k&i\end{pmatrix}$. [on hold]

How do I show $$M(n,k,q)=\sum_{i=0}^{q}(-1)^{q+i}\binom{q}{i}\begin{pmatrix}0&n\\k&i\end{pmatrix}$$ for $q>1?$
4
votes
4answers
522 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
2answers
38 views

How many different (circular) garlands can be made using $3$ white flowers and $6m$ red flowers?

This is my first question here. I'm given $3$ white flowers and $6m$ red flowers, for some $m \in \mathbb{N}$. I want to make a circular garland using all of the flowers. Two garlands are considered ...
1
vote
1answer
47 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 ...
1
vote
0answers
29 views

A combinatorial game theory problem

In details, Let, there are four bishops on a chessboard where every two bishops are in pair ( as there are 4 bishops that means 2 pairs and in each pair they sit in vicinal squares). How many ...
0
votes
1answer
50 views

Can this binomial summation be simplified?

I got something like $\displaystyle\sum_{i=0}^K{ \binom{n+i}{i} \cdot \alpha^i} $ where $n,\ K,\ \alpha$ are definite values, $\binom{n+i}{i}$ is the Combinatorial number that choose $i$ from ...
0
votes
0answers
71 views

Number of sequences of 0s and 1s of length N such that k consecutive 1s are present [on hold]

How many different sequences of $0$s and $1$s of length $N$ are possible such that at least $k$ consecutive $1$s are present in them where $k\leq N$ exactly $k$ consecutive $1$s are present in ...
-1
votes
1answer
35 views

All variants of stars and bars / balls and bins problem [on hold]

The Stars and Bars problem or Balls and Bins problem are the the very basic in combinatorics but at the same time are quite helpful for beginners. Can we have list of variants of these problems? Add ...
1
vote
1answer
23 views

Union of each family is not the whole set

Let $n\geq k>0$, and consider all $\binom{n}{k}$ subsets of $A=\{1,2,\ldots,n\}$ of size $k$. We want to partition it into families so that the union of each family is not equal to $A$. At least ...
2
votes
0answers
20 views

Concerning the summation of digits to square-free numbers

Consider an alphabet of $n+1$ letters: $\{0,...,n \}$. Let $z$ be a number in base $n+1$ such that it has at most $n$ digits (so the initial/first string of digits can be composed of $0$'s). Let ...
1
vote
1answer
28 views

Concerning the summation of digits in strings: how many strings have an even such sum?

This is a continuation of a previous question of mine Consider an alphabet of $n+1$ letters: $\{0,...,n \}$. Let $z$ be a number in base $n+1$ such that it has at most $n$ digits (so the ...
5
votes
1answer
50 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
3answers
47 views

How many ways to make a connected graph using 4, 5, 6 edges?

How can/how many ways can you make a connected graph that has 5 vertices using 4, 5, 6 edges? I'm not sure how it would look like for 4 edges. Can you draw a diagram?
1
vote
0answers
14 views

Inequality to bound $\sum_i a_i b_i - \sum_i c_i d_i$ (harmonic eigenfunction/graph) type sum with constraints

We have a homogeneous graph $G = (V,E)$ with a function $f:V\rightarrow \mathbb{R}$. We define the following modulus: $\displaystyle \omega(s) = \sup\{f(x)-f(y) \ | \ |x-y|=s \}$ and wish to lower ...
0
votes
0answers
31 views

A question on matching points in the plane

Let $A,B\subset\mathbb{R}^2$ with $|A| = |B| = 5$. For any $x\in \mathbb{R}^2$ denote by $A_x\subseteq A$ the set of points $a\in A$ such that $a\leq x$ (product order). We know that the following ...
0
votes
2answers
52 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 ...
3
votes
2answers
91 views

Christmas protocol

Since holiday season is coming, here is a little practical-purpose combinatorics question. Lots of group of friends or families practice the random variant of Secret Santa, where each member buys a ...
2
votes
1answer
35 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 ...
0
votes
1answer
32 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 ...
7
votes
6answers
323 views

Prove that $\binom n2 + \binom {n-1}2$ is always a perfect square

Prove that if $n$ is a positive integer and $n >1$: $$\binom n2 + \binom {n-1}2$$ is always a perfect square. I know we need to turn that into a binomial, but I can't follow how. Please note I'm ...
4
votes
2answers
51 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 ...
1
vote
0answers
35 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 ...
0
votes
0answers
25 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 ...
1
vote
1answer
27 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 ...
1
vote
1answer
50 views
+50

Hypergraph rainbow colouring of $\{1 \dots n\}$ for $A = \{A_1, \dots A_k\} : A_i \subset \{1, \dots n\}$

We are given collection of sets $A = \{A_1, \dots A_k\}$, where each set $A_i \subset \{1,\dots n\}$. Colouring $\{1, \dots n\}$ into $s$ colours would be called 'rainbow' for given $A$, if $\forall ...
10
votes
1answer
120 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\}$, ...
1
vote
0answers
79 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?
0
votes
0answers
18 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
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 ...
1
vote
1answer
34 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 ...
8
votes
1answer
60 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 ...
18
votes
6answers
8k views

Probability: 6 Dice are rolled. Which is more likely, that you get exactly one 6, or that you get 6 different numbers?

Here's the question: 6 Dice are rolled. Which is more likely, that you get exactly one 6, or that you get 6 different numbers? Here's what I've done: The number of possible outcomes is $6^6 = ...
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 ...
1
vote
1answer
27 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}. ...
1
vote
1answer
32 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, ...
7
votes
0answers
76 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
26 views

Count and description of vertices of certain faces of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$

For $k \ge 1$, $d \ge 2$ and $k \le d - 1$, let ${}^f_d\Omega^t_{d+k} (d;c_k(d - 1))$ be the intersection of $k - 1$ facets of the Tridiagonal Birkhoff polytope $\Omega^t_{d+k}$ with equations: ...
3
votes
1answer
620 views

How many ternary (0, 1, 2) sequences of length 10 are there without any pair of consecutive digits the same?

How many ternary (0, 1, 2) sequences of length 10 are there without any pair of consecutive digits the same? Not sure if I understood the question correctly. It's asking for possible 10 digit number ...
0
votes
1answer
47 views

Combinatorics-Table Arrangement

How many way can you arrange 10 people in a circle given that 2 particular people cannot sit together? I'm not sure how to solve this. I was thinking of maybe $\frac{8!}{10!}$ But I'm pretty sure ...
6
votes
1answer
101 views

How can a finite graph be viewed as a discrete analogue of a Riemann surface?

In the paper "Riemann–Roch and Abel–Jacobi theory on a finite graph" by Baker and Norine, the first line of the abstract states: "It is well known that a finite graph can be viewed, in many respects, ...
1
vote
2answers
415 views

Lattice Paths from $(1, 1) \to (x, y)$ [on hold]

Moderator Note: This is a current contest question on Brilliant.org. Let $S$ be the set of $\{(1,1), (1,−1), (−1,1), (1,0), (0,1)\}$-lattice paths which begin at $(1,1),$ do not use the same ...