This tag is for basic 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 (5)

0
votes
0answers
40 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
37 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
69 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
39 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
1answer
17 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
0answers
19 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
25 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
96 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
27 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
53 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
212 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
36 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
65 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 ...
0
votes
0answers
13 views

At least two elements not in $A_x\cup A_y\cup A_z\cup A_w$

The number of subsets of $T=\{1,2,\ldots,n\}$ is $2^n$. Suppose we pick some of them, $A_1,A_2,\ldots,A_k$, such that for any $x<y<z<w$, at least two elements of $T$ are not in $A_x\cup ...
5
votes
0answers
46 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
15 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
56 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 ...
-1
votes
1answer
62 views

Show that [0,1) is equinumerous to (0,1] by giving an example of a bijection from [0,1) to (0,1] [closed]

Just trying to do my math homework. Need some help. "Show that [0,1) is equinumerous to (0,1] by giving an example of a bijection from [0,1) to (0,1]"
0
votes
2answers
23 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
17 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
30 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
49 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
19 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 ...
3
votes
2answers
44 views

Silly mistake on evaluating the sixth term of $\left (\frac{a}{b}+\frac{b}{a^2}\right)^{17}$?

I am trying to evaluate the sixth term of $\displaystyle \left (\frac{a}{b}+\frac{b}{a^2}\right)^{17}$ with the binomial theorem. I've done the following: The sixth term might be the term for $k=5$ ...
1
vote
1answer
34 views

Two Urns contain white and black balls, drawn using a set of rules. Probability that nth ball drawn is white.

Two urns contain respectively 'a white and b black' and 'b white and a black' balls. A series of drawings is made according to the following rules: (i) Each time only ball is drawn and immediately ...
0
votes
2answers
52 views

Any 3 letters shuffled in a word- What is the probability that the word remains the same? [closed]

A sign reads "ARKANSAS". Three letters are removed and put back into the three empty space at random. What is the Probability the sign still reads "ARKANSAS"?
3
votes
0answers
56 views

Can this summation be expressed differently?

Lets say I have a sum that states the following $$ \sum_{j=0}^{k-c} {k-c \choose j}\ln(a)^{k-c-j} \frac{d^j}{dx^j}[(x)_c] $$ where $(x)_c$ is the falling factorial such that $$ (x)_c = ...
0
votes
0answers
47 views

linear extension of a finite poset

I am trying to solve exc 3.57 in Stanley's Enumerative combinatorics vol 1. The problem is to show that the number $e(P)$ of linear extensions of a finite poset $P$ satisfies $$e(P) \geq ...
3
votes
2answers
38 views

Graph theory - inequality

I'm having troubles solving the following problem which is about proving an inequality in the field of graph theory. We consider G = (V,E) a graph with n a natural ...
2
votes
1answer
18 views

How many possible permutations are possible if ranking n entities using the 'standard competition ranking' strategy?

I don't know if I'm missing something here, but this doesn't look as straightforward to me as I thought it to be. I basically want to calculate the number of unique rankings that are possible when ...
4
votes
2answers
47 views

A sequence $a_i$ such that $|a_1-a_2|,|a_2-a_3|,\ldots$ is also permutation of the positive integers

Let $a_1,a_2,\ldots,$ be a permutation of the positive integers. Is it possible that $|a_1-a_2|,|a_2-a_3|,\ldots$ is also a permutation of the positive integer? My idea is to construct the sequence ...
1
vote
1answer
23 views

Need help in understanding how to solve combinatorial problem involving difference between values

So here is the problem from the book: Y represents the difference between the number of heads and tails from a coin that was tossed k times. We want to know all possible values of Y. Then, say k = ...
-2
votes
0answers
9 views

Why doesnt a (43, 43, 7, 7, 1)-design exist according to the conditions?

I have tested this using the necessary conditions for a BIBD and it's giving me a green light but I know this isn't a design. Why not?
1
vote
0answers
21 views

How many pure trees with a fixed number of nodes exist?

How many pure trees of size (number of nodes) $n$ exist? Apart from having this fixed size, the trees can be arbitrary. The sequence starts like this: Here's the beginning of the sequence:
2
votes
2answers
52 views

Why isn't Mary a victim of the permutation?

