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)

3
votes
1answer
33 views

How many integers from 43523 to 93107 contain at least one digit 7

How many integers from $43523$ to $93107$ contain the digit $7$ at least once? I know that if we had $43000$ to $93000$, we would subtract integers that do not contain digit $7$ from the total ...
2
votes
2answers
49 views

Number of ways of visiting N places

A tourist wants to visit $N$ cities, each numbered from $1$ to $N$, but he wants to visit them in a weird order. A weird order is such in which no city numbered $i$ is the $i$-th to visit in his ...
3
votes
1answer
27 views

How many straight lines can be made between 10 points such that 4 of them are colinear?

So i know how to get the answer. We just have to find $C(10,2)$ and subtract $C(4,2)$ and add 1. We are basically counting all the points between co-linear points as 1. So the question is why we are ...
1
vote
1answer
20 views

How many different arrangements of triangles that are either red or blue around a regular heptagon are possible?

I have the following problem I have an yellow heptagon (regular $7$ sided polygon) Against every side there is a triangle. The triangle is either red or blue. How many different arrangements of ...
1
vote
3answers
6k views

soccer betting combinations for accumulators

I would like to bet on soccer games but I would like to place a bet on every combination possible. For example, I bet on $10$ different games, and each soccer match can go three ways: either a win, ...
1
vote
0answers
17 views

Number of ways to get from a point to another one in the plane

I was trying to solve the following problem related to "counting cases": Consider the point $(0,0)$ in the plane and another point $(m,n)$ with $m,n>0$ integers. Suppose you want to get from the ...
1
vote
1answer
51 views

A sum of Stirling numbers of the second kind

Find a formula (either exact or asymptotic in $N$) for $S(N)$, where \begin{equation} S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}. \end{equation} ...
1
vote
0answers
16 views

Real world uses or interesting facts about/for Associahedron or Permutohedron

I'm doing a small research project into these but their Wiki page and other pages I've looked at just detail what they are, and their properties. Does anyone know of any real world applications or ...
3
votes
1answer
4k views

Sum of combinations of n taken k where k is from n to (n/2)+1

I wonder if there's a formula for obtaining the sum of $n\choose k$'s where $k$ is from $n$ to $\frac{n}{2}+1$. I found out that in odd numbers, it is $2^{n-1}$ (powerset divided by $2$). 1 = 1 3 = ...
0
votes
3answers
56 views

How many distinct ways can the number be written as product of $3$ factors?

How many distinct ways can the number $126$ be written as a product of $3$ positive integer factors? I found that the prime factors are $126=2\times3\times3\times7$. But how to get number of ...
2
votes
1answer
18 views

For each of the following restrictions, find the smallest size n for strings over $\{a, b, c\}$ that can be used as codes for $27$ people.

For each of the following restrictions, find the smallest size $n$ for strings over $\{a, b, c\}$ that can be used as codes for $27$ people. a. There are $k$ $a$’s, $l$ $b$’s, and $m$ $c$’s and $k + ...
3
votes
2answers
37 views

What is probability that out of the first half on N objects, none will be matched with their own label?

The problem: We have N (even) objects ordered $o_1 ... o_N$ , each having their own label. The labels are reassigned to the objects randomly. What is the probability that that neither of the first ...
1
vote
0answers
20 views

The Divisors of $s(2s+1)$ and Primes $n$, $4n+1$, and $6n+1$

This question is somewhat related to this one. Most of this is by way of a computer search: claim: If $s$ is any positive integer I write $\varphi_{s} =s(2s+1)$. Let $\tau$ be the divisor ...
1
vote
1answer
20 views

What is the probability Amy wins a lottery prize for correctly choosing 5, not six, numbers…

Here is the full question: What is the probability that Amy wins a lottery prize for correctly choosing 5, not six, numbers out of six integers chosen at random from the integers between 1 and 40 ...
2
votes
1answer
13 views

Half primes in the set

Let S be 30 element subset of {1,2,....2015} such that every pair of elements in S are relatively prime. Prove that at least half of the elements in S are prime numbers
5
votes
2answers
94 views

If we are given that a list of $n$ numbers has $11,660$ derangements, what is the value of $n$?

The Full Question For the positive integers $1,2,3,\dots n-1,n$, there are $11,660$ where $1,2,3,4,5$ appear in the first five positions. What is the value of $n$? My Work First I considered all ...
0
votes
0answers
25 views

Combinatorial Nullstellenatz riddle

I've been unable to solve the last problem here: http://www.mit.edu/~evanchen/handouts/BMC_Combo_Null/BMC_Combo_Null.pdf Let $n ≥ 2$ be even and let $v_1, v_2, . . . , v_k ∈ \{±1\}^n$ be vectors of ...
26
votes
6answers
307 views

You have to estimate $\binom{63}{19}$ in $2$ minutes to save your life.

This is from the lecture notes in this course of discrete mathematics I am following. The professor is writing about how fast binomial coefficients grow. "So, suppose you had 2 minutes to save your ...
0
votes
0answers
8 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
46 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
19 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
23 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
36 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
21 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?
5
votes
1answer
95 views
+100

Counting the number of rank $r$ binary $n \times k$ matrices that has unique columns

I'm trying to figure out how many ways there are to construct a $k \times n$ binary matrix such that it has rank $r$ and no column is repeating. I've tried a bunch of different approaches. The attempt ...
3
votes
2answers
41 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
23 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
37 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
35 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 ...
4
votes
3answers
84 views

Winning All Levels in a Game

There are $L$ levels in a game. In each turn of the game, you go through each level one by one and try to complete it. The goal is to complete all levels of the game. The probability of completing any ...
3
votes
0answers
67 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, ...
-3
votes
2answers
39 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
18 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
21 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!
7
votes
0answers
254 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
47 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
31 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
216 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
40 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
40 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
38 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
23 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
21 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 ...