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
19 views

Dirichlet's principle- task.

Given is set $S$ where $|S| = n > 1 $ and his subsets $M_1, ..., M_{n+1}$ such that $M_i \neq M_j, i \neq j $ Using Dirichlet's principle prove that exists $A, B$ where $A,B \subset \{1,...,n+1\} $ ...
3
votes
1answer
80 views

Stars and Bars problem involving odd restriction, and equal or greater than restriction.

I just had this question in an exam and was unsure how to complete some parts using the Stars and Bars method. Problem as follows: How many solutions has the equation: $x_1 + x_2 + x_3 + x_4 + x_5 ...
0
votes
2answers
39 views

Is this proposition posible? [duplicate]

In a board, you have $13$ White round pieces, $15$ Black round pieces, and $17$ Red round pieces. In each round you can choose two different color pieces and change them with two other pieces of ...
1
vote
0answers
40 views

Taking derivative of a partial bell polynomial?

I am trying to prove a statement that involves me taking the derivative of a bell polynomial. Is there an elementary way to express: $$ \frac{d}{dx}[ B_{n,k}(x_1,x_2,....,x_{n-k+1})] $$ Where you ...
2
votes
0answers
47 views

A list of numbers and

I have a real life problem that math may be able to solve. I am no mathematician so if you have any insight please use the simplified version. This problem is way beyond me. My gut tells me there is ...
3
votes
0answers
47 views

How many ways to place 3 non-attacking bishops given the following conditions

How many ways are they to place 3 non-attacking bishops on an $n \times n$ board such that $2$ of these bishops are placed within the $(n-1) \times (n-1)$ board and the other 1 is placed outside of ...
2
votes
1answer
42 views

How many different ways are there from $(0,0,0)$ to the point $(4,3,5)$?

I had an exam in my introduction to combinatorics lectures today, there was a question like this: In the $3D$ space, consider the points of integer coordinates. Using only moviments corresponding ...
0
votes
2answers
76 views

The probability of throwing the total of at least $16$ with $4$ dice

The probability of throwing the total of at least $16$ with $4$ fair dice? It seems difficult to count the favorable outcomes manually, because there are $6^4 = 1296$ outcomes in total, and with ...
0
votes
0answers
11 views

Split Question: Bergelson multiplicative density of evens and powers of 2

This post splits the post: Questions about Bergelson multiplicative upper density into one more concentrated series of questions. It is largely copied directly. Let $\mathbb{P} \subset \mathbb{N}$ ...
1
vote
2answers
620 views

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s.

