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)

0
votes
0answers
11 views

Number of nodes (or vertices) with degree at most average degree + some constant [on hold]

I'm struggling with a problem of graph theory. In any graph I'm trying to compute how many nodes have degree at most average degree + 1 (or some constant independent of the graph). Obviously there ...
1
vote
1answer
51 views

proof by CP$ \binom{m}{1} S_{1}(n)+\binom{m}{2} S_{2}(n)+\binom{m}{3} S_{3}(n)+ \cdots +\binom{m}{m-1} S_{m-1}(n)=(n+1)^m-(n+1)$

I would appreciate if somebody could help me with the following problem: Q: How to Proof (by combinatorial proof) $$ \binom{m}{1} S_{1}(n)+\binom{m}{2} S_{2}(n)+\binom{m}{3} S_{3}(n)+ \cdots ...
2
votes
1answer
21 views

Understanding derangement.

From the inclusion-exclusion principle we get that out of $N$ objects with one label each, there is a probability of $$\sum_{k=1}^N (-1)^{k+1}\frac{1}{k!}$$ that a random assignment of the $N$ labels ...
0
votes
1answer
26 views

Number of non periodic strings

How many non-periodical strings of length N with letters from a to z exist? My only idea was something about prime factorization to find the amount of periodical strings of length N.
2
votes
1answer
37 views

How does the multiplication law creates order?

I have the following question : There are $2n$ students divided to couples to do homework. Using the multiply law we can choose the first couple then the second then the third couple and so on. The ...
0
votes
0answers
22 views

arranging $n$ objects of one kind and $m$ objects of other kind in a row

Why are there precisely $\binom{m+n}{n}$ ways of arranging $M$ objects of one kind and $N$ objects of other kind in a row?
3
votes
2answers
47 views

How many onto functions are there from a set with $5$ elements to a set with $3$ elements? [on hold]

Consider functions from a set with $5$ elements to a set with $3$ elements. (a) How many functions are there? (b) How many are one-to-one? (c) How many are onto? a) Each element mapped to $3$ images. ...
0
votes
1answer
32 views

What book about algebraic combinatorics is it?

Recently I found a fragment of a book about algebraic combinatorics on the internet coincidentally. And I found it's really an excellent resource of learning polynomial method, about Combinatorial ...
0
votes
0answers
43 views

Confusion About “Stars and Bars” Method

Let's suppose I were trying to count the number of nonnegative integer solutions to the equation $x+y<2k$ for $x,y,k$ nonnegative integers. This is, of course, equivalent to solving $x+y\leq2k-1$. ...
2
votes
2answers
36 views

Counting the number of ways (variants)

I'm learning about combinatorics and wanted to see if I understand when to apply what methods when it comes to counting the number of ways to distribute x items. There are a lot of concepts I've ...
3
votes
0answers
70 views

Latin squares using fixed word lists

Consider the problem of constructing a latin square of order $N$, using only row and column values from a given word list ($W$) containing some subset of the $N!$ possible word values. For example, ...
-2
votes
2answers
42 views

How many strings of six lowercase letters have at least one vowel?

The English alphabet has $21$ consonants and $5$ vowels. How many strings of six lowercase letters have at least one vowel? My attempt: I'm confused between using combinations and just ...
0
votes
2answers
24 views

Two discrete r.v. problem, joint density

Problem A cook needs two cans of tomatoes to make a sauce. In his cupboard he has $6$ cans: $2$ cans of tomatoes, $3$ of peas and $1$ of beans. Suppose that the cans are without the labels, so he ...
1
vote
0answers
20 views

Basic probability problem with negative binomial distribution

John goes to the grocery. His mother sent him to buy $20$ peaches and requested him to be sure that the peaches were mature. Suppose the probability of a peach of being mature is $p$ and suppose that ...
5
votes
1answer
1k views

Combinatorics - Catalan numbers recursive function proof by induction help

I'm trying to prove that $$C_n = \sum_{i=0}^{n-1} C_iC_{n-i-1}$$ when $1\leq n$ and $C_0 = 1$ by induction. ($C_n$ is the $n$th catalan number). For $n=1$ this is true. Assume it is true for $n=k$: ...
0
votes
0answers
22 views

Find the number of n- digit ternary sequences with at least one instance of consecutive 0's.

I know how to do this problem with binary sequences but I have no idea how to start with ternary sequences. Any help would be great!
8
votes
0answers
264 views

Rotations of a tetrahedron

Let $P$ be a tetrahedron inside an sphere such that all of its vertices are on the surface of the sphere. Suppose that three quarters of sphere's surface is colored black. Show that there is a ...
0
votes
2answers
49 views

how many ways are there to distribute 48 identical balloons to 7 children if each child gets at least one balloon

