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)

11
votes
2answers
103 views

Students who see ears of another student

A student is standing in each cell of an $n\times n$ grid, looking at one of the four directions: up, down, left, right. It turns out that no student is at the border and looking out of the grid, and ...
2
votes
2answers
36 views

Number of winning tern in a deck of cards and other 3 related questions

There is a deck made of $81$ different card. On each card there are $4$ seeds and each seeds can have $3$ different colors, hence generating the $ 3\cdot3\cdot3\cdot3 = 81 $ card in the deck. A tern ...
3
votes
0answers
71 views

Prime factors of binomials

Is it true that for each $n\geq 2$ there are two primes $p, q$ such that (at least) one of them divides $\binom{n}{k}$ for each $1\leq k\leq n-1$? Examples: For $n=6: \binom{6}{1}=6; ...
0
votes
1answer
36 views

Positive integers NOT divisible by 3 or more primes

How many positive integers $<200$ are NOT divisible by 3 or more primes ? My answer: \begin{eqnarray*} &=&\text{Number of positive integers less than }200-\text{ Number of composite ...
2
votes
1answer
41 views

How many different cubes can be obtained if four colours are used?

I would like a confirmation to my answer. In this question, faces sharing a common edge cannot be of the same colour. My way of reasoning started by choosing the colours Red (R), Yellow (Y), Green ...
3
votes
2answers
63 views

Calculate $\sum_{j=0}^k\binom {2k+1}{2j+1}^2=?$

Knowing that: $${2k\choose k}=\sum_{j=0}^k{k\choose j}^2.$$ calculate the sums: $$\sum_{j=0}^k\binom {2k+1}{2j+1}^2=?$$ Any sugestions please? Thanks in advance.
2
votes
1answer
35 views

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

I got the following problem: Given a set of 16 different people. We partition the people into pairs of two. Each pair needs to accomplish a task. And the probability that a pair accomplishes ...
2
votes
1answer
30 views

groups with equal sums [duplicate]

Suppose we have $2n+1 $ real numbers.if we remove any of these numbers we can seperate the remaining $ 2n $ numbers in two groups of $ n $ numbers with equal sums.show that all these numbers are ...
2
votes
1answer
42 views

Counting permutations of a multiset restricted by nearness condition

I've been scratching the noggin on this for a bit, and have come up blank so far. Given a multiset $S$ with $Z$ zeros and $O$ ones, how many permutations are there where there is at least one pair of ...
3
votes
1answer
36 views

Finite abelian groups (application of structure theorem)

Problem Find all finite abelian groups that simultaneously have exactly $7$ elements of order $2$, exactly8 elements of order $3$, exactly $8$ elements of order $4$, at least an element of order ...
2
votes
0answers
39 views

General solution for a combinatorial problem

I want to find a general solution for a problem. I explain the problem with an example. $\underline{Problem}:$We have a matrix $A$ of size $M \times N$, where $M <N$. We choose sub-matrices of ...
0
votes
0answers
58 views

Generalization of Binary Bracketing

Is there possibly any natural approach to generalize the idea of binary bracketing (bracketing functions) to the continuous case, such that the well-known discrete version becomes a special case of ...
1
vote
3answers
36 views

ordered pairs $(A,B)$ of subsets of $X$ >such that $A\neq \phi\;,B\neq \phi$ and $A\cap B = \phi\;,$ is

Let $X$ be a set of $5$ elements. Then the number of ordered pairs $(A,B)$ of subsets of $X$ such that $A\neq \phi\;,B\neq \phi$ and $A\cap B = \phi\;,$ is $\bf{My\; Try::}$ Let $X = ...
0
votes
3answers
27 views

Grandfather-Grandchildren Family Photograph Combinatorics Problem.

In how many different ways a grandfather along with two of his grandsons and four granddaughters can be seated in a line for a photograph so that he is always in the middle and the two grandsons are ...
0
votes
1answer
47 views

Combinatorics-Table Arrangement

How many way can you arrange 10 people in a circle given that 2 particular people cannot sit together? I'm not sure how to solve this. I was thinking of maybe $\frac{8!}{10!}$ But I'm pretty sure ...
3
votes
4answers
186 views

Formula for $1! \times 2! \times \cdots \times n!$?

Are there any useful forms for the expression $1!\cdot 2!\cdot 3!\cdot ...\cdot n!$? I'm trying to solve a problem that involves this expression and thought it might help to find a more "workable" ...
3
votes
0answers
38 views

Trying to prove a congruence for Stirling numbers of the second kind

I am struggling with a demonstration for this: When $n$ and $m$ are 2 natural integers such that $n-m$ is odd, then the following congruence holds for Stirling number of the second kind ${n \brace ...
0
votes
2answers
25 views

Length required to get equivalent password security based on available character set

I understand a password of length 12 is very secure if each character is independent of the others and it potentially mixes the 26 lowercase, 26 uppercase, 10 digits, and 32 typeable special ...
2
votes
1answer
29 views

Getting a full house with exactly 3 suits represented

How many ways can you make a full house with only 3 suits represented in the 5 card hand? My attempt: get the pair first: $$ {13 \choose 1}{4 \choose 2}$$ this allows us to pick any $2$ suits ...
3
votes
2answers
90 views

Find the function of integer numbers $\sum_{n=0}^{\infty }\frac{n^k}{n!}=f(k) \cdot e$

Find the function of integer numbers $$\sum_{n=0}^{\infty }\frac{n^k}{n!}={f(k)}\cdot e$$ I took many values of $k$ and I found the following results $$\sum_{n=0}^{\infty }\frac{n^1}{n!}=e$$ ...
3
votes
1answer
86 views

Some combinatorial identity.

Let $a_1 \ge 0$ and $a_2 \ge 0$ be real numbers and let $n_1 \ge 0$ and $n_2 \ge 0$ be integers. Finally let $m\ge 1$ be another integer. By using the method of generating functions I have shown that ...
2
votes
1answer
37 views

$A$: set of Alice's frieds, $B$: Bob's friends, $C$: all people. Find $P(A \subseteq B)$ and $P(A \cup B = C)$

(Introduction to Probability, Blitzstein and Nwang, p.80) Alice, Bob, and 100 other people live in a small town. Let C be the set consisting of the 100 other people, let A be the set of people ...
1
vote
0answers
22 views

What is $F_P$ and $E(P)$?

I'm reading Handbook of Graph Theory: At this section, he speaks about $F_P$ and $E(P)$. It's not really clear what they are. I guess there is enough context for someone to answer me but if ...
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
0answers
37 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
10 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
14 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$ ...