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
1answer
58 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
87 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
26 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
58 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
69 views
0
votes
1answer
43 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
64 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
64 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
72 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
156 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
70 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
69 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 ...
2
votes
1answer
57 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
27 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
37 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
31 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
38 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 ...
1
vote
3answers
55 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
40 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
66 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
66 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
51 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
24 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 ...
2
votes
2answers
103 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
48 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
21 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
82 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
49 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
19 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
49 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 ...
2
votes
1answer
78 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
32 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 ...
3
votes
1answer
79 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 ...
1
vote
1answer
174 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
29 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
90 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
132 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
42 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
73 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
105 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: ...
1
vote
2answers
196 views

to find total number of subsets

I was working out some problem where I needed permutation and combination. I took the cartesian product of $n$ sets where number of elements in each set is even. Further the elements of this cartesian ...
3
votes
2answers
83 views

Pulling balls from a box

This is a homework problem I just need checked before I hand it over. It seems deceptively easy so I'm not sure if I'm missing something. In a box there are $10$ balls, each coloured differently. In ...
2
votes
1answer
66 views

Find a recurrence relation for $h_n$. Let $h_n$ denote the number of spanning trees in the fan graph shown below.

Let $h_n$ denote the number of spanning trees in the fan graph shown below. Find a recurrence relation for $h_n$. I know it's got something to do with $h_n=F_{2n-1}$. But how else to find a ...
0
votes
1answer
68 views

How many possible sums of the digits of an n-digit number?

Suppose I have a seven-digit positive number (allowing leading zeroes): How might I go about finding the total number of possible sums of those seven digits? My first instinct was to say it's simply ...
-1
votes
1answer
61 views

Deleting maximal independent sets in graph

Consider an undirected graph $G=(V,E)$. The maximum degree of any vertex is $10$. A set $E'\subseteq E$ is called "maximal independent" if no two edges in $E'$ share a vertex, but adding any more edge ...
3
votes
1answer
69 views

How many bandits must agree?

Problem A group of $n~(1 \leq n \leq 30)$ bandits hid their stolen treasure in a room. The treasure needs to be locked away. The bandits want to ensure that at least $k~(1 \leq k \leq n)$ of the ...
1
vote
1answer
158 views

Generator matrix of a binary cyclic code

I need to find the Generator and Parity check matrix of a binary cyclic [9,2] code. If I calculated right, the Generator polynomial is x^7 + x^6 + x^4 + x^3 + x + 1 and the check polynomial is x^2 - x ...
2
votes
1answer
56 views

Using Stirling's formula to uniformly bound Bernoulli success probabilities

In this paper, the authors say that for any $\gamma \in [1/2,1)$, there is a positive constant $B=B(\gamma)$ such that for any $n$, $$ \sum_{n\gamma\leq k \leq n} \binom{n}{k} \leq B n^{-1/2}2^{n ...
1
vote
0answers
39 views

Determine the formula for hexagon arrangements.

The puzzle to be solved is similar to a jigsaw but using n regular hexagons of equal size for pieces. The pieces are to be placed within a defined perimeter to create a picture. Q: If we let the ...