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 (4)

1
vote
0answers
23 views

a problem with computing binomial coefficients

I have a problem with computing the binomial coefficient in polynomial algebra. Let we have $a=(a_1,...,a_n)$ and $b=(b_1,...,b_n)$ as an n-tuples such that $ (0,...0) \leq a ,b \leq ...
1
vote
0answers
38 views

Abiguous dates such as $8/3/2007$

How many ambiguous dates are there in a year? An ambiguous date is one like $8/3/2007 $ which could either mean the $8$th of March or the $3$rd of August. Is it right to say that $1/1/2007$ must mean ...
1
vote
2answers
29 views

seat arrangement possibilities

What could be possible arrangements for the below? A, B, C, D and E are sitting on a bench. A is sitting next to B, C is sitting next to D, D is not sitting with E who is on the left end of ...
0
votes
0answers
15 views

Calculating ONeill prices in combinatorial auctions using the dual (Linear programming)

I am trying to calculate the O’Neill prices[1] for the individual atoms in a combinatorial auction. The method is: Solve the IP to find the optimal allocation for the auction. Remove the integer ...
1
vote
2answers
30 views

Simple Combinatorial Proof [duplicate]

$$ \sum_{i=0}^n {n \choose i} i = n2^{n-1} $$ I am having trouble formulating a combinatorial proof. An algebraic proof is quite simple, where one expands $(1 + x)^{n}$ and then takes the ...
0
votes
1answer
15 views

Possible combinations for this example

I'm currently writing about databases and superkeys and I need a little help with the following issue. For one element: Elements: A Combinations: A For two ...
0
votes
0answers
40 views

Expected number of days on which at least two of 50 people were born

Question A group of 50 people are comparing their birthdays. Find the expected number of days in the year on which at least two of these people were born. Answer $$ ...
0
votes
1answer
48 views

Subset sums and conditions

For a given $n$-element set $N$, how can I find all $r$-element subsets of $N$ such that sum of all elements of $r$ is: $(i)$ less than $a$ $(ii)$ greater than $a$ $(iii)$ equal to $a$ ? Further ...
1
vote
1answer
40 views

how to generate rook polynomial

I've encountered rook polynomials. I just can't seem to understand how to generate them by hand for small examples such as 3x3 boards. Take for instance: $$\begin{matrix} 1 & 1 & 0 \\ 1 ...
1
vote
1answer
23 views

Question about a method in elementary combinatorics.

I'm reading Martin's: Counting: The Art of Enumerative Combinatorics. How many ways are there to arrange the letters in NASHVILLETENNESSEE with the first N precending the first S and with the ...
0
votes
2answers
53 views

Combinatorics - Am I doing this properly?

I'm working on an assignment and I'm not sure if I'm doing it properly so I figured I'd ask and make sure. The question is, a university gives each student a 6 digit code for a student number. a) ...
0
votes
2answers
60 views
0
votes
1answer
41 views

Combinatorics, marks to students

please am I right in my solutions for these problems ? There was a test in a school, but teacher lost all the completed tests. He has to give some points to studens. a)How many possibilities are ...
1
vote
0answers
17 views

Permutations with repeated elements [duplicate]

Say you have n digits and you want to see how many different numbers you can form with these digits (i.e. all possible numbers, not only the ones that are n digits long). These digits however aren't ...
1
vote
3answers
61 views

Amount of binary strings

i `ve got this problem, can you help me ? I can solve subquestion a) but i really don`t have a clue how to find recursive formula. S_n is the amount of binary strings with size n, which don’t ...
0
votes
1answer
23 views

Calculating the probability of a combination with repetition

If I have n colors, (Let's say n=3 , blue=0, red=1 and green=2). And we have r boxes (Let's say r=5). So we have these combinations (with repetition). ...
0
votes
1answer
48 views

Digit sum of natural numbers in interval

can you help me with this problem ? How many natural numbers $n$, $1 ≤ n ≤ 10^4$, with digit sum $= 7$, can you find ?
3
votes
2answers
121 views

Calculating the number of combinations we can put people in a queue with some restrictions

Suppose we have $n$ number of persons, all with different heights. We need to stack them such that only $x$ are seen from the front and $y$ are seen from the back. Smaller people are hidden behind ...
1
vote
0answers
38 views

Compute transition probability in n step in infinte markov chain

I want to calculate the probability of transition in n step from state 0 to state 0 ($p_{00}^{(n)}$) in below Markov-Chain : if self loop in state 0 doesn't exist, probability computed with Catalan ...
2
votes
2answers
53 views

