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

In how many ways can we pick a group of 3 different numbers from the group $1, 2, 3, …, 500$ such that one number is the average of the other two?

Here's the question which I'm struggling with - In how many ways can we pick a group of 3 different numbers from the group $1, 2, 3, ..., 500$ such that one number is the average of the ...
0
votes
0answers
13 views

Squares Containing digits from Fibonacci Numbers

This is a problem that I thought of myself. Currently, the digits of $F_1$ through $F_n$ are written on the chalkboard in order, where ${F_n}$ is the Fibonacci Sequence and $n \ge 5$ We shall ...
4
votes
2answers
24 views

Pair of friends and a pair of “enemies” in each group of three students

The problem: There is a class. In each group of three students in the class there is a pair of friends and a pair of "enemies". Find the maximum number of students in the class. I tried to play with ...
0
votes
1answer
27 views

How many non-congruent triangles with perimeter 11 have integer side lengths? [on hold]

How many non-congruent triangles with perimeter 11 have integer side lengths? I failed to solve it. Can anyone help?
1
vote
2answers
24 views

Combinatorics: Does this method take into account every possible matchup

It's actually a question on finding the probability, but I am stuck on a different part of this question. There are $2^n$ players playing a tennis tournament. I have to find the total number of ways ...
0
votes
1answer
22 views

number of ways of arranging balls so that there are exactly two pairs of green balls

There are $5$ identical red balls and $6$ identical green balls. In how manys we can arrange them so that there are exactly two pairs of green balls. Let red balls be $R,R,R,R,R$ and green be ...
1
vote
0answers
37 views

How many ways to pick four increasing numbers from 1 through 39?

Say there's a bin of balls numbered 1 through 39, how many ways are there to pick 4 increasing numbers in a row? First I figured that it would be a permutation without repetition problem, so I got ...
2
votes
2answers
34 views

constrained stars and bars problem

I want to know number of solutions for following equation, where $r_k$'s are non-negative integers, and there is a constraint on $r_k$'s such that $r_1 \geq r_2 \geq \cdots \geq r_K$ \begin{equation} ...
0
votes
0answers
14 views

Small graphs containing all trees on $n$ vertices

What do those graphs look like which contain a copy of every tree on $n$ vertices and such that no proper subgraph has this property?
4
votes
2answers
106 views

What am I counting wrong?

EDIT: I made a mistake in the beginning, the second condition has changed. Sorry for this. I'm asked to count the number of sets of 4 elements that satisfy the two following conditions: 1) Each ...
-1
votes
0answers
26 views

Number of solutions of equation with natural numbers [on hold]

Given natural numbers $s, n, k$. How to find number of solutions to equation $a_1 + a_2 + \ldots + a_s = n-s$ where $0 \leq a_i \leq k-1$ and $a_i \in \mathbb{N}$?
0
votes
0answers
32 views

all but one sub-strings within a cyclic string

over $GF(q)$ where $q\in\mathbb{N}$, we build a string of size $q^n-1$. now, how can I show that it is impossible to construct that string so it contains all sub-strings of size $n$ exactly once, but ...
-1
votes
0answers
16 views

Onto functions from a set with 4 elements to a set with 3 elements [duplicate]

How many onto functions are there from a set with four elements to a set with three elements? If the four elements set is A = {a, b, c, d} and the three elements set is B = {u, v, x} I see these ...
1
vote
0answers
20 views

What is the probaility that two random permutations have same order?

I am interested in the orders of random permutations. Since the law of the log of the order of a permutation converges to a normal law (for instance Erdös-Turan Statistical group theory III), one ...
0
votes
2answers
26 views

equation to create unique value

I have a list of n objects say [ apple, orange, carrot, cherry, banana ] Now I am trying to come up with an equation which will generate an unique number for ...
3
votes
1answer
52 views

Product of sums into a sum of products

Any idea on how I can get an expression in the form of sum of products from the following one?: \begin{equation} \prod_{i=1}^M \left(\sum_{n=1}^i x_n\right) \end{equation}
1
vote
1answer
32 views

The probability of being dealt at least 5 wanted cards

In a fictional deck of cards, there are 30 cards, 15 different ones (each card has an identical pair, so 15 pairs = 30 cards). I want to answer the question: I am dealt 10 cards. I wish to receive 5 ...
5
votes
1answer
83 views

How to solve this hard sum problem?

$$\sum _{ x=1 }^{ \infty }{ \frac { 3{ x }^{ 2 }+12x+16 }{ { \left( x\left( x+1 \right) \left( x+2 \right) \left( x+3 \right) \left( x+4 \right) \right) }^{ 3 } } } =\frac { 1 }{ 4{ (a!) }^{ b } } ...
7
votes
2answers
95 views