A) Find a recurrence relation for the number of n-digit binary sequences with no pair of consecutive 1s. (A binary sequence only uses the numbers 0 and 1 for those who don't know) B) Repeat for ...
2
votes
0answers
27 views

Split Question: Bergelson Multiplicative Density of “Even-like” sets

This post splits the post: Questions about Bergelson multiplicative upper density into one more concentrated series of questions. It is largely copied directly. Let $\mathbb{P} \subset \mathbb{N}$ ...
2
votes
1answer
37 views

A specific group lacking Følner sequences

How does one go about proving that the free group $<a,b,a^{-1},b^{-1}>$ lacks any Følner sequence?
5
votes
5answers
2k views

How many even 3 digit numbers contain at least one 7.

How many even 3 digit numbers contain at least one 7. I got 126, but it was not an answer choice for the problem. Can anyone help?
0
votes
0answers
21 views

Question about a possible relationship between additive and Bergelson multiplicative upper densities

Let $A \subseteq \mathbb{N}$; let $\mathbb{P} \subset \mathbb{N}$ be the set of all primes. Let $\forall n \in \mathbb{N}, F_n = \{a_n \prod_{i=1}^n (p_i^{r_i}): a_n \in \mathbb{N}, p_i \in ...
0
votes
1answer
52 views

How to show a number is not a sum of squares

I've been tasked with the following: Let $m$ and $n$ be positive integers, prove that $4^{n}(8m+7)$ cannot be written as the sum of three squares. I've already gotten the idea that I should do ...
1
vote
2answers
89 views

Flipping a coin until 4 heads occur, or until flipped 7 times. How many combinations are possible?

Question: A coin is tossed until either 4 heads occur or until the coin has been tossed 7 times. How many heads/tails sequence are possible? For example, HTHTTHT, HHHH, THHTHH, and TTTTTTT are all ...
1
vote
2answers
32 views

Probability of selecting three of the same thing from a collection

Question: A collection of 6 items is to be randomly drawn from a bin containing 100 good items and 8 defective items. What is the probability that exactly 3 of the items chosen are defective? My ...
1
vote
1answer
62 views

How often do I need to draw until all balls in an Urn are of the same color?

Suppose there is an Urn with $n$ balls, $m$ being white and $(n-m)$ being black. Now we draw $c, c < n$ balls - any white ball drawn will be colored black - then we put all balls back into the Urn ...
1
vote
2answers
159 views

How many non-decreasing sequences of finite length do exist?

Given a finite set of numbers $A=\{1,2,\dots,k\}$. How many sequences $a_{1} a_{2}...a_{n}$ of length $n$ with $a_i\in A$ and $a_i \le a_{i+1} $ for $i\in \{1,\dots,n-1\} $ do exist? Obviously, if ...
2
votes
3answers
77 views

Proving a Binomial Sum

How do I prove that $$\sum_{r=0}^{n-1}\left[ r \binom{n}{r} \binom{n}{r+1}\right]=n \binom{2n-1}{n-2}$$ without induction? I've tried manipulating $(1+x)^n$ and the binomial coefficients, but to no ...
2
votes
1answer
303 views

Counting binary strings that have atmost k consecutive 0's

I know how to count how many binary strings with length n and having exactly k 0's are there but i am not able to find a way to count the number of binary strings that have exactly x 0's and y 1's and ...
0
votes
0answers
58 views

number of pairs of equal elements in the sample

Version 1: let $P$ be a discrete probability distribution with support over whole $\mathbb{N}$. What is the probability of having exactly $m$ pairs of equal items in a sample of size $n$ drawn from ...
1
vote
1answer
53 views

Queens on a chessboard

What is the smallest number of queens that can be placed on a chessboard so that every square is either occupied or can be reached in one move?
1
vote
1answer
57 views

Obtuse triangles in a regular polygon

How many triangles formed by three vertices of a regular $17$-gon are obtuse? As an extension, how many triangles formed by three vertices of a regular $n$-gon are obtuse?
0
votes
1answer
54 views

solving a inclusion-exclusion problem

Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such that their GCD is 1. For example,N=10 and the positive integers are ...
0
votes
1answer
37 views

proof of a formula

I need combinatorial approach to prove the following formula.I read books and internet articles but I didn't find a satisfactory explanation.Here is the formula to calculate ordered bell numbers. I ...
3
votes
3answers
149 views

What's the probability of a straight in $5$ card poker given $5$ and $7$ of hearts?

Using a standard $52$ card deck, if you are given the $5$ and $7$ of hearts from it, what is the probability that you end up with a straight if $3$ additional cards from that same deck are given to ...
2
votes
2answers
534 views

Permutations / Combinations - suppose a word is a string of 8 letters of the alphabet with repeated letters allowed

1.) How many words are there? Not sure how to solve this since repeated letters are allowed. $n^r$ is the formula we are told to use for permutations with repeated objects, but $26^8$ seems like too ...
1
vote
1answer
24 views

Combinatorics problem

I am trying to solve this question, my solution involves solving a combinatorial problem as follows : Number of arrangements of exactly k distinct elements in n slots such that each one of the ...
0
votes
0answers
43 views

Approximation for fewest incompatibilities in a task scheduling selection algorithm

Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal ...
0
votes
1answer
52 views

Making reccurence relation

I have trouble in understanding how to make recurrence relations. I read some of the questions on stack exchange but this stuff is not intuitive to me. For example, when we want to find a number of ...
1
vote
2answers
81 views

Proving a combinatorics equality

How to prove the following? Should I use induction or something else? Let n and r be positive integers with n ≥ r. Prove that $${\binom{r}{r}} + {\binom{r+1}{r}} + · · · + {\binom{n}{r}} = ...
2
votes
2answers
67 views

Total possible combinations of primes

I have been working on a problem as follows: Do there exist 100 consecutive natural numbers none of which is prime? I know that the answer is 'yes', by considering 101!, and noting the sequence 101! + ...
1
vote
2answers
27 views

Trying to find polynomial-time algorithms for knapsack-like problems

Consider two related problems: You have $n$ cannisters that must go into $m$ trucks that can each carry $k$ cannisters. You require that no truck becomes overloaded, and for each cannister, there is ...
0
votes
1answer
84 views

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we're given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise ...
1
vote
0answers
46 views

möbius function on poset

Let $P$ be the poset of all subsets of $\{1,2,\ldots, n\}$ with av even number of elements, ordered by inclusion. There is a recursive formula for the Möbius function on a poset: $$ \mu(x,y) = ...
2
votes
1answer
144 views

Fight against the Hydra - Graph Theory

The following problem is supposed to be a nice application of the basic knowledge of graph theory. I consider it however as difficult and I would be happy if someone could help me find a solution. ...
0
votes
0answers
38 views

inverse element in incidence algebra of a poset

This question is from Stanley's Enumerative combinatorics vol 1, excercise 3.90. Let $P$ be a finite graded poset. Let $m(s,t)$ denote the number of maximal chains from $s$ to $t$, and $l(s,t)$ the ...
2
votes
3answers
57 views

Understanding a Summation

Can someone help explain why the following holds? $$ \sum_{j=0}^{k}\left[(k-j)\frac{a^{k-j}}{(k-j)!}\frac{(1-a)^j}{j!}\right] = \frac{a}{(k-1)!} $$ I can't quite work through this, and my teacher ...
4
votes
3answers
275 views

Combinations of pizza toppings with at least one vegetable and at least one meat.

Here is a question from my quiz: Superior Pizza has seven vegetable ingredients and nine meat ingredients. The number of ways to select five ingredients (no doubling on ingredients) with at ...
0
votes
2answers
165 views

Combinations - 17 women and 21 men to form a committee of size 7

How many committees are possible if a committee must have $3$ women and $4$ men? $_{38}C_3+_{38}C_4$ or $\frac{38!}{3!35!}+\frac{38!}{4!34!} = 8,435+73,815 = 82,251$ How many committees are possible ...
1
vote
1answer
82 views

Pigeon-Hole Principle and 2d grid

Q:Consider the 2D grid with integer coordinates.Prove that if we take 5ve points on the grid then there exist two of the points whose average is also a point on the grid. I understand the basic idea ...
5
votes
0answers
52 views

Degree distribution of a graph of integer partitions

Consider a graph whose nodes are the integer partitions of $n$, connected by an edge if you can get from one partition to the other by ‘sliding one square of its Young diagram’ – that is, if one ...
0
votes
1answer
283 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
0
votes
2answers
154 views

Find a recurrence relation for the number of ways to go n miles by fast walking at 2 miles per hour or

A) Find a recurrence relation for the number of ways to go n miles by fast walking at 2 miles per hour or jogging at 4 miles per hour or running at 8 miles per hour; at the end of each hour a choice ...
0
votes
2answers
30 views

