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)

2
votes
1answer
245 views

Positivity of the alternating sum associated to at most five subspaces

Let $V_1 , V_2 , \dots , V_n $ be proper subspaces of $ \mathbb{C}^m$ and let $$\alpha = \sum_{r=1}^n (-1)^{r+1} \sum_{ \ i_1 < i_2 < \cdots < i_r } dim(V_{i_1} \cap \cdots \cap V_{i_r})$$ ...
1
vote
4answers
54 views

Given that $6$ men and $6$ women are divided into pairs, what is the probability that none of the women will sit with a man?

I've generalized the question I was given here for simplicity: $6$ men and $6$ women are to be paired for a bus trip. If the pairings are done randomly, what's the probability that no women will end ...
0
votes
2answers
56 views

Combination - Distribution of gifts.

Seven different type of gifts are to be distributed among $10$ children. Every kind of gift must be at least given to one child. Then, how many combinations do we have? Note:You have $A, A, A....$ ...
4
votes
3answers
211 views

How many solutions for equation with simple restrictions

I'm working on an assignment in which I have to count the number of solutions for this particular equation: $$x_1+x_2+x_3+x_4=20$$for non negative integers with $x_1<8 $ and $x_2<6$ I'm aware ...
-2
votes
0answers
15 views

Confusing Conditional Probability question 68 [on hold]

The four top tennis players in the world A, B, C, and D are invited to a special tournament where the winner gets one million dollars. In round one, Player A plays player D and player B plays player ...
2
votes
4answers
52 views

Prove the formula $\sum_{k=1}^n k\binom{n}{k} = n \cdot 2^{n-1}$ for all integers $n > 0$ [duplicate]

I just got to this question and I became a question mark. I wonder if anyone can help me with this one, because I don't even know how to begin to tackle this problem. The question: Prove the ...
3
votes
2answers
69 views
+50

Find number of ways to seat $n$ boys and $n$ girls in a row so that every boy has atleast one girl sitting beside him.

My attempt: I am getting $2^n(n!)^2$ . First I paired $n$ boys and $n$ girls in $n!$ ways then these pairs can be arranged in $n!$ ways and in each of these pairs boy and girl can arrange themselves ...
2
votes
1answer
296 views

Faces of the Permutahedron

We define the Permutahedron as the convex hull of all permutations of the vector $(1,2,\dots,n)\in\mathbb R^n$. I am having trouble seeing why the number of $n-k$ dimensional faces of this polytope is ...
-1
votes
5answers
68 views

Deck of Cards Stats Probability Question [on hold]

Randomly select two cards in sequence from a full deck of 52 cards, what i s the probability that the first one is a King given that the second one is a King. If someone can please help me with this ...
2
votes
1answer
46 views

In how many ways can $8$ appointments be scheduled for a physician visiting a nursing home with $20$ patients? [on hold]

A physician routinely visits a local nursing home on Thursday mornings to examine patients. Suppose the facility has $20$ residents, but the physician only has time to check $8$. The supervisor places ...
3
votes
1answer
24 views

Probability: Finding the Number of Pears Given Two Scenarios

You have a bag containing 20 apples, 10 oranges, and an unknown number of pears. If the probability that you select 2 apples and 2 oranges is equal to the probability that you select 1 apple, 1 ...
3
votes
1answer
54 views

Number of 'walks' which stay above 0.

Consider a set of distinct $n$ numbers where $a_i \in \mathbb{R} $ and $$\sum_{i=1}^{n} a_i = 0$$ A walk is defined to be the sum of the numbers, so that the $k$th position is the partial sum to $k$. ...
0
votes
0answers
3 views

Counting subgraphs of bounded extremal degrees

Let $m\leq n-1$. Is there a closed expression counting the subgraphs of minimum degree $\geq m$ (resp. maximum degree $\geq m$) on $n$ labelled vertices?
2
votes
1answer
19 views

How do you calculate the width of the Poset Lattice of Divisors?

Let $n = 10800 = 2^43^35^2$ I can find a set of eleven divisors of $n$ such that none divides another: $$\begin{array}{ccccc} & & & 2 3^3 & 3^35\\ & & 2^23^2 & ...
0
votes
1answer
40 views

Finding a closed formula for: $1\cdot2\cdot3+2\cdot3\cdot4+…+(n-2)\cdot(n-1)\cdot(n)$ [duplicate]

As I calculated the sum of the serie above doesn't exist(sum doesn't converge). How can I prove it using the double computing(combinatorical method)?
1
vote
1answer
26 views

How many ways to divide $n$ different pieces of chocolate in two non empty groups?

