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)

1
vote
1answer
144 views

Would this proof strategy work for proving the lonely runner conjecture?

The problem is the lonely runner conjecture. This conjecture states that if $k$ runners begin running down a circle of unit circumference with random speeds, it will always the case that all runners ...
1
vote
0answers
15 views

Use the 'rule of sum to prove that $\sum_{k=0}^n 2^k=2^{n+1}-1$.'

I'm attempting a combinatorics problem that asks to use the 'rule of sum to prove that $\sum_{k=0}^n 2^k=2^{n+1}-1$.' The rule of sum says that 'if $S=\cup_{i=1}^t S_i$ is a union of disjoint sets ...
0
votes
1answer
45 views

Counting non-overlapping substrings of size 2 and 3 in a string

Given a string S of length n that contains exactly $\lceil \frac{n}{4} \rceil $ b's and $\lfloor \frac{3n}{4} \rfloor$ a's: Part 1: How many NON-overlapping occurrences of aa must occur in S? For ...
2
votes
2answers
406 views

A cog wheel math puzzle

A machine has 4 cog wheels in connection. The largest wheel has 242 teeth and the others have 66,48 and 26 respectively. How many rotations must the largest wheel make before each of the wheel is back ...
4
votes
3answers
95 views

Show that $ \sum_{k=0}^{r} \binom{r-k}{m} \binom{s+k}{n} = \binom{r+s+1}{m+n+1} $?

I can't resolve this exercise and I need a tip. $$ \sum_{k=0}^{r} \binom{r-k}{m} \binom{s+k}{n} = \binom{r+s+1}{m+n+1} $$ where $ n \geq s $.
1
vote
0answers
13 views

Sampling substrings of a beaded necklace to determine the necklace composition

I have a necklace composed of 100 beads, where each bead is one of 13 colors. If I am only able to look at one 4 bead sub-sequence at a time (connected, as they would be on the necklace) , how many ...
2
votes
4answers
59 views

Show that there is a number on the form $11 \dots 000 \dots 0$ divisible by 2014

Show that there is a number on the form $11 \dots 000 \dots 0$ (some number of $1$s followed by $0$s) divisible by $2014$. I'm helping someone practise for the math olympiad, and this question has me ...
7
votes
1answer
174 views

If $G$ is shellable, then $G \backslash \{x_i\}$ is shellable?

A simplicial complex $\Delta$ on the vertex set $\{x_1,\dots,x_n\}$ is shellable if the facets of $\Delta$ can be ordered, say $F_ 1 , . . . , F _s$, such that for all $1 \leq i < j ...
1
vote
0answers
19 views

The probability that two matrix vector products are equal

Consider a random $n$ by $n$ circulant matrix $M$ whose first row entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first ...
1
vote
2answers
34 views

Looking for set of combinatorics problems

I'm preparing to Mathematics for Computer Science exam. What I learned from past edition of exams is fact of very often occurence of old problems. I mean more or less known problems, but possible to ...
1
vote
2answers
305 views

Probability of picking specific balls

Suppose I have $20$ red balls in one box and $20$ blue balls in another box. There $12$ red balls and $7$ blue balls have stars on them. I randomly take out one red ball and one blue ball at each ...
0
votes
1answer
20 views

Number of partitions containing $k$ occurrences of a given number

Consider the ordered partitions of $N$ with size $m$ ($m \leq N$), that is, the set $\mathcal{P}_m^N$ of all vectors $\vec{n} \in \mathbb{N}^m$ such that $\sum_{i=1}^m n_i = N$. In how many of these ...
0
votes
2answers
639 views

number of ways to divide an array into m sets of equal sum

I recently came across this question: Find the number of ways to divide and array into m subarrays of equal sum? Ex: given a[]= {1, 1, 2, 3, 4, 5}, m= 2 ...
2
votes
0answers
27 views

Number of “left-to-right” walks on a line graph

Let $G_n$ be the line graph on $n$ nodes. An example when $n=4$: Let $a_n(k)$ be the number of walks on this graph of length $k$, which start at node $1$ and end at node $n$. $a_n$ satisfies a ...
0
votes
2answers
26 views

Anagrams contained within random strings

What is the probability that a random string of length $n$ will contain an anagram of a shorter string of length $k$? E.g., you generate a string of 50 random letters, repetitions allowed, what are ...
0
votes
1answer
17 views

What is the number of unique labeled connected graphs with N Vertices and K edges?

I've seen this question several times, and this one caught my attention. I'm now aware that there is no closed formula for this. My knowledge of graph theory is limited, and I wasn't able to find an ...
2
votes
1answer
268 views

Probability or Set

I'm really good at probability, but this time I seems like I'm not. My friends asked me a very tricky question, and I want to see if there's anyone who can find out the answer. Here's the ...
-3
votes
1answer
66 views

