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

Counting arrays problem [closed]

Given N, M and D I need to count how many sequence of N elements a[1],a[2].....a[n] can be formed which satisfy these 2 conditions : Each element is between 1 ≤ Ai ≤ M. Greatest common divisor of ...
4
votes
1answer
82 views

Average time to fill boxes with balls

Let's have n users with each having a ball and m boxes. The users put their ball in a random box. It takes exactly 10 seconds for all balls to be put in a random box (independently to the number of ...
0
votes
1answer
43 views

Prove that a preorder is not anti symmetric

Let $\prec$ be a relation on the set $ A = Z \times (N \setminus \{0\}) $ in this way: A. $<a,b> \prec <c,d> $ if $ ad \le bc$ Prove that $\prec$ is a Preorder and show it's not ...
0
votes
2answers
27 views

A question about different pairs that are formed from a set of 16 different balls such that…

I got the following problem: Given a set of 16 different balls, 8 are white and 8 are black. If we partition the set of balls into pairs of two different balls and let $X$ be a discrete random ...
1
vote
0answers
27 views

Urn problem- distribution after all balls of x randomly selected colours are removed

Apologies for any notational problems or lack of clarity: I'm a linguist not a mathematician. Anyway, here goes: There is an urn with $n$ balls divided into $k$ colours, where the number of each ...
0
votes
1answer
11 views

If I'm counting the number of binary strings of a certain length with a certain number of 1's, should I use combinations or permutations?

And should I use repetition allowed, or repetition not allowed formula? A binary string is a string with 1's and 0's in a row. {0,1} is a different string from {1,0}. Say I'm considering binary ...
0
votes
1answer
15 views

How many different words of length $12$ can I build using $0,1,2$ symbols

I think I know the answer because its about cycle, but I'm wondering where my intuition failed if we have $2^n$ binary words of length $N$ shouldn't we have also $3^n$ words which we can build using ...
0
votes
0answers
24 views

Product of two combination terms

Is it possible to write the product of these two combinations as one combination term $N\choose r$$M\choose r$ where $r<N,M.$ Is it possible to say anything about the kind of distribution it ...
1
vote
1answer
16 views

Calculating how many elements are in the product of Cartesian multiplication

Let $A = \{1,3\}, B = \{1, 2\}, C = \{1, 2,3\}$. How many elements are there in the set $\{(x,y,z) \in A \times B \times C | x + y = z \} $ ? Two things I'm not familiar with here, First, how ...
6
votes
5answers
250 views

Permute “aaaaabbbbbccccc” so that no two identical letters are adjacent

This is a follow up question to Application of PIE. How many strings with the letters "aaaaabbbbbccccc" are there so that no two identical letters are adjacent?
2
votes
2answers
71 views

Application of PIE

Let $A_1, . . . , A_m$ be sets such that $|A_i| = n$ and $A_i \bigcap A_j$ = ∅ for $i \ne j$. Find the number of sequences of elements from $\bigcup A_i$ which have the following properties: (1) Every ...
0
votes
2answers
13 views

Discrete Math Combinatorics Sets and Subsets

Can someone please explain why the following question's answer is (a)? Let S be a set of size 37, and let x and y be two distinct elements of S. How many subsets of S are there that contain x but do ...
0
votes
2answers
30 views

Counting : How many combinations are possible in a sorted set

In a set of n elements, where each element can be any of $ \{0,1,2,3,4,5,6,7,8,9\} $ how many different combinations are possible. Note that all elements are sorted i.e. $\{3,2\}$ is the same as ...
2
votes
1answer
76 views

Minimum number of ways to color each integer

I have seen this problem floating around for a while but with no answer. Since the USAMTS deadline has passed, I would really like to see an answer for this. The farthest I got with this was that $n ...
0
votes
2answers
45 views

Probability that a bitstring of length $25$ will contain atleast two $1$s

We choose a bitstring of length $25$ uniformly at random. What is the probability that this string contains at least two $1$s? (a) $1 − \left(\frac12\right)^{25} − 25\left(\frac12\right)^{25}$ (b) ...
1
vote
1answer
30 views

Discrete Math: Combinatorics and recursion

Let S be a set of size 37, and let x, y, and z be three distinct elements of S. How many subsets of S are there that contain x and y, but do not contain z? (a) $2^{33}$ (b) $2^{34}$ (c) $2^{35}$ ...
0
votes
2answers
21 views

Determine the number of integral solutions of the equation

Let ${x_1 + x_2 + x_3 + x_4}$ = 20 which satisfy: 1 $\leq$ $x_1$ $\leq$ 6, 0 $\leq$ $x_2$ $\leq$ 5, 4 $\leq$ $x_3$ $\leq$ 9, 2 $\leq$ $x_4$ $\leq$ 7. Determine the number of integral solutions. I ...
1
vote
1answer
28 views