How many ways can 25 red balls be put into 3 distinguishble boxes if no box is to contain more than 15 balls?

I'm reading Martin's: Counting: The Art of Enumerative Combinatorics. How many ways can 25 red balls be put into 3 distinguishble boxes if no box is to contain more than 15 balls? I understand ...
1
vote
1answer
51 views

Showing that a graph is NOT planar

Each edge of the complete graph with 11 vertices is colored either red or blue. We then look at the graph consisting of all red edges and the graph consisting of all blue edges. How do I show that at ...
1
vote
0answers
26 views

n-variable analogue of Chu-Vandermond identity

Is there an n-variable generalization of the well known Chu-Vandermond identity, such as $$ {{a_1+\cdots +a_m}\choose{k_1+\cdots + k_m}}=\sum_{k_1+\cdots+k_m=n} {a_1 \choose k_1}\cdots {a_m \choose ...
0
votes
1answer
18 views

the number of ways of shading a grid

In how many ways can we shade exactly two squares of the nine squares on a $3\times 3$ grid such that the two shaded squares have no side in common?
0
votes
1answer
24 views

Planar graph with V ≥ 2 has at least 2 vertices whose degrees are at most 5

If G was a planar graph on V ≥ 2 vertices. How would I go about proving that G has at least 2 vertices whose degrees are at most 5? I understand that planar graphs can be drawn so that every edge is ...
1
vote
2answers
31 views

Manipulation of combinations

Let $k,n\in\Bbb N_0$, with $k\le n$. Prove that $$\binom{n+1}{k+1}=\sum_{j=0}^{n-k}\binom{n-j}k\;.$$ Just was hoping someone could give me a hint or two with this problem. I think it has to ...
-4
votes
1answer
55 views

How many integers from $1$ to $1000$ are divisible by none of $3 , 5$ and $7$ [closed]

answer me please How many integers from $1$ to $1000$ are divisible by none of $3 , 5$ and $7$
1
vote
3answers
52 views

Number of Triples Between $1$ and $n$

The exact question is: Let $n$ be a positive integer. Find the number of triples $(a,b,c)$ such that $1\leq a\leq b\leq c\leq n$ .
1
vote
3answers
33 views

The number of (non-equal) forests on the vertex set V = {1, 2, …,n} that contains exactly 2 connected components is given by

The number of (non-equal) forests on the vertex set V = {1, 2, ...,n} that contains exactly 2 connected components is given by $\sum_{k=1}^{n-1} {n-1 \choose k-1} k^{k-2} (n-k)^{n-k-2}$. I am unsure ...
4
votes
2answers
54 views

Number of solutions to equation, range restrictions per variable

Find the number of solutions of the equation $x_1+x_2+x_3+x_4=15$ where variables are constrained as follows: (a) Each $x_i \geq 2.$ (b) $1 \leq x_1 \leq 3$ , $0 \leq x_2$ , $3 \leq x_3 \leq 5$, $2 ...
0
votes
1answer
36 views

permutations with the English alphabet

How many four-letter words, using the English alphabet, are possible if letters if only vowels may be repeated? How many four-letter words are there if at most one repetition of any letter is allowed? ...
0
votes
1answer
32 views

Find the number of trees on the vertex set V = {1, 2, …, 8} in which all vertices have degree 1 or 4.

I am unclear how to figure this out. I understand that if there were 6 vertices of deg = 1 and 2 vertices of deg = 4 then I can simply check if the degrees all add up to 2n-2 and use a specific thm: ...
0
votes
2answers
23 views

A rental car agency has 12 identical cars available and 7 identical vans…

My question is: A rental car agency has 12 identical cars available and 7 identical vans a) If the group needs to rent four cars and two vans, in how many different ways can they select their ...
1
vote
2answers
61 views

How can the sniffer dog find the bag of drugs?

There are $n$ bags. In one of the bags are drugs. There is a dog that when given a group of bags, can tell whether there are drugs in the group or not. Each sniff counts as a "turn". What is the best ...
-1
votes
2answers
44 views

combinatorics problem counting

We are given a word which has 50 symbols and we are given an alphabet with 30 symbols each one diffrent from the others.The number of the diffrent words in which every symbol is at least one? my ...
0
votes
1answer
19 views

Are there two notions of flow?