Pigeonhole Principle proving [on hold]

Suppose that there are 30 people in the room. Assume that everyone in the room has at least one acquaintance. Show that there are two persons in the room who have equal numbers of acquaintances. Since ...
2
votes
1answer
28 views

count permutations that do not contain repeated combinations

I am trying to count the number of permutations that do not contain order specific groupings that have occurred in permutations that have already been counted. Example: For the set {A B C D E}; if ...
2
votes
3answers
460 views

hotel occupancy counting problem

The multiple-choice question: A hotel has four vacant rooms. Each room can accommodate a maximum of four people. In how many different ways can six people be accommodated in the four rooms? (A) 4020 ...
0
votes
2answers
47 views

Calculating the number of ways to arrange a set of letters such that no two identical letters can occur consecutively

How can I find the number of ways in which the letters $$z,z,y,y,x,x,w,w,v,v$$ can be arranged so that two letters of the same kind never appear consecutively. I am not confident that my approach is ...
2
votes
2answers
303 views

Deriving recursion from generating function

Given a generating function for some sequence, I'm basically interested in the first few values. Well an explicit closed form would be nice, but often there isn't any. I suppose if there is any, I'd ...
10
votes
0answers
66 views
+100

Congruent quadrilaterals in a tri-colored $72$-gon

I recently watched a movie (A Brilliant Young Mind) in which this problem appeared: Let the vertices of a regular $72$-gon be colored red, blue, and green in equal parts. Show that there are $4$ ...
2
votes
2answers
37 views

Soft Question: Combinatoric reading material

I am curious if anyone can recommend a good introductory text on combinatorics in similar vein as Richard J. Trudeau's Introduction to Graph Theory put out by Dover. For those who have not read it, ...
1
vote
1answer
30 views

elementary problem in combinatorics

Let $X=\{1,2,3,4,5,6,7,8,9,10\}$ and $R$ be a set defined by $$\{(x,y)\in X\times X: \text{$x$ and $y$ have the same remainder when divided by $3$}\}$$ Then what's the numbers of elements in $R$? My ...
3
votes
5answers
101 views

Proof check: $(4n)!$ is divisible by $2^{3n}3^{n}$

Question: Show that $(4n)!$ is a multiple of $2^{3n}3^{n}$ for all $n$. Proof: It's easy (involves kinda messy calculation tho) to show by induction that $(4n)!$ is a multiple of $2^{3n}$. Now, since ...
1
vote
2answers
30 views

Why the Ramsey number $R(2,4)$ is not equal to $2$?

I'm reading Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory. Here: I don't understand: For all $2$-colorings, it must have a $K_p$ and $K_q$ or it must have a $K_p$ or a $K_q$? I'm ...
-1
votes
1answer
46 views

Polynomial in $x$ problem

please help me solve this problem: a polynomial in $x$ is defined by $$a_0 + a_1x + a_2x ^ 2 + ... + a_{2n} \, x^{2n} = (x + 2x^2 + ... + nx^n) ^ 2 .$$ Show that: $$\sum_{n + 1}^{2n}a_i = n(n + ...
6
votes
2answers
57 views

How to draw the 5 dimensional hypercube graph with 56 edge crossings?

I'm probably doing something stupid but I can't seem to think of a way to draw $Q_5$ with $cr(Q_5) = 56 $. In this paper the author says drawing a hypercube graph with $\leq56$ edge crossings is easy ...
4
votes
1answer
42 views

How many ways to arrange m chosen objects when there are n total objects, and some are indistinguishable?

I have $n$ different types of objects, where each member of a type is indistinguishable from every other member. There are $k_1$ of the first type, $k_2$ of the second type, and so on, up to $k_n$ of ...
14
votes
13answers
3k views

Show that from a group of seven people whose (integer) ages add up to 332 one can select three people with the total age at least 142. [on hold]

I need help with this problem, and I was thinking in this way: $$ x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} = 332 $$ and I need to find three of these which sum is at least 142. But I ...
4
votes
2answers
437 views

Give the combinatorial proof of the identity $\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$

Given the identity $$\sum_{i=0}^{n} \binom{k-1+i}{k-1} = \binom{n+k}{k}$$ Need to give a combinatorial proof a) in terms of subsets b) by interpreting the parts in terms of compositions of ...
2
votes
4answers
2k views

Fermat's Combinatorial Identity: How to prove combinatorially? [duplicate]

$$\binom{r}{r} + \binom{r+1}{r} + \binom{r+2}{r} + \dotsb + \binom{n}{r} = \binom{n+1}{r+1}$$ I don't have much experience with combinatorial proofs, so I'm grateful for all the hints. (Presumptive) ...
5
votes
4answers
134 views

