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
0answers
38 views

Need to create a list of combinations from a given set

I need the best way to create a list of all the combinations for a given set so each element in the list sits next to all others with the least number of repeated combinations. Example: I have x ...
1
vote
0answers
31 views

Probability of alternating shirts

5 men are wearing red shirts and 5 men are wearing blue shirts. If the 10 men are lined up randomly, what is the probability that the colors will alternate? My attempt: I started out by assuming ...
0
votes
0answers
24 views

Ramsey number for tree and complete graph [duplicate]

I am having a lot of trouble understanding Ramsey theory. I am working on an exercise that asks for the Ramsey number $R(T,K_{1,n+1})$ where $T$ is a tree with $m$ edges and $n$ is a multiple of $m$. ...
0
votes
1answer
67 views

Combinatorics: Using binomial coefficients to figure out playing card combinations

I have this sample problem from my notes about how to find different 5-card poker hands from a standard 52-card deck. Can someone explain to me what's going on? I don't get why the ...
0
votes
1answer
46 views

Multiple persons flip biased coins multiple times

I've been trying to solve this seemingly easy problem for some time, but I'm not that well-versed in probability, so I thought I would ask. Let there be $N$ persons each with identical biased coins ...
1
vote
0answers
80 views

A problem of periodic functions , the greatest common divisor and a lattice

I am trying to solve the following problem. If $\psi(s) = \frac{s(s-1)}2$. I write $f(s,k) = (\psi(s),\psi(s-k))$, where $k$ is a fixed positive integer. Let $K$ be the image of $f_{s,k}$. If $s>3$...
0
votes
2answers
33 views

The Hand Shaking Lemma

In any graph G=(V,E) [the hand shaking lemma] $$ \sum_{v \in V} \deg(v) = 2 |E| $$ (original at http://i.stack.imgur.com/af4en.png) where |E| donetes the number of edges I alredy tried to count ...
0
votes
0answers
19 views

Number of object distribution between four people (with cases)

Four people are dealing the total amount of money, which is $1000$ monetary units in terms of $100$ monetary units. Count the number of ways for this distribution if: $1)$ Every person doesn't have ...
0
votes
1answer
32 views

How many of the spanning trees, $K_n$ have vertex n as a leaf?

So I know that I should probably use Cayley's formula here, which is that for positive integer $n$, there are $n^{n-2}$ labeled trees on n vertices. So I looked at a few trees and saw that when n = 3 ...
0
votes
2answers
27 views

Combinatorics How Many Tree

How can I prove that for any tree $G=(V,E)$, $$ |E|=|V|-1 $$ I have tried the induction on the number of vertices but nothing happened.
0
votes
1answer
59 views

Sum of the first k multi-nomial coefficients for fixed n

Multinomial coefficients are defined as $$\binom{n}{k_1,k_2,\cdots,k_m}$$ where $n=k_1+k_2+\cdots+k_m$ Is there closed form solution available for the sum of the first $t$ multinoial coefficients? ...
1
vote
1answer
28 views

Combinatorics - # of ways to choose people to 2 groups with condition

In a class there are 30 students, we need to choose 2 groups of 11 students so they can play against each other. Josh, one of the pupils has to be in one of the groups. What I did is this: We'll put ...
1
vote
3answers
49 views

Combinatorics - arranging people in a circle with a condition