I'm reading Jungnickel's Graphs, Networks and Algorithms. He defines the flow as a mapping $f:E\to \mathbb{R}_0^+$, which seems to mean the value of the flow of each edge, but in here: When he ...
0
votes
3answers
77 views

clarification on the formula $\frac{n!}{(n-k)!}$

$\dfrac{n!}{(n-k)!}$ is used in order to find non-repetitive lists of length $k$ given $n$ possible symbols. For example: find the number of non-repetitive lists of length five that can be made ...
3
votes
1answer
37 views

Unresetting 4-digit number lock

Let there be an imaginary digital lock that verifies a simple 4-digit passcode (in base 10 numbers, like 4281 or 3349, etc.) BUT unlike other locks, it does not reset after a failed trial. That means ...
0
votes
0answers
11 views

Number of *distinct* dot products of an integer vector by elements of a hyper-rectangle

Imagine a vector $\boldsymbol{v}$ composed of integers, and the set $S$ of all integer vectors within a hyper-rectange, with one corner at the origin and other at $\boldsymbol{m}$. In other words: $S ...
0
votes
2answers
28 views

Principle of inclusion and exclusion

How many integer solutions can we have for the equation $x_1 + x_2 + x_3 = 18$, if $0 \leq x_1 \leq 6$, $4 \leq x_2 \leq 9$ and $7 \leq x_3 \leq 14$? Using the Principle of inclusion and Exclusion: I ...
1
vote
0answers
49 views

Calculate winning outcomes of plurality voting

My problem is similar to this one, but different in some significant ways. As in the above question, I have voting with $n$ voters and $m$ candidates. However, I care about which voter voted for ...
0
votes
1answer
29 views

How many polynomials in $Z_{p}[x]$ have degree n or less?

For your reference, $Z_{p}[x]$ refers to the set of all polynomials with coefficients integer mod p. To me it seems like this and the degree (power) of the two polynomials are unrelated. What ...
2
votes
1answer
53 views

Probability distribution of the sum of 1 to n random integers

I apologize in advance if the title of this question was not clear, I do not know how to formalize this question myself, and therefore I need help. I will try to explain the problem as simple as ...
0
votes
0answers
19 views

List all vectors of the binary [9,2] cyclic code

How do I know how many vectors there will be? I know the length(dimension?) is 7. I also know the generator matrix is: ...
1
vote
1answer
54 views

How many different numbers can you make with the following digits?

How many different numbers can you make with the following eight digits? $1, 2, 2, 3, 3, 3, 0, 0$ The problem I encounter is how to include numbers that aren't 8 digits long? For instance the ...
0
votes
0answers
14 views

Give the idempotent generators of the four binary QR codes C1 , C2 , C3 , C4 , of length 7.

I'm having trouble on some homework. This is the last problem and I can't figure it out. Can anyone help or point me in the right direction? Thanks! For each code Ci , 1 ≤ i ≤ 4, from part (a), give ...
0
votes
1answer
29 views

stars-and-bars problem with an upper limit uppon the number of stars between between 2 bars

Can't be more precise than the title of my question! How many possibilities to put N balls in n bags with the additional constraint that each bag can contain no more than $r_i$ ($r_1$, $r_2$, ... ...
1
vote
2answers
112 views

Compute the following sum $ \sum_{i=0}^{n} \binom{n}{i}(i+1)^{i-1}(n - i + 1) ^ {n - i - 1}$?

I have the sum $$ \sum_{i=0}^{n} \binom{n}{i}\cdot (i+1)^{i-1}\cdot(n - i + 1) ^ {n - i - 1},$$ but I don't know how to compute it. It's not for a homework, it's for a graph theory problem that I try ...
0
votes
1answer
29 views

Combinatorial puzzle concerning labelled equilateral triangles

Consider equilateral triangles $\Delta$ of fixed size and in a fixed position with each side labelled by a label $l \in \{1,\dots,k\}$. Obviously there are $k^3$ such labelled triangles. Let ...
1
vote
1answer
25 views

Compositions with all odd parts

How many compositions of n are there where all parts of the composition are odd? I know how to solve for the number of composition when all are even. However, I'm getting stuck with finding all the ...
1
vote
4answers
75 views

“Story” proof of $\sum_{i=j}^n {i \choose j} = {n+1 \choose j+1}$

I am reading a book "Discrete Mathematics for Computer Scientists". One of the exercises asks for a "story" proof of this: $\sum_{i=j}^n {i \choose j} = {n+1 \choose j+1}$. My question is that: ...