Concerning the summation of digits in strings: how many strings have an even such sum?

This is a continuation of a previous question of mine Consider an alphabet of $n+1$ letters: $\{0,...,n \}$. Let $z$ be a number in base $n+1$ such that it has at most $n$ digits (so the ...
1
vote
1answer
31 views

Number of numbers with an even sum of digits in a certain base

This question might be somewhat repetitive of previous questions, but I could not find anything quite like it. Consider an alphabet of $n+1$ letters: $\{0,...,n \}$. Let $z$ be a number in base ...
8
votes
3answers
356 views

Chips do not form rectangle on board

Given is an $n\times n$ board with $n\geq 3$. We place a chip in some cells, so that no four chips form a rectangle with sides parallel to the sides of the board. How many chips can we place, at most? ...
0
votes
1answer
32 views

Applying Bayes Rule to Cards

I was playing poker with a friend last night when a question occured to us. I had a two Jacks and the flop came out: King Queen and 4. So, suddenly my pocket Jacks are not so great, unless another ...
1
vote
1answer
22 views

Asymptotics of a sum of scaled multinomial coefficients

I'm interested in finding the asymptotics of the following (for $p \in [0,1]$) $$\sum_{k=1}^{\lfloor (n-1)/2 \rfloor} \frac{k {n-1 \choose 2k} {2k \choose k}} {4^{k}p^{k}}.$$ The central binomial ...
3
votes
2answers
78 views

Finite sum involving Stirling numbers

I am trying to evaluate the following finite sum: $$ \sum_{h=0}^{m}\binom{m}{h}2^{m-h}S(h,k-r)S(m-h,r),\qquad 0\leq r\leq k\leq m, $$ where $S(n,k)$ is the Stirling number of the second kind. Can ...
3
votes
1answer
42 views

Let there be 9 fixed point on the circumference of a circle.

Let there be 9 fixed points on the circumference of a circle. Each of these points is joined to every one of the remaining 8 points by a straight line and the points are positioned on the ...
0
votes
1answer
16 views

Combinatorics: Sampling with Replacement (Door Key Question)

You have a key ring with N keys, exactly one of which is your house key. You randomly try one key at a time until you get the correct key. However, you mix the keys that you have already tried with ...
2
votes
1answer
26 views

How many ways are there to arrange k out of n elements in a circle with repetition?

If you a set of the n elements, in how many ways $Q(n,k)$ can you take some of them and arrange them on a $k$-gon, when repetition of one element is allowed but rotations of one arrangement are not ...
4
votes
2answers
70 views

Count ways 30 distinct books go to 6 students so each receives at most 7 books

What is a good method to number of ways to distribute $n=30$ distinct books to $m=6$ students so that each student receives at most $r=7$ books? My observation is: If student $S_i$ receives $n_i$ ...
1
vote
2answers
23 views

Number of monotonic set functions from all the subsets of some finite set to 0 or 1

Let $N=\{1,2,\ldots n\}$ be some finite set. Let $f:P(N)\rightarrow\{0,1\}$ be a function such that $A\subset B\rightarrow f(A)\leq f(B)$ I'm trying to find an upper bound to the number of such ...
1
vote
1answer
24 views

Multinomial identity - guidance needed

I need hints on a direction to proove that $$\displaystyle\prod_{k=1}^{n} {{k+1\choose2}\choose k} ={{n+1\choose2}\choose1,2,3.....,n}$$ Any ideas?
2
votes
3answers
76 views

number of subsets from the set {1,2,3,…,n} whose sum is even?

I was told to do this using recursion (no loops and cannot be in constant n time). We essentially have a linked list starting at 1 going until n. I have figured out how to do this mathematically, but ...
5
votes
1answer
46 views

Lattice Paths problem

I was assigned to determine the number of "lattice paths" that are in a 11 x 11 square. Recalling that I can only go upwards and rightwards, here is my approach: Note: The red square is the ...
2
votes
0answers
20 views

Need a hint with permutations and pigeonhole-principle question

let $\pi_1,\pi_2,\pi_3\in S_{28}$. Help me prove that there are two sub-sequences of 28 with length 4 $i_1< i_2 <i_3<i_4,\ and\ \ j_1<j_2<j_3<j_4$ so that $\pi_q(i_n)=\pi_p(j_n)$ ...
0
votes
2answers
67 views

Need hint about with pigeonhole principle problem

$a_i$ and $b_i$ are two sequences with $2n$ elements where $\forall i:\ 1\leq i\leq 2n\implies\ 1 \leq a_i , b_i \leq n$ . I need to show that there are two subsets of indexes $I,J\subset [2n]$ so ...
0
votes
2answers
28 views

How many 4digit numbers can be written with $0,1,3,4,5,6,8,9$ and conditioned that numbers have to be greater than 4500

How many 4digit numbers can be written with $0,1,3,4,5,6,8,9$ and conditioned that numbers have to be greater than 4500 ?
0
votes
2answers
48 views

Solving a horse race related problem

How many ways are there for N=4 horses to finish if ties are allowed? Note that order does matter! One of my friends solved this problem in the following way and he told answer for N=5 will be 541. He ...
0
votes
2answers
23 views

Double Factorial: Number of possibilities to partition a set of $2n$ items into $n$ pairs

I know that the partition of $2n$ items into $n$ pairs has something to do with double factorial, but I am not sure how many possibilities we exactly have. We can choose such a partition into pairs ...
0
votes
1answer
41 views

Number of possible ways to distribute 15 chocolate bars among 10 children

(Introduction to Probability, Blitzstein and Nwang, p. 39) There are 15 chocolate bars and 10 children. In how many ways can the chocolate bars be distributed to the children, in each of the ...
1
vote
1answer
39 views

Number of different normalized inner products?

Let $u,v\in\{0,1\}^n$ be $0-1$ vectors with $n$ components. Let $I=\langle u,v \rangle$. Clearly $I$ can take values in $\{0,1,\dots,n-1,n\}$. How many different values can $$I'=\frac{\langle u,v ...
1
vote
1answer
33 views

Counting review(permutations); Discrete Structures [closed]

You are given $6$ distinct books and $5$ identical blocks of wood. How many ways are there to arrange these books and blocks in a straight line? (a) $\dfrac{11!}{4!}$ (b) $\dfrac{11!}{5!}$ (c) ...
2
votes
1answer
29 views

How many 6digit odd numbers can be written with $0,0,2,2,5,5$

How many 6digit odd numbers can be written with $0,0,2,2,5,5$ This is how my textbook solve the problem $(3 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 2) \cdot \frac{1}{2! \cdot 2!} = 18$ But I'm ...
0
votes
1answer
44 views

In how many ways can you distribute 18 fruits among 18 pirates so that each gets 1 piece of fruit?

Assume you have 5 oranges, 7 limes, and 6 lemons. How many ways can you distribute these among 18 pirates so they can each get 1 fruit and avoid scurvy? (This is a homework problem) My first ...
1
vote
0answers
25 views

Let $p,q$ and $r$ be positive prime numbers. Determine the number of abelian groups of order $p^6q^3r$

Let $p,q$ and $r$ be positive prime numbers. Calculate the number of non isomorphic abelian groups of order $p^6q^3r$. I've tried to use the structure theorem. So we have $$G \cong \mathbb Z/\langle ...
1
vote
4answers
122 views

How many ways can the vertices of an equilateral triangle be colored using three different colors?

Its not $3^3$ because some of the colorings are equivalent. How would I apply Burnside's theorem to this?
0
votes
1answer
17 views

Interchangeable Suits in a Deck of Cards

I have $32$ cards and am going to deal all of them to $4$ players. Player 1 has 32 choose 8 possible hands. player 2 has 24 choose 8 possible hands. Player 3 has 16 choose 8 possible hands. Player ...
0
votes
2answers
19 views

Find a closed form for the generating function for each sequence below

I understand the generating function of this sequence. But I'm not sure how to put this in the closed form. (1) -1,-1,-1,-1,-1,-1,-1,0,0,0 (2) 0,0,3,-3,3,-3,3,-3 (3) 1,0,1,0,1,0 (4) $a_n = 4-7n$ ...
9
votes
0answers
165 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
0
votes
2answers
38 views

Derangement formula; proof by induction

Proof by induction that $ d_{n}=nd_{n-1}+(-1)^{n} $ where $d_{n}$ is number of $n$-element derangements.
0
votes
1answer
42 views

How many nonisomorphic graphs are there with 10 vertices and 43 edges?

How would I go about solving this? I know that $K_{10}$ has $9+8+7+\dots+1=45$ edges. So would it be something like $\binom {45}{43}$ because out of the 45 total edges, one must choose 43 for the ...
-3
votes
0answers
63 views

Colors Problem: Given Equation [duplicate]

What is the smallest positive integer $n$ that satisfies the following condition: We can color each positive integer with one of those $n$ colors such that the equation $w + 6x = 2y + 3z$ has no ...
1
vote
1answer
22 views

How many different vertical arrangements are there of 10 flags if…?

How many different vertical arrangements are there of 10 flags if 4 are white, 3 are blue, 2 are green and 1 is red? I know the answer is 12 600 but am not sure how to get to it. Could someone walk ...