After the example I think that the order of the groups doesn't matter so ${(A),(B,C)}$ and $(B,C),(A)$ counted as $1$. Suppose we split $5$ chocolates into a group of size $1$ and a group of size of ...
1
vote
0answers
38 views

Combinatorial interpretation of Euclid's form for even perfect numbers

Euclid showed that if $p$ is a prime such that $2^{p}-1$ is also a prime, then the number $n=2^{p-1}.(2^{p}-1)$ is perfect. Much later, Euler proved that every even perfect number is of this form. ...
0
votes
1answer
16 views

Summation of all j-combinations (Expanding composition formula)

I found a formula for a problem that I was trying to solve, the Formula 3.2 in Section 3 at page 441 of this document.I am a little unsure about the "Summation over all j-combinations". Here is what I ...
1
vote
1answer
689 views

How many $3$ digit even numbers can be formed by using digits $1,2,3,4,5,6,7$, if no digits are repeated?

How many $3$ digit even numbers can be formed by using digits $1,2,3,4,5,6,7$, if no digits are repeated? ATTEMPT There are three places to be filled in _ _ _ I wrote it like this _ _ $2$ _ _ $4$ ...
2
votes
0answers
25 views

Distribution of distinct object problem

So i was given this question. How many ways are there to place 10 distinct people within 3 distinct rooms with exactly 5 people in the first room and 2 people in the second room? So i asked this ...
1
vote
2answers
916 views

How many words can be formed, each of $2$ vowels and $3$ consonants from letters of the word “DAUGHTER”.

How many words can be formed, each of $2$ vowels and $3$ consonants from letters of the word "DAUGHTER" What my textbook has done: it has first taken combinations of vowels and then consonants then ...
2
votes
0answers
24 views

Generating subsets with 1 common element

I have a number $n$ and a set $S$ of $n(n-1)/2$ elements : $ \{1, 2, \ldots, n(n-1)/2\}$ I'm looking for an algorithm to generate $n$ distinct subsets of $S$, each having $n-1$ elements, with the ...
0
votes
1answer
20 views

Expanding Restricted Compositions formula

I recently started to look into restricted compositions and I found a formula for a problem that I was trying to solve, the Formula E at page 441 of this document. In my case I have n =8, k=3, t=1 ...
1
vote
2answers
71 views

How many different 8-letter words can be made with three $a$s, two $b$s, two $c$s and a $d$?

How many words, without making any reference to their meaning can be written from the letters: $ a,a,a,b,b,c,c,d$ ? what is the best approach to solve this kind of problem ?
1
vote
2answers
154 views

Counting outcomes of a coin flipping sequence

So I have this question regarding counting the possible outcomes of a coin flipping sequence. Here it is: A coin is flipped 12 times where each flip comes up either as heads or tails. How many ...
1
vote
2answers
79 views

Find the recursive definition for the number of strings on 0, 1, 2 avoiding the substring 012?

This is the question $a(n)$ the number of strings on $0, 1, 2$ avoiding the substring $012$ and the answer is $$a(n)=3a(n−1)−a(n−3)$$ with $$a(0)=1,a(1)=3,a(2)=9$$ My question is how to you get this ...
-2
votes
0answers
33 views

Different Ids on mars [on hold]

I am doing some exam questions - and I don't know the answer, can u show How to calculate it and what the answer is? The question: On Mars, each Martian alien, has an ID card with a unique ...
3
votes
1answer
66 views

How many ambiguous dates exist?

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

Number of words of length $n$ on the alphabet $a,b,c$ recurrence. [on hold]

Let $a_{n}$ be the number of words of length $n$ on the alphabet $a,b,c$ such that $b,c$ are not adjacent. What is the recurrence relation for $a_{n}$.
12
votes
4answers
900 views

Volume of 1/2 using hull of finite point set with diameter 1

It's easy to bound a volume of a half. For example, the points $(0,0,0),(0,0,1),(0,1,0),(3,0,0)$ can do it. The problem is harder if no two points can be further than 1 apart. Bound a volume of 1/2 ...
5
votes
2answers
30 views

solve for variable in combination

i have the combination ${n\choose 11}=12376$ and am looking to solve for $n$. it turns out to be $17$. of course can use brute force approach where just plug numbers in for $n$ but am looking for a ...
2
votes
0answers
60 views

Counting integers from $1$ to $n$ with an odd number of divisors in {1,2,3,…,k}

Question Given $n,k$ find the number of integers between $1$ and $n$ that have odd number of divisors in {1,2,3,...,k} Example If $n=10$ and $k=3$, the numbers $1(1),5(1),6(1,2,3),7(1)$ have odd ...
0
votes
2answers
44 views