Combinatorial Proof for Binomial Identity: $\sum_{k = 0}^n \binom{k}{p} = \binom{n+1}{p+1}$ [duplicate]

I am studying combinatorics and I came across the identity $$\sum\limits_{k=0}^n \binom kp =\binom {n+1}{p+1}.$$ I have read the algebraic proof and it does not appeal to me. Is there an elegant ...
0
votes
0answers
41 views

partitions and generating functions ( combinatorics ) [on hold]

Given partition into distinct parts, let’s say the the ODD parts are: the biggest part, the $3$-rd biggest part, the $5$-th biggest part, etc.; and the EVEN parts are: the $2$-ne biggest part, the ...
0
votes
0answers
31 views

Gambler's Ruin With a Pay Schedule

I am curious about how to calculate the expected number of games until a gambler with $B$ dollars gets to $M>B$ dollars, or gets ruined. I am also curious how to calculate the probability of ruin. ...
1
vote
1answer
39 views

Generating Series and Recurrence Relation and Closed Form

We have the following recurrence relation: $b_n=2b_{n-1}+b_{n-2}$ and initial conditions $b_0=0, b_1=2$ I use the generating series method to solve as following: Let ...
11
votes
2answers
197 views

Smallest integer $k$ so that no Sudoku grid has exactly $k$ solutions

Inspired by this question, consider hints on a Sudoku board. A regular puzzle has a unique solution. It is clear that there are puzzles with 2 or 3 solutions, and therefore, I guess, puzzles with say ...
0
votes
3answers
55 views

recurrence relations and generating functions - I need a hint

I need to find "closed form" to the recurrence relation given by: $a_{n+1} = \sum_{k=0} ^ {n} k a_{n-k}$ and $a_0 = 1$. I have tried using generating functions but it is no good. Any help would be ...
1
vote
1answer
38 views

How many ways can an integer $i$ appearing in a sequence with multiplicty at least $j$, be minimal

Let us construct an integer sequence of length $n$, where the integers are chosen from $\{1, 2, ..., k\}$, with i.i.d. uniform probability $\frac{1}{k}$. I want to compute the probability ($p_{ij}$) ...
0
votes
1answer
20 views

Different sums by adding the currency.

How many different sums can be formed by the following $5$ dollar, $1$ dollar, $50$ cents, $25$ cents, $10$ cents, $3$ cents, $2$ cents, $1$ cent. As there are $8$ different things and at ...
6
votes
5answers
694 views

Given 5 integers show that you can find two whose sum or difference is divisible by 6.

I'm trying to solve this problem using the pigeon hole principle. When dividing an integer by 6 there are 6 different remainders, {0, 1, 2, 3, 4, 5}. Seeing as there are the same number of "holes" ...
2
votes
3answers
29 views

The number of times will an individual child goes to the cinema before a group is repeated.

$1.)$ A mother with $7$ children takes $3$ at a time to a cinema.She goes with every group of $3$ that she can form.How many times can she go to cinema with distinct groups of $3$ children? ...
2
votes
4answers
61 views

Random number function (counting)

I have task I can't get my head around, even with a suggested answer. You have a function the generates a random integer between $0 - 65535$. Your task is to generate random integers $125-525$ ...
1
vote
0answers
18 views

Euler Integral of a self-overlapping tube with a cusp singularity

I am studying in depth the following paper on Euler calculus applied to target enumeration: https://www.math.upenn.edu/~ghrist/preprints/eulerenumerationpart1.pdf Within this paper there is an ...
3
votes
0answers
31 views

Maximum difference between tails in absolute value

I toss a fair coin $n$ times. Some notation: $S_i=$ difference between #heads and #number of tails after the first $i$ tosses, $1\leq i\leq n$. $M_n=\max(S_1,S_2,\dots,S_n)$, ...
-8
votes
0answers
47 views

identity permutations [on hold]

I need some help with the following question : For the permuation $ π $ on n elements we define the term : $ π^k=i $ if the composition of π on it self k times is the identity permutation . (where ...
0
votes
0answers
38 views

Number of ways to put hat(s) in $5$ boxes.

If their are two kinds of hats , red and blue and at least $5$ of each kind, in how many ways can the hats be put in each in each of the $5$ different boxes. I assumed that their are $10$ hats ...
4
votes
3answers
56 views

Chart of Rounds for a Game

I need to solve the following problem for actual use. 10 people will be playing a game. They play the game 4 people at a time. Each time they play they garner points within the game. Each person ...
0
votes
0answers
31 views

Properties of Coefficients of Order Polynomials

I am working on a problem involving determining the order polynomial $\Omega_P(k)$ of a partial order $P$, which counts the number of order-preserving transformations/maps from $P$ to the $k$-chain ...