Partitioning graph edges into two cycleless sets

Given a directed graph $G=\left(V,E\right)$, provide an algorithm that partitions $E$ into two disjoints sets $E_1,E_2$ such that $E=E_1\cup E_2$ and $G(V,E_1)$, $G(V,E_2)$ have no cycles. The ...
1
vote
2answers
42 views

Probability that the numbers on the tags marked $ 1; 2;…; n$ will be consecutive integers.

A random box contains tags marked $ 1; 2;...; n$. Two tags are chosen at random with replacement. Find the probability that the numbers on the tags will be consecutive integers. My Attempt Case I: ...
2
votes
1answer
33 views

Remainder of a combination

Problem from a contest: What is the remainder when $\binom{169}{13}$ is divided by $13^5$? I thought that Wolstenholme's/Babbage's would help, but not entirely sure how.
1
vote
1answer
80 views

Problem on Möbius function on a finite poset

I try to solve excercise 3.129 in Stanleys Enumerative combinatorics vol 1. The problem is the following: Let $P$ be a finite poset, and let $\mu$ be the Möbius function of $P \cup \{ ...
0
votes
1answer
27 views

hi, for an independent event, like flipping a fair coin does Pr(A|B) always equal to Pr(B|A)?

for an independent event, like flipping a fair coin does Pr(A|B) = Pr(B|A)? Example You flip a fair coin, independently, three times, Event A. The first flip results in heads Event B. The coin ...