How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear?

So i was given this question. How many 10-digit decimal sequences (using 0, 1, 2, . . . , 9) are there in which digits 3, 4, 5, 6 all appear? My solution below (not sure if correct) Let $A_i$ = set ...
1
vote
1answer
29 views

Give a recursion for the number h(n) of strings in S of length n.

Let S be the set of strings on the alphabet {0,1,2,3} that do not contain 12 or 20 as a substring. Solving this I got: $$ h(n) = 4h(n-1) - 2h(n-2)$$ with $h(0) = 1, h(1) = 4,h(2) = 14 $. When I did ...
0
votes
3answers
73 views

List all the permutations for the letters $a,c,t$

I know a permutation is $p(n,r)=\dfrac{n!}{(n-r)!}$ but I am confused how to go about solving this problem. Help please?
0
votes
3answers
42 views

Combinatorics president and votes

There are 5 candidates for presidency and 11 people that can vote at most one of them (so they can decide not to vote). How many combinations of votes are there if no candidate can recieve more than 5 ...
1
vote
2answers
33 views

Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3

Find the Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3. (Numbers are selected without replacement). I made a list like this: The sum of ...
-1
votes
2answers
36 views
1
vote
1answer
47 views

How many ways are there to place 10 distinct people within 3 distinct rooms with exactly 5 people in the first room and 2 people in the second room?

So I was given this question. How many ways are there to place $10$ distinct people within $3$ distinct rooms with exactly $5$ people in the first room and $2$ people in the second room? I have ...
5
votes
2answers
82 views

Minimum elements present in {0, 1, 2, …, 225} to guarantee triple which sums to 225

Suppose I have the set: $$A=\{0, 1, 2, ... 224, 225\}$$ I want to find a triple that sums to $225$ (where a triple is a set of 3 unique values from the set). No Repetition Version: There are many ...
0
votes
0answers
24 views

Looking for mathematical/combinatorial and computational explanation regarding adding values in a $5 \times 4$ (matrix?) with a constraint.

Given the following matrix (not sure if I should call it that): Matrix $5 \times 4$ I want to add all possible combinations of values such that each Horse gets but one value from each Bookie. What I ...
0
votes
1answer
27 views
+50

Finding the data regarding the four racket games.

In a vijantkhand sports stadium, athletes choose from $4$ different racket games (apart from athletes which is compulsory for all) These are tennis, table tennis, squash and badminton. It is ...
1
vote
0answers
21 views

Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
1
vote
3answers
62 views

How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ with restrictions

So i was Given this question. How many different integer solutions are there to the equation $x_1 + x_2 + x_3 + x_4 = 21$ $0 \leq x_i \leq 9$? I just assumed it would be ${21+4-4-1 \choose ...
2
votes
2answers
20 views

Why use C(n,r) instead of P(n,r) when considering how many strings can be formed in which a specific letter appears before another specific letter?

I am dealing with a problem in which I must determine how many strings can be formed by ordering the letters ABCDE subject to the conditions given. The condition that I am given is that A appears ...
2
votes
3answers
54 views

Abstract Combinatorics

In a library there is a sequence of $n$ books. There is someone that never wants to take books that are neighborhoods of each other. How many possibilities are there, for him, to take $k\le n$ books? ...
4
votes
6answers
171 views

Proving that $\binom{n}{k}\binom{\smash{k}}{m}\binom{m}{r} = \binom{n}{r}\binom{n-r}{n-m}\binom{n-m}{n-k}$

How would you show that $$\binom{n}{k}\binom{k}{m}\binom{m}{r} = \binom{n}{r}\binom{n-r}{n-m}\binom{n-m}{k-m}$$ for $n\geq k\geq m\geq r$ ?
1
vote
0answers
48 views

Is it always possible to get MC/DC coverage on an $n$-input Boolean function with $n + 1$ test cases?

In software engineering, there is a coverage metric for testing called modified condition/decision coverage, or MC/DC for short. This metric is well-known in the avionics industry due to showing up in ...
3
votes
0answers
23 views

Extremal set theory problem concerning translations of a set of integers

Let $A$ be a subset of $B = \{1, 2,\ldots,n\}$. Suppose that $F$ is a family of subsets of $B$, each of which is a translation of $A$ and no two of which intersect more than once. What is the maximum ...
0
votes
1answer
59 views

The probability of the sum of $10$ dice rolls adding up to $57$

So the question is: given that you roll $10$ dice, what is the probability of the sum of the total dice rolls adding up to $57$? I know that there are three ways to do this: Seven die rolls must ...