I understand how to get the generating function (g(x) = (e^x) - 1, I believe) but I am having trouble finding the coefficient. Any ideas?
0
votes
1answer
35 views

A binomial-related inequality

For integer $m\geq 1$, show that: $$\sum_{|k|<\sqrt{m}}{2m \choose m+k}\geq 2^{2m-1}.$$ What I have tried: I tried binomial expansion of $2^{2m}$ but it was unsuccessful. Any other idea?
11
votes
3answers
225 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 ...
1
vote
1answer
46 views

How many distinct patterns exist for a 5x5 grid by filling 3 colors?

Using 3 colors to fill in a $5\times5$ grid (you don't have to use all colors), then how many distinct patterns exist? The "distinct" means we have to consider the symmetry. Any effective approach is ...
2
votes
0answers
23 views

Closed formula involving $q$-binomials

I was working on a combinatorial problem over finite fields, and the following quantity came up $$ \sum_{r=0}^k r\binom{n-k}{r}_q\binom{k}{k-r}_qq^{r^2},$$ where $k,n$ are integers such that ...
1
vote
1answer
76 views

Questions on Erdős–Ginzburg–Ziv theorem for primes and understanding related lemmas and their applications.

While trying to prove the prime case of Erdős–Ginzburg–Ziv theorem: Theorem: For every prime number $p$, in any set of $2p-1$ integers, the sum $p$ of them divisible by $p$. I came across with ...
7
votes
1answer
1k views

How many possible arrangements for a round robin tournament?

How many arrangements are possible for a round robin tournament over an even number of players $n$? A round robin tournament is a competition where $n = 2k$ players play each other once in a heads-up ...
1
vote
1answer
125 views

Generalization of principle of inclusion and exclusion (PIE)

The PIE can be stated as $$|\cup_{i=1}^n Y_i| = \sum_{J\subset[n], J\neq \emptyset} (-1)^{|J|-1} |Y_J|$$ where $[n]=\{1,2,...,n\}$ and $Y_J=\cap_{i \in J} Y_i$. Problems using it are usually reduced ...
4
votes
3answers
41 views

A walk on the chessboard with conditions!

A 16 step path is to go from (-4,-4) to (4,4) with each step increasing in either the x-coordinate or the y-coordinate by 1. How many such paths stay outside or on the boundary of the square ...
-2
votes
1answer
83 views

How to solve given recurrence relation?

From the following recurrence relation: $a_n =- a_{n-1}+8a_{n-2}+12a_{n-3}+25\cdot3^{n-2}-18n^2+48n+14$, for $n\geq3$ Where $a_0=6, a_1 = 0 $ and $a_2=57$. My attempt: I have generated a ...
0
votes
0answers
49 views
+50

Circumscribed Simple Line Arrangements Have Hamiltonian Circuits?

An arrangement of $s$ lines are drawn in the plane so that no three lines intersect at a common point and no two lines are parallel. Now circumscribe this arrangement by a circle so that all ...
1
vote
1answer
24 views

How many ways are there to arrange the letters of word $ALGEBRA$ such that the relative order of the vowels and consonants doesn't change?

I did this question this way :- there are 4 consonants in the words (LGBR) and there are 7 letters in the word. $therefore$ number of in which consonants can be arranged in relative order will be ...
2
votes
1answer
27 views

Why is d in A(n,d) not always equal to 1?

In Communication Theory, for $A(n,d)$ (=the size of a largest code of length $n$ and minimum distance at least $d$), why is $d$ not always equal to $1$? If min. distance $= d$, for any code of length ...
0
votes
2answers
33 views

A question of permutations and combinations with six cards and six envelopes.

Six cards and six envelopes are numbered 1,2,3,4,5,6 and cards are to be placed in envelopes so that each envelope contains exactly one card and no card is placed in the envelope bearing the same ...
1
vote
2answers
47 views

arithmetic mean of smallest numbers of all subsets of r elements formed out of (1,2,..n)

Consider all subsets of r elements of the set $\{1,2,3,......,n\}$ where $1 \leq r \leq n$. Each of these subsets has a smallest member. Let $F(n,r)$ denote the arithmetic mean of these smallest ...
0
votes
0answers
33 views

PhD in Combinatorics (instead of Mathematics) [migrated]

In recent years I have become aware of a few PhD programs specifically in combinatorics and optimization. Most notably, Georgia Tech and Carnegie Mellon both have PhD programs in Algorithms, ...
0
votes
1answer
32 views

Number of cyclic paths in a rectangular grid?

If we start at the down-left corner or equivalently the origin and move only in the first quadrant, using only 4-directional moves, what are the number of ways to make a cyclic routes back to ...
3
votes
1answer
77 views

Proving $\sum_{s \in S} \frac{1}{n}$ converges for $S = \{ s \in \mathbb{N} : s$ has no zeros on its decimal representation $\}$

Consider $S \subset \mathbb{N}$ as the set of numbers which do not have the algarism $0$ on its decimal representation. For instance: $$S=\{1,2, \dots, 9, 11, 12,\dots, 19, 21, 22, \dots\}$$ I want ...
0
votes
4answers
34 views

How many mixed double pairs can be made from 7 married couples provided that no husband and wife plays in a same set?

So for first man there can be 7 possible partners including his wife, for the next man there will be 6 possible partners and so on, $therefore$ for $7$ men and $7$ women, there will be $7!$ possible ...
5
votes
3answers
87 views

Probability with n dice

I'm studying probability and am currently stuck on this question: Let's say we have n distinct dice, each of which is fair and 6-sided. If all of these dice are rolled, what is the probability that ...
0
votes
0answers
15 views

Combinations with up to m repetitions [duplicate]

I have a variation of the standard problem of combinations (order unimportant) with repetitions. The twist is that the number of repetitions is limited. If we take the ice cream flavor example from ...
2
votes
1answer
61 views

Number of permutations in lawn tennis so no husband and wife play together.

In how many ways can a lawn tennis mixed doubles be made up from seven married couples if no husband and wife play in the same set? Please explain the logic.
2
votes
1answer
17 views

Understanding the proof of catalan numbers using lattice paths

I am trying to understand a proof to come up with the catalan numbers presented in the book "A course in combinatorics" by van Lint and Wilson. The authors say that by reflecting the part of the path ...
9
votes
2answers
126 views

A nice and hard colouring problem

This question is a generalization of a problem recently appeared in a Italian mathematical competition. $A$ and $B$ are two coprime integers, both greater than $2$. A non-constant colouring $$ ...
1
vote
2answers
48 views

Counting the number of “distinct” permutations of two sets?

I don't really know how to introduce this question, so I start defining something I needed in order to well understand the problem I met! Let $A$, $B$ two finite sets of distinct elements, with ...
4
votes
0answers
39 views

Find the sum of $\binom{2007}{0}+\binom{2007}{4}+…+\binom{2007}{2004}$ [duplicate]

Find the sum of $$S=\binom{2007}{0}+\binom{2007}{4}+\binom{2007}{8}+...+\binom{2007}{2004}$$ My work so far: $$(1+1)^n=2^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+...+\binom{n}{n}$$ ...
1
vote
1answer
19 views

How do I create a minor of a $K_5$ or $K_{3,3}$ configuration from this $10$ vertex graph?

I have a graph with $10$ vertices, all of which are degree $3$: I am trying to show it is either planar or nonplanar, so I use the circle-chord method to create a circuit $abcdefghija$ (easy since ...
1
vote
1answer
16 views

There are 14 identical objects that will be placed into 3 boxes. In how many ways can this be done?

For this combination problem, I used the formula for combination (n + k - 1) choose (k - 1) to get the answer of (14 choose 2). Is this correct? If not, can someone explain what I did wrong?
0
votes
1answer
15 views

Is this the correct way of drawing a combinatorial circuit based on the disjunctive normal form and logic table?

The logic table: $$\begin{array}{|c3:c|}\hline x & y & z & f(x,y,z) \\\hline 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & ...
3
votes
0answers
41 views

Probability problem of fishes in a lake

Exercise In order to estimate the number $N$ of fishes in a lake, a fisherman executes the following procedure: in the first step, he captures $n$ fishes and after marking them, he returns them to ...
0
votes
1answer
33 views

Can someone explain the particular solution for non homogeneous recurrence relations?

This is the recurrence relation: $a_n=5a_{n-1} - 6a_{n-2} + 4^n + 2n + 3$ for $n\geq2$ , $a_0 = 5, a_1 = 19.$ I get the general solution. $ c_n = C_12^n+C_23^n.$ The particular solution is in the ...
2
votes
5answers
118 views

How to prove $\frac{1}{1-p}=\sum_{n=r}^\infty {{n \choose r}p^{n-r}(1-p)^r }$

As we know $\frac{1}{(1-p)^{r+1}}=\sum_{k=0}^\infty{{k+r \choose k} p^k}$ and $\frac{1}{1-p}=\sum_{k=0}^\infty {p^k}$. But how to prove $$\frac{1}{1-p}=\sum_{n=r}^\infty {{n \choose r}p^{n-r}(1-p)^r ...
0
votes
1answer
32 views

How many words of length n over the alphabet {a,b,c} such that the sub-word aa does not appear?

The question asks that it be solved as a recurrence relation, as in set up a recurrence relation then determine initial values to give a solution. However I am not really confident setting up ...