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
18 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
0answers
57 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 ...
-2
votes
2answers
30 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
22 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 ...
1
vote
0answers
18 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 ...
0
votes
1answer
45 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 ...
1
vote
3answers
39 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
11 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
28 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 ...
1
vote
1answer
34 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 ...
4
votes
4answers
500 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 ...
3
votes
0answers
74 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
73 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
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 ...
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
29 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
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 ...
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
34 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 ...
1
vote
0answers
34 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
59 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
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}. ...
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 ...
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
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
50 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
1answer
24 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 ...
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
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
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^*$?
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}\\ &= ...
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
88 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
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 ...
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 ...