Adam has 12 children In how many ways we can arrange his children around a circle table if Josh cannot sit next to Mark? My solution to this is: The total number of permutations for a circle is: $(n-...
2
votes
2answers
603 views

A Seating Optimisation Problem

Suppose that you have a cinema hall of size $n\times m$ (where $n$ is the number of rows and $m$ the number of seats in a row). Now, given that there are exactly $l$ people who need only the left ...
8
votes
1answer
121 views

Roots of unity filter, identity involving $\sum_{k \ge 0} \binom{n}{3k}$

How do I see that$$\sum_{k \ge 0} \binom{n}{3k} = (1 + 1)^n + (\omega + 1)^n + (\omega^2 + 1)^n,$$where $\omega = \text{exp}\left({2\over3}\pi i\right)$? What is the underlying intuition behind this ...
2
votes
0answers
140 views

determine number of possible combinations having maximum element less than sum of remaining elements

I am provided with a value m , such that I have numbers from 1 to m , and another number n ( n<=m) such that I can choose any n numbers from given m numbers. Now I need to calculate number of ...
1
vote
1answer
44 views

Show that the sum of a run of integers is divisible by $n$

Here is the problem: Let $a_1,a_2,...,a_n$ be integers. Show that there exist integers $k$ and $r$ such that the sum $$a_k+a_{k+1}+...+a_{k+r}$$ is divisible by $n$. My thoughts: I suppose we ...
1
vote
1answer
69 views

Example(s) of a symbolic dynamical system with proximal but not asymptotic points

Can anybody give me (an) example(s) of a symbolic dynamical system (preferably arising from a substitution) which has a pair of points which are proximal but not asymptotic? I would prefer to work ...
0
votes
3answers
126 views

How many ways to arrange INSTRUCTOR

How many ways to arrange INSTRUCTOR, in which there are exactly two consonants between successive pairs of vowels. Before any full blown solution could I get a hint towards how to consider the ...
2
votes
2answers
54 views

Number of ways three awards can be given to 5 students

Three distinct awards are to be given to a group of five students. In how many ways can this be done if (a) no student receives more than one award and (b) no student receives more than two awards? ...
1
vote
0answers
195 views

How many Strings of 6 letters contain: Exactly one Vowel, At least one Vowel?

I'm asked the following two questions: How many Strings of 6 letters contain a) Exactly one Vowel b) At least one Vowel a) This is what I know: The English alphabet has 21 consonants and 5 vowels. ...
0
votes
2answers
193 views

How many ways to pair off women at a dance.

How many ways are there to pair off 10 women at a dance with 10 out of 20 men? Soln: P(20,10) X 10! (For the positions each woman could take) My first reaponse was to use a technique with $\binom{...
2
votes
1answer
52 views

Choose Sixteen Cookies from Five Varieties

A cookie shop sells 5 different kinds of cookies. How many different ways are there to choose 16 cookies if... (a) you have no restrictions? (b) you pick at least two of each? (c) you pick at ...
0
votes
0answers
22 views

How should a composite variable be constructed?

I have a set of multiple variables which are used as the arguments of a function. I have collected all of the instances of the various values of the variables together with the output of the function ...
0
votes
1answer
37 views

Existence of a (40,13,4)BIBD (Balanced Incomplete Block Design)

I have been asked to prove that there exists a (40,13,4)BIBD. I admittedly have no idea where to start with this. Checking some of the necessary conditions for BIBDs shows me that if such a BIBD ...
0
votes
2answers
34 views

How to calculate a sum which implicates sets

So the set $A=\{1, 2, 3, 4, 5, 6\}$ and $P(A)$ the set of the parts of $A$. And $f : P(A)\to \mathbb{N}$ the function which associates to each subset of $A$ its cardinality. Calculate $$\sum_{E\in P(...
1
vote
1answer
133 views

In how many ways can you split 100 identical coins to 5 people, so that no one gets more than 50 coins?

In how many ways can you split 100 identical coins to 5 people, so that no one gets more than 50 coins? I know the general formula : $\binom{n+k-1}{n-1}$ Can someone give me some directions?I was ...
1
vote
1answer
68 views

Determine the number of relations on A that are

I'm sure this is a super simple question but I'm a bit stuck on how exactly I'm supposed to solve this. I have a feeling this might be a counting related question but I'm not sure. If anyone could ...
0
votes
2answers
81 views

How many 10 letter sequences are there using 5 vowels and 5 consonants?

How many 10 letter sequences are there using 5 vowels and 5 consonants? What is the pribability ome of these words has no consecutive pair of consonants? For the first part I reasoned that each ...
2
votes
0answers
43 views

What do we know on the number of groups of a given order?

I wanted to recast this question, it was asked at least once for example here: Known bounds for the number of groups of a given order. The reason I ask again is, that in the answers is not much ...
1
vote
1answer
47 views

6 digit number with digit(0-9) precisely 4 or 5 different digits

I just want to be sure if i'm right so i have: For 4 digits: $C(10,4) = 210 $- to get number of combinations of 4 different digits 1 digit repeat 2 more times - $C(4,1) = 4 $ number of other ...
1
vote
1answer
33 views

Distinct birthdays problem. Verification of solution.

Question Consider $n$ people who are attending a party. We assume that every person has an equal probability of being born on every day of the year, independent of everyone else. Assuming that nobody ...
-1
votes
4answers
61 views

Proving algebraic identities

Could someone show how: $$\binom{n}{r}+\binom{n+1}{r}+\binom{n+2}{r}=\binom{n+3}{r+1}?$$ I tried expanding but in the end nothing really got cancelled to prove the identity.
2
votes
2answers
301 views

Choosing $3$ objects from $32$ equidistant objects on a circle with restrictions given.

Suppose $32$ objects are placed along a circle at equal distances. In how many ways can $3$ objects be chosen from among them so no two of the three chosen objects are adjacent nor diametrically ...
1
vote
0answers
34 views

How many different topology exist on A, where is |A| = n [duplicate]

So the question is "How many different topologies exist on A union, where is |A| = n"?
1
vote
0answers
49 views

Congruence of Euler numbers modulo Fermat numbers

The exponential generating function of the unsigned Euler numbers $E_{n}$ is $$\frac{1}{\cos x}=\sum_{n\ge 0}\frac{ E_n}{n!}x^n$$ For $k,n\gt0$, not too large, one can observe that $$E_{ 2^{2^k}\...
0
votes
0answers
23 views

How to partition a set of integers to minimize a function?

The input of my problem consists of two sets of positive integers: $x$ (of size $n$) and $c$ such that $\sum_{c_i \in c}c_i=n$ and $c_i\geq c_{i+1}$. For example, we have: $x=\{600,300,50,700,900,20,...
1
vote
2answers
766 views

In how many ways can we arrange 4 letters of the word “ENGINE”?

I need to know a combinatoric solution to this problem, with Generating functions in book, gives us 102. It might be a very simple problem, but Im very confused with this. Would be very nice of you ...
-2
votes
2answers
134 views

Combinatorics Choosing Objects Under Condition

If 28 objects are arranged in a circle at equal distance from each other, in how many ways can 3 objects be chosen such that no two are adjacent or diametrically opposite.
2
votes
1answer
50 views

Count the pair of numbers that satisfy the set

I have an operation $f$ which takes two numbers $A$ and $B$ and returns a symmetric difference of digits of these two numbers. For example having $453$ and $1134$ the operation will produce a set <...
3
votes
4answers
116 views

String of 0's and 1's in combinatorics

Here is a question in one of my combinatorics homework. We want to know the number of string of $n$ ones and zeros in which no zeros are next to one another and out of those $n$ digits we have $m$ ...
1
vote
1answer
98 views

Seeking a combinatorial proof $\sum _{k=0}^n (n-2k)^3\binom{n}{k}=0$

I would appreciate if somebody could help me with the following problem Q: Seeking a combinatorial proof $(\binom{n}{k}=\frac{n!}{k! (n-k)!} )$ $$\sum _{k=0}^n (n-2 k)^3 \binom{n}{k}=0$$
0
votes
1answer
48 views

There are 5 cubes, each cube has a different color and on each cube the numbers 1-6. Someone throws the cubes

There are 5 cubes, each cube has a different color and on each cube the numbers 1-6. Someone throws the cubes. How many combinations are there, in which the set of the numbers that appear on the cubes ...
0
votes
0answers
25 views

Infinite monkey theorem: Average times a given string appears in $n$ typed characters?

I'm trying to get my head around how to think about the following case of the infinite monkey theorem. How many times on average does a given string appear in $n$ characters typed by the monkey? ...
-1
votes
2answers
98 views

3 girls and 4 boys were standing in a circle . What is the probability that two girls are together but one is not with them?

Question: 3 girls and 4 boys were standing in a circle . What is the probability that two girls are together but one is not with them ?
0
votes
1answer
17 views

Independent Set of Product Graph and Ramsey Number

For two graphs $G,H$, define $G\otimes H$: it has vertex $V(G)\times V(H)$, $(v_1,v_2)(v_1',v_2')\in E(G\otimes H)$ if it satisfies all the following three requirments (i) $(v_1,v_2)\neq (v_1',v_2')$ ...
1
vote
2answers
55 views

Two different answers - cubes and colors

If there are 5 cubes in 5 different colors (on each cube the numbers 1-6), and I want all the ways to choose the cubes so that at least 1 cube shows the number '3'. I can think of two different ways ...
4
votes
1answer
50 views

There are 5 cubes, each cube has a different color and on each cube the numbers 1-6

There are 5 cubes, each cube has a different color and on each cube the numbers 1-6. Someone throws the cubes. a. How many results are there? I was thinking: $6^{5}$ ways for the throws regardless of ...
3
votes
0answers
20 views

Within the number of different ways to order in line the letters of the word NOVATOLOGY, in how many ways G and N are not successive?

Within the number of different ways to order in line the letters of the word NOVATOLOGY, in how many ways G and N are not successive? I was thinking - let's put aside N and G. There are $\frac{8!}{3!}$...
0
votes
1answer
55 views

How many surjective functions are there. [duplicate]

How many surjective functions exist from the set $A= \{1,2,3,4,5,6\}$ (Domain) to the set $B=\{w,x,y,z\}$ (Image). I have no idea on how you do this. Any hints would be helpful. I know that I can ...