Number of ways to partition $40$ balls with $4$ colors into $4$ baskets

Suppose there are $40$ balls with $10$ red, $10$ blue, $10$ green, and $10$ yellow. All balls with the same color are deemed identical. Now all balls are supposed to be put into $4$ identical baskets, ...
6
votes
2answers
85 views

Given the set $A=\{1,2,\dotsc,14\}$, find all subsets of $7$ elements that sum to a multiple of $7$.

I would appreciate if somebody could help me with the following problem. Given the set $A=\{1,2,\dotsc,14\}$, calculate the number of distinct sets $M \subset A$ such that $|M| = 7$ and such that ...
3
votes
2answers
58 views

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 ...
-1
votes
1answer
42 views

Why the Sum of all possible outcomes does not equal to one, in this case?

The question is an extension from an example (click this--> Introduction to Probability and Its Applications by Richard Scheaffer, Linda Young. The link points to the exact question/solution. Edit:- ...
1
vote
2answers
34 views

Binary Strings: How to determine if decomposition is ambiguous

Let's say I have the following decomposition: $$\{100,10011,00110\}^*$$ How would I determine if the decomposition is ambiguous or unambiguous?
0
votes
1answer
32 views

More intuitive way for solving this problem than using the multinomial theorem?

I'm the TA in a discrete math course and there was a problem in this weeks problem set which I had troubles solving. It goes like this: Find the coefficients of $v^2w^4xz$ in the expansion of $(3v + ...
0
votes
0answers
27 views

Using a combinatorical proof for recursion

I am having trouble understanding a combinatorial proof. I have a recursion, $$ a(n) = 2*a(n-1) - a(n-2) $$ And the combinatorial explanation (i.e., proof-light) is that $a(n)$ is just the count ...
1
vote
1answer
22 views

Need combinatorial formula

Let we have a forest $F_n(P)$ with $n$ nodes defined by set $P$ of all pairs $\{\text{father}, \text{son}\}$. For instance $P=\{\{1, 2\}, \{3, 4 \}, \{1, 3 \}\}$ defines a forest $F_5(P).$ Let ...
0
votes
1answer
23 views

Probability of drawing $m$ of $A$ in $n$ cards given a deck of $d$ cards contain $a$ copies of $A$?

As in the title I'm trying to work out what the chances of drawing $m$ copies of a specific card in $n$ draws are given a deck size of $d$ containing $a$ copies of $A$. I've tried using permutations ...
2
votes
2answers
33 views

Counting permutations with given condition

I need to find number of permutations $p$ of set $\lbrace 1,2,3, \ldots, n \rbrace$ such for all $i$ $p_{i+1} \neq p_i + 1$. I think that inclusion-exclusion principle would be useful. Let $A_k$ be ...
0
votes
1answer
34 views

In how many different ways can the gifts be given? [on hold]

For Valentine's Day $5$ children receive a total of $6$ different gifts. Each child receives at least one gift and each gift is given to exactly one child. In how many different ways can the gifts ...
1
vote
1answer
29 views

Show impossibility of a perfect covering

Problem: Show that a $8 \times 8$ chessboard cannot be perfectly covered by $1$ square tetramino, and 15 other tetraminoes chosen from straight tetraminoes and Z-tetraminoes. My attempt: I tried to ...
3
votes
1answer
21 views

How many teams can be formed?

I would like to calculate the number of choices of teams I can make in the following scenario. Suppose a team is comprised of 3 characters (1 leader and 2 support members) and suppose there are 108 ...
5
votes
3answers
38 views

Combinatorial argument for $\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$

I need to show that $$\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$$ I know that $\displaystyle \binom{n}{k}\binom{k}{i}$ is counting the number of ways to pick $k$ elements ...
2
votes
1answer
35 views

Probability of an array having all distinct numbers

Suppose you have an array of size $2n$. There are two times $2n^2$ distinct numbers that can be put into the array without replacement, i.e. for each choice of number, there are two copies, so a ...
1
vote
1answer
18 views

Number of permutations of $S_n$ such that $\sigma^h(a) = \sigma^k(b)$

A basic result in combinatorics is: In $S_n$ there are $(n-d)(n-2)!$ permutations $\sigma$ such that $\sigma^k(a) = b$, if $a \neq b$; $d(n-1)!$ permutations $\sigma$ such that ...
1
vote
1answer
20 views

How many options are there to award gold, silver, and bronze medals to a group of $10$ athletes?

How many options are there to award gold, silver, and bronze medals to a group of $10$ athletes? Is this permutation or combination, and is there repetition? I thought this would be a combination ...
1
vote
0answers
41 views

Estimates for the Dedekind number $M(9)$

The Dedekind number $M(n)$ is the number of antichains in the partial order of subsets of $\{1,\dotsc,n\}$. It is only known for $0 \leq n \leq 8$. Question. What are some known upper and lower ...
5
votes
1answer
44 views

Number of $n$-digit permutations with exactly $n-2$ digits smaller than the next

How many permutations of $1,2,\cdots, n$ contain exactly $n-2$ digits that are smaller than the digit immediately to their right? My solution proceeded with recursion. It has some chance of being ...
1
vote
0answers
26 views

Possible closed form or approximation?

Does it have some closed form or approximation ? I tried on my own but i am not getting any idea regarding this. $$\sum_{k_1=k}^{M}\sum_{k_2=k}^{M}\frac{k_1^{-\gamma} k_2^{-\gamma} ...
-1
votes
1answer
38 views

The number of ways to divide 10 people into groups of given size [on hold]

Find the number of ways in which $10$ people can be divided into $2$ groups consisting of $7$ and $3$ people Three groups consisting of $4$, $3$ and $2$ people with $1$ person rejected. $5$ groups ...
3
votes
1answer
41 views
+50

Find the maximum number of people who participated in exactly three games?

Gauri Apartment housing society organised annual games, consisting of three games: snooker, badminton and tennis. In all, $510$ people were members in the apartments' society and they were ...
2
votes
2answers
41 views

In how many ways can a committee of $6$ people be selected from $7$ men and $6$ women if it can contain at most one of persons A and B?

A committee of $6$ people will be formed with $7$ men and $6$ women. The oldest of the $7$ men is A and the oldest of the $6$ women is B. It is described that the committee can include at most one of ...
2
votes
2answers
46 views

Solving the recurrence $A_n = \sum_{k=1}^{n} 2^{k+1} A_{n-k}$

Let me ask a very simple question: Let $(A_n)$ be a sequence of integers defined by $A_0 = 1$ and $$\forall n \geq 1 : A_n = \sum_{k=1}^{n} 2^{k+1} \cdot A_{n-k}.$$ There is an explicit formula for ...
0
votes
0answers
19 views

Use probabilistic method to show existence of a particular subset

Suppose that a $2m \times 2m, m \geq 4$ table is populated with numbers $1, 2..., 2m^2$ (i.e. each number appear exactly twice). Show that there exists a selection of $2m$ cells such that the ...
0
votes
1answer
32 views

Counting the frequency of a flush hand in $7$-card poker

I'm trying to count the frequency of a flush hand in $7$-card poker. Since a flush hand could be thought of as having $5$ cards with the same suit while the other $2$ doesn't matter, I wrote down as ...
0
votes
0answers
60 views

Order-Preserving Bijection $f:A\to A^*$?

Let $A$ be a well-quasi-ordered infnite set. Does there exist an order-preserving bijection $f:A\to A^*$, where $A^*$ is the free monoid over $A$ under the subword ordering? Would this subword ...
0
votes
2answers
22 views

Probability; bridge hand question

$13$ cards are chosen at random with no replacement from a deck of $52$ cards. find the probability there are $5$ spades chosen, $4$ hearts, $3$ diamonds and $1$ club. I got ...
1
vote
1answer
12 views

Splitting $N$ Groups of Objects into $M$ bins

For simplicity, I'll give the example as splitting 3 bins of balls into 4 bins. Bin 1 contains $N_1$ blue balls, bin 2 $N_2$ red balls, and bin 3 $N_3$ green balls How many combinations of ways ...
3
votes
1answer
30 views

Combinatorics: How do you find the coefficient in the given expression?

The question asks me to find the coefficient of the term $x^6y^4$ in the expression $(xy^2+x^2+3y)^7$. This was pretty simple. This is how I did it: $$(xy^2+x^2+3y)^7 = \sum_{a+b+c = n} (xy^2)^a + ...
0
votes
1answer
12 views

Show that if a bipartite graph $G = (V, E)$ with bipartition $V = A \cup B$ is $k$-regular, then $|A| = |B|$.

A graph is $k$-regular if every vertex has degree $k$. Show that if a bipartite graph $G = (V, E)$ with bipartition $V = A \cup B$ is k-regular, then $|A| = |B|$. I dont understand it. Please explain ...
0
votes
3answers
27 views

How many different varieties of pizza can be made if you have the following choices:

How many different varieties of pizza can be made if you have the following choice: small medium, large; thin, hand tossed, pan; and $12$ toppings (cheese is an automatic), from which you may select ...