For 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)

2
votes
1answer
86 views

Arrange soccer fixtures with correct home - away alternation for each team

I am trying to do as the title says. I have 10 teams in the same group. Every team must play the rest once each but each of them will always alternate home and away. This means that if they play at ...
1
vote
2answers
104 views

How many ways to tie $2$ ropes so that we do not have a loop

BdMO 2014 Higher Secondary: Avik is holding six identical ropes in his hand where the mid portion of the rope is in his fist. The first end of the ropes is lying in one side, and the other ends ...
2
votes
1answer
55 views

Find the tens place of a number

For any odd number N ending with the digits $1,3,7$ or $9$, $(N)^{20\cdot n}$ ends with $01$. Here, $n$ is any natural number Now I have tested the result with a few odd numbers. But is there any ...
1
vote
1answer
32 views

Number of triangles in a triangulation

Wikipedia Delaunay Triangulation On this page, I read (with $n$ the number of edges): "In the plane (d = 2), if there are b vertices on the convex hull, then any triangulation of the points has at ...
5
votes
5answers
160 views

How to find $ \binom {1}{k} + \binom {2}{k} + \binom{3}{k} + … + \binom{n}{k} $

Find $$ \binom {1}{k} + \binom{2}{k} + \binom{3}{k} + ... + \binom {n}{k} $$ if $0 \le k \le n$ Any method for solving this problem? I've not achieved anything so far. Thanks in advance!
3
votes
1answer
77 views

At most $2n$ vectors, the angle between which $\geq\pi/2$.

In a previous question it is proved that in $\mathbb R^n$ there are at most $n+1$ vectors, the angle between which $>π/2$. How to prove that there are at most $2n$ vectors, the angle between which ...
2
votes
2answers
156 views

Binomial coefficients identity: $\sum i \binom{n-i}{k-1}=\binom{n+1}{k+1}$

I am trying to prove $ \sum_{i=1}^{n-k+1} i \binom{n-i}{k-1}=\binom{n+1}{k+1} $ Whichever numbers for $k,n$ I try, the terms equal, but when I try to use induction by n, I fail to prove the ...
5
votes
1answer
63 views

Subgroups of $S_n$ that can send any subset of $[n]$ to any equally sized subset of $[n]$

This is a repost of a question I was trying to solve yesterday that got deleted. The question asked for a characterization of the subgroups $G$ of $S_n$ which when endowed with their natural action on ...
3
votes
3answers
90 views

A combinatorial identity: $\sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $

I proved this combinatorial identity while doing some linear algebra. For any positive integer $k$, $$ \sum _{i + j = k} (-1)^i {n \choose i} {n + j - 1 \choose n - 1 } = 0 $$ I was wondering what ...
2
votes
2answers
52 views

Number of solutions to 3-variable sums with restrictions

I came across the following problem 1) How many solutions does the equation $x_1+x_2+x_3=8$ have with integers $x_i\ge0$? There are $9$ possible values for $x_1$. For each of those, there are ...
6
votes
2answers
127 views

Number of solutions of a simple equation

Problem How to count the number of distinct integer solutions $(x_1,x_2,\dots,x_n)$ of the equations like : $$|x_1| + |x_2| + \cdots + |x_n| = d $$ the count gives the number of coordinate points ...
1
vote
0answers
32 views

Loose/fuzzy bin packing - minimizing overhead