I've answered the following question: In a class, there are 8 female students in which one of them is called Mary and seven male students, in which one of them is called John. Considering ...
6
votes
2answers
139 views

What is the coefficient of $x^{25}$ in $(x^3 + x + 1)^{10}$?

Working on some contest problems and came across this question. Here's what I have so far on the off chance that my thinking is correct... So using Vieta's the coefficient of the $x^{25}$ should be ...
0
votes
1answer
30 views

Orthogonal Latin Square

Find a Latin square orthogonal to the following Latin square: 0 2 1 3 2 0 3 1 3 1 2 0 1 3 0 2 I have done this by using trial and error. But my ...
1
vote
1answer
11 views

Given the points $A,B,C,D$ in a straight line $m$ and $A,E,F,G$ in a straight line $n$, how many triangles can be formed with these points?

Given the points $A,B,C,D$ in a line $m$ and $A,E,F,G$ in a straight line $n$, how many triangles can be formed with these points? I've done the following: I've used the following heuristic: ...
3
votes
1answer
107 views

Number of self-avoiding rook walks in a rectangular grid

I was wondering how many self-avoiding rook walks there are on an $m×n$ grid. A self-avoiding rook walk is a path from the bottom left corner to the top right corner of the grid, composed only of ...
2
votes
0answers
24 views

Identifying a function that involves combinations of terms

I need to know if a function exists that partitions terms in such a way as seen below $$ \frac{d^n}{dx^n}[\frac{(x)_c}{n!}] $$ Note that $(x)_c$ is the falling factorial of x and $c \geq n$, This in ...
3
votes
0answers
54 views

The number of partitions by distinct positive numbers

Let $N>0$ be a natural number and let $P(N)$ denote the number of ways to write $N$ as a finite sum of $a_i$ such that the $a_i$ are strictly decreasing positive natural numbers. There is a paper ...
1
vote
3answers
52 views

Combinatorial card game [duplicate]

There is a card game I've played before, where it goes as follows: You take a standard deck of cards, and shuffle them randomly. You then proceed by flipping each card and placing them down, ...
1
vote
0answers
27 views

Number of non-crossing pairs

Let $n,k$ be positive integers. What is the number of sets of $k$ distinct ordered pairs $\{(a_1,b_1),\ldots,(a_k,b_k)\}$ such that $1\leq a_i,b_i\leq n$ are integers, and for no $i\neq j$ is it the ...
0
votes
0answers
50 views

Recurrence of a trapped random walk

i am wondering how behaves a symmetric random walk on $\mathbb Z$ except in $\pm 1$ where it goes towards 0 with probability $p$ and towards $\pm 2$ with probability $ q < p \ (p+q=1)$ ? on which ...
0
votes
1answer
42 views

Order dice rolls in the game of Risk

Last evening I was playing the game of Risk with some friends, and this question came to my mind: Can one order all the possible dice rolls of the attacker (from the best one to the worst one) ...
7
votes
2answers
60 views

Sum of cells on infinite board is even

Let $a,b,c$ be pairwise relatively prime positive integers. In an infinite checker board (infinite in all directions), each cell contains an integer. The sum of the integers in any $a\times a$ square ...
0
votes
1answer
42 views

How do you load $n$ cannisters into $m$ trucks such that no truck is overloaded

We have $n$ cannisters, and for each one there is a specified subset of trucks which can carry it. There are $m$ trucks that can each hold $k$ cannisters. Is there a way to load all $n$ cannisters ...
1
vote
1answer
24 views

Number of ways to place chess figures on one line of chess board [duplicate]

How many ways to place chess figures of one color (2 rooks, 2 knights, 2 bishops, 1 king and 1 queen) on one line of chess board such that 2 bishops are located on the cells with different color and ...
2
votes
4answers
38 views

Consider the number of $3$ distinct numbers formed with the digits $2,3,5,8,9$. How many of them are even?

I'm trying to answer the following: Consider the number of $3$ distinct numbers formed with the digits $2,3,5,8,9$. How many of them are even? I first tried to make the following counting: First ...
4
votes
3answers
90 views

Using up letters on a refrigerator is NP-complete

You spend some time with your preschool-age daughter trying to use up all of the magnet letters on the refrigerator to spell words that she knows. Formally, you have a set of letters and you are ...