I have a sequence of n random numbers, with a mean of m. How can I order them in a sequence seq a way that minimizes the following expression? $$ \sum\limits_{i=1}^n \left|\frac {\sum_{j=1}^i ...
0
votes
0answers
67 views

Help in Understanding the Formula for The Lattice Point Counting in Triangles with Rational Coordinates

Yesterday I have found this paper while searching Google. However, since the author of this paper gave no examples of implementing the following formula, I don't understand how to implement it in ...
1
vote
4answers
77 views

How to show $I_p(a,b) = \sum_{j=a}^{a+b-1}{a+b-1 \choose j} p^j(1-p)^{a+b-1-j}$

Show that $$I_p(a,b) = \frac{1}{B(a,b)}\int_0^p u^{a-1}(1-u)^{b-1}~du\\= \sum_{j=a}^{a+b-1}{a+b-1 \choose j} p^j(1-p)^{a+b-1-j}$$ when $a,b$ are positive integers. I have no idea how to proceed. ...
0
votes
1answer
56 views

How to determine number of parametric pairs if parameters have different number of values

I have been following a book on an example to determine number of parametric pairs: There are 7 parameters, each with 8 possible values. To determine pairs, they use the combinatorial number (7 ...
4
votes
0answers
58 views

Can the principle of inclusion/exclusion be used to count elements in the intersection of a sequence of sets?

The principle of inclusion-exclusion (PIE) is often used to count the number of elements in a union of $n$ sets in terms of an alternating sum of their various intersections: $$ \left |\bigcup_{i \in ...
1
vote
2answers
99 views

Number of strings of length 10 consisting of the digits 0,1,2,3 with even sum of digits

A weight for string is simply the sum of digits. Now if the digits are 0, 1, 2 and 3, how many possible strings are there of even weight if the string is 10 digits? My reasoning: there must be an ...
5
votes
2answers
191 views

What is the coefficient of $x^{18}$ in the expansion of $(x+x^{2}+x^{3}+x^{4}+x^{5}+x^{6})^{4}$?

How to approach this type of question in general? How to use binomial theorem? How to use multinomial theorem? Are there any other combinatorial arguments available to solve this type of question? ...
4
votes
4answers
338 views

Encode order of playing cards (data compression)

Suppose we have a deck of cards, shuffled in a random configuration. We would like to find a $k$-bit code in which we explain the current order of the cards. This would be easy to do for $k=51 \cdot ...
0
votes
1answer
15 views

Optimization relaxtion quesiton

I have the following LP relaxation of an integer programme (the programme formed from the set cover problem) minimize $\sum_{j=1}^{m} w_{j}x_{j}$ subject to $\sum_{j:e_{i} \in S_{j}} x_{j} \geq 1$ ...
1
vote
2answers
79 views

Finding an eigenvalue of a special cubic graph

My question is about a cubic graph $G$ that is the edge-disjoint union of subgraphs isomorphic to the graph $H$ that is as below: I want to prove that $0$ is an eigenvalue of the adjacency matrix ...
0
votes
3answers
45 views

can anyone explain this combinatorial problem?

I got this problem from "$102$ Combinatorial Problems From the Training of USA IMO Team". I don't need the solution to this problem. Just an explanation of what I'm supposed to prove. Let $n$ be an ...
1
vote
0answers
62 views

Is there any efficient progam or software to calculate the fractional chromatic number?

The fractional chromatic number $\chi_f(G)$ is a generation of the chromatic number of a graph $G$. It can be formulated as a linear programming question: Let $\mathcal{I}(G)$ be the set of all ...
2
votes
7answers
75 views

numbers in a 5 digit number

i have a very simple question i need to know the probability of a 5 digit number to be with the digit 5 only one time so first digit cant be 0 so i do: $8\times9\times9\times9\times1$ ...
0
votes
4answers
36 views

Two different results for splitting sample points into groups of a certain size?

Let's say I've got a group of 12 people and want to split them into groups of 4. According to this post How many ways $12$ persons may be divided into three groups of $4$ persons each?, the possible ...
0
votes
1answer
48 views

A question on divisors of $A=(q^n-1)(q^n-q)(q^n-q^2)\cdots(q^n-q^{n-1})$

Let $A=(q^n-1)(q^n-q)(q^n-q^2)\cdots(q^n-q^{n-1}),$ where $q=p^r,\ p$ is prime and for some $r\in \mathbb{N}\cup\{0\}.$ Does $q^s,$ for some positive integer $s,$ divide $A?$ Or what are the divisors ...
2
votes
2answers
153 views

How many prime number factors are there for 420(base 6)?

I don't know the actual approach. I did it this way: $2\cdot210=420$ (base 6) $2\cdot103=210$ (base 6) $3\cdot21=103\;$ (base 6) Now $21$ (base 6) $= 13$ (base 10) = prime So, the total number of ...
1
vote
1answer
137 views

A number trick: determining the boxes from which the numbers were taken, given their sum

Mr. X is a famous magician. He has 1 to 100 cards at his disposal. He puts them in 3 different boxes-red,green,blue. Now, he requests the audience to blindfold him and select 1 card each from any 2 ...
2
votes
1answer
47 views

Distinct ways three integers can sum to a constant

So I am doing some quantum mechanics and it has led to some combinatorics. I need to know how many distinct ways I can have $N_1+N_2+N_3=N$ where $N$ is fixed so we can change $N_1$, $N_2$ and $N_3$. ...
0
votes
1answer
23 views

Help checking a question on graph theory.

Can someone check these (bit skeptical of my answers). a) How many copies of $C_4$ in $K_n$? Picking any 4 vertices can be used to give a copy of $ C_4 $of each of these there are $4!$ ways in which ...
2
votes
1answer
105 views

Closing a subcategory under finite colimits by transfinite induction

Let $\mathcal{C}$ be a locally small category with all finite colimits, and let $\mathcal{A}$ be a small full subcategory. I wish to prove the following: Proposition. There exists a full subcategory ...
9
votes
5answers
150 views

Number of sequences of $0$s, $1$s, and $2$s with length $n$ such that there is a $0$ somewhere between every pair of $2$s

Let $a(n)$ be the number of sequences with length $n$ which consists the digits $0,1,2$ such that between every two occurrences of $2$ there is an occurrence of $0$ (not necessarily next to the ...
2
votes
1answer
32 views

How many copies of $C_4$ are there in $K_n$

How many copies of $C_4$ are there in $K_n$? I said that any 4 distinct vertices is one copy of $C_4$ in $K_n$ so there must be $n$ choose $4$ total copies of $C_4$ are there in $K_n$. Is this ...
3
votes
1answer
88 views

Find the number of natural numbers

$N$ is a natural number greater than 1 and less than 100. $F(1), F(2), \dots, F(n)$ are the factors of $N$ in such a way that $1=F(1)< F(2)< F(3)< \dots < F(n)=N$. Further, $D= ...
1
vote
1answer
27 views

Why the generating function of $a_r=r$ is $xf'(x)$ instead of $f'(x)$?

I've seen the following definition: Theorem 5.1 $f(x),g(x)$ are the generating functions of the sequence $(a_r),(b_r)$. $[...]$ $(iv)$ The generating function to $(ra_r)$ is ...
7
votes
4answers
325 views

Truncated alternating binomial sum

It is easily checked that $\displaystyle\sum_{i\ =\ 0}^{n}\left(\, -1\,\right)^{i} \binom{n}{i} = 0$, for example by appealing to the binomial theorem. I'm trying to figure out what happens with the ...
6
votes
4answers
1k views

How many natural numbers less than 200 will have 12 factors/divisors?

How many natural numbers less than 200 will have 12 factors (a.k.a. divisors)? I think the answer is $11$. Firstly there can be at most $3$ distinct prime factors. $12=1\cdot12 =2\cdot6 ...
1
vote
1answer
651 views

Number of possible combinations of the Enigma machine plugboard

This is a question about basic combinatorics. I recently watched again a youtube video about the Enigma cipher machine (in the Numberphile channel, https://www.youtube.com/watch?v=G2_Q9FoD-oQ), where ...
1
vote
2answers
60 views

pictorial illustration of simplicial complexes

Consider the following two complexes (Bruns&Herzog p.215): By just looking at the complex on the left, i am not sure how to read its faces. Surely its vertices are $v_1,v_2,v_3,v_4,v_5$. The ...
0
votes
0answers
19 views

Bound problem of Coding Theory when distance is even

I encounter the following two exercises when learning coding theory, but I can't get a proof. If there exists a $q$-ary code $(n,K,d)$, where $d=2l$ is an even number, prove that $q^n\geq ...
3
votes
4answers
114 views

Physical substance/meaning of $0!=1$? [duplicate]

I know the question sounds silly, however all I could find is the mathematical proof justifying the same but the convincing inference is still missing. My intent basically was to ask for the better ...
9
votes
3answers
244 views

On solutions of an equation in $\mathbb{Z}_3$

For integer numbers $x_1, x_2, y_1, y_2, y_3$ suppose that $$ x_1 + x_2 \equiv y_1 + y_2 + y_3 \pmod 3. $$ For $k=0, 1, 2$ define $$ s_k = \Big| \{ y_i \,|\, y_i \equiv k \pmod 3 \} \Big| - \Big| ...
1
vote
1answer
101 views

What is the probability to find exactly $4$ trios of people that have the same birthday? (from $k$ people)

What is the probability to find exactly $4$ trios of people that have the same birthday? (from $k$ people). I was asked to solve this using the Inclusion–exclusion principle. Can anyone please help ...
3
votes
1answer
123 views

Combinatoric Coefficients of a Polynomial

I have the following function: $$f(x)=\left(T_{N_2}(x)-T_{N_1}(x)\right)\left(T_{N_3}(x)-T_{N_1}(x)\right)\left(T_{N_3}(x)-T_{N_2}(x)\right)$$ where $T_{N}(x)=1+x+\frac{x^2}{2!}+...+\frac{x^N}{N!}$ ...
1
vote
2answers
73 views

Does this function have closed form?

Define $$f(p,n)=\sum_1^n s_i$$ where $s_i$ is defined as the maximal integer value such that $i= p^{s_i}r_i$ for integer $r_i$. For example, we'd have $$f(2,15)=\sum_1^{15} s_i=1+2+1+3+1+2+1=11.$$ ...
1
vote
2answers
67 views

Strategy to find out how wires are connected

There is a tube with $100$ electrical wires that are not labeled. At side $A$ of the tube, the terminal ends of the $100$ electrical wires can be connected. It is possible to connect more than $2$ ...
0
votes
0answers
31 views

Maximum flow problem with non-zero lower bound

Given G = (V,E ) a directed graph, if $ X \subseteq V $ we note with $\delta ^{+}\left(X\right)$ = $\left \{ xy\in E \mid x \in X, y\in V - X \right \}$ and $\delta ^{-}\left(X\right)$ = $\delta ...
0
votes
2answers
54 views

Why the sequence generated by $x+e^x$ is $(1,x,\frac{x^2}{2!},\frac{x^3}{3!},\frac{x^4}{4!}\ldots)$?

I am trying to find the sequence generated by $x+e^x$. I have the sequence generated by the function $e^x$ which is $\displaystyle (1,x,\frac{x^2}{2!},\frac{x^3}{3!},\frac{x^4}{4!},\ldots)$, as for ...
2
votes
0answers
64 views

An expression for the number of n-bit binary strings with at most k ones (without summations)

Say we need to find an expression for the number of binary strings of length $n$, which have at most $k$ ones. My solution was to split the problem into $k+1$ cases, where the number of ones, ...
6
votes
5answers
3k views

How to show that this binomial sum satisfies the Fibonacci relation?

The binomial sum $$s_n=\binom{n+1}{0}+\binom{n}{1}+\binom{n-1}{2}+\cdots$$ satisfies the Fibonacci relation. I failed to prove that $\binom{n-k+1}{k}=\binom{n-k}{k}+\binom{n-k-1}{